Счетное множество

Счётные множества

Множество, равномощное множеству всех натуральных чисел, называетсясчётным .

Мощность множества натуральных чисел обозначается א0 = |N|.

Не более чем счётное множество – множество счётное или конечное.

Этим определением мы достали из класса эквивалентности, который назвали счётным, одного представителя – множество натуральных чисел – и теперь есть с чем сравнивать другие множества.

Любая биекция &#&57;. N &#85&4; M называется нумерацией множества М. М=i | i= 0, 1,2, …>.

Таким образом, если найдена нумерация некоторого множества, то тем самым доказано, что оно счётное. Элементы счётного множества называют также последовательностью.

Пусть задан алфавит А – некоторое множество символов, называемых также буквами. Назовём словом в данном алфавите конечный ряд букв, написанных друг за другом. Иногда удобно рассматривать пустое слово, совсем не содержащее букв – его обозначают &#&23;.

Докажем, что в любом языке имеется счётное множество слов

Теорема. Если алфавит А конечен, то множество слов в алфавите А* счётно.

Следствие. слов в алфавите <0,1,2,…,9> – счётное число. Это – проверка на корректность – мы снова подтвердили счётность множества натуральных чисел.

Теорема. Любое подмножество счётного множества не более чем счётно.

&#&633; Пусть А – счетно. Значит, его элементы могут быть перенумерованы: <а1. а2. …, an ,…>. Элементы любого подмножества ВÍА можно расположить в порядке возрастания номеров: . Следовательно, подмножество имеет нумерацию &#&57;(n)= &#&632;

Теорема. Любое бесконечное множество содержит счётное подмножество.

&#&633; Пусть А0 — бесконечное множество. Значит, оно непусто и $ а1 ÎА0. Положим А10 \1 >. А1 не пусто, т.к. в противном случае А0 =1 >, что противоречит предположению о бесконечности А0. Продолжим процедуру: в А1 найдётся a2. положим А21 \2 >=А0 \1. a2 > …и т.д.

На n-шаге получим: Аn0 \1. …,an > непусто, т.к. в противном случае А0 =1. …,an >. Кроме того, по построению ai ≠ak. если i ≠ k – элементы попарно различны. Тогда $ аn ÎАn и, по построению, Аn+1 = Аn \n > непустое множество.

Таким образом, по индукции мы построили множество, состоящее из попарно различных элементов <а1. а2. …, an ,…>Î А0 с нумерацией &#&57;(n)=an. &#&632;

Из доказанных теорем следует, что счётное множество является самым минимальным по мощности из всех бесконечных множеств – потому, наверно, его и называют алеф ноль.

Теорема. В любом бесконечном множестве можно выделить два непересекающихся между собой счётных множества. Доказательство – разбиение на чётную и нечётную нумерации.

Теорема. Объединение любого не более чем счетного семейства множеств счётно.

Занумеруем элементы объединения семейств следующим образом:

a) I конечно; б) I счетно

Последовательность (a11 ,a21 ,a12 ,a22 ,a31 ,…) – нумерация. Принцип её построения таков – сначала фиксируется N = 2 и записываются аik такие, что i+k = N. Затем N &#85&4; N+1 и все повторяется.

Замечание: В семействах могут быть одинаковые элементы

Следствие. Множество А* всех слов в счётном алфавите А счётно. Пусть задана нумерация в А: A=<а1. а2. …, an ,…>

Обозначим через Аn конечный алфавит: Аn =<а1. а2. …, an >. Любое слово в А* состоит из конечного числа букв (по определению), поэтому оно является словом в некотором конечном алфавите, а именно в Ak. k=max(k1. k2. …, kn ). Т.о. множество всех слов в алфавите А есть объединение счётного числа множеств А1. А2 ,…, Аn .

Пример. Алгебраические числа. Корни произвольного многочлена an x n +… + a0. где аk – целые числа, называются алгебраическими числами. Многочлен можно рассматривать как слово в конечном алфавите: А=<0,1,2,… ,*,+,-> – множество таких слов счетно, а корней у многочлена конечное число. Поэтому и множество всех алгебраических чисел счётно.

Теорема. Множество значений функции, определённой на счётном множестве, не более чем счётно. &#&57;(n) = f(an ) – нумерация.

Теорема. Пусть А – бесконечное множество, а B – его не более чем счётное подмножество. Тогда, если множество A\B бесконечно, то оно равномощно множеству A .

Выберем из A\B счётное подмножество C ; по построению B∩C =О. Объединение B и C счётно, поэтому существует биекция f. BÇC→C. Надо построить биекцию А&#85&4; A\B. Построим:

Следствие. если A бесконечно, а B не более чем счётно, то объединение AÇB не более чем счетно.

Счетные и несчетные множества.

Лекция 10. Конечные и бесконечные множества

10.1.Конечные и бесконечные множества

10.2.Счетные и несчетные множества.

10.3.Счетность множества рациональных чисел.

10.4.Несчетность множества действительных чисел

Лекция посвящена вопросам сравнения бесконечных множеств. Рассматриваются счетные и несчетные множества, вводится понятие мощности как инструмента различения бесконечных множеств

Обратите внимание на различие в определении счетных и несчетных множеств, понятие мощности

А.В. Дорофеева «Высшая математика» глава XIV стр.330-356

Р.Курант, Г.Роббинс «Что такое математика» глава II § 4, стр. 104-115

А.Я.Хинчин «Восемь лекций по математическому анализу». Лекция 1 «Кнтинуум»

1. Приведите примеры конечных и бесконечных множеств

2. Дайте определение счетного множества (приведите примеры)

3. Дайте определение несчетно множества (приведите примеры)

4.Покажите, что у конечного множества из n элементов 2 n подмножеств

4. Докажите, что множество рациональных чисел счетно

5. Докажите, что множество действительных чисел несчетно

6. Приведите примеры множеств эквивалентных отрезку [0,1]

Конечные и бесконечные множества

Рассматривая различные множества, мы замечаем, что иногда можно, если не фактически, то хотя бы примерно, указать число элементов в данном множестве. Таковы, например, множество всех вершин некоторого многогранника, множество всех простых чисел, не превосходящих данного числа, множество всех молекул воды на Земле и т. д. Каждое из этих множеств содержит конечное, хотя, быть может, и неизвестное нам число элементов. С другой стороны, существуют множества, состоящие из бесконечного числа элементов. Таково, например, множество всех натуральных чисел, множество всех точек на прямой, всех кругов на плоскости, всех многочленов с рациональными коэффициентами и т.д.

Говоря, что множество бесконечно, мы имеем в виду, что из него можно извлечь один элемент, два элемента и т.д. причем после каждого такого шага в этом множестве еще останутся элементы.

Два конечных множества мы можем сравнивать по числу элементов и судить, одинаково это число или же в одном из множеств элементов больше, чем в другом. Спрашивается, можно ли подобным же образом сравнивать бесконечные множества? Иначе говоря, имеет ли смысл, например, вопрос о том, чего больше: кругов на плоскости или рациональных точек на прямой, функций, определенных на отрезке [0,1], или прямых в пространстве, и т.д.?

Сравнение конечных множеств

Сравнивая конечные множества можно поступать двояко:

1) подсчитать и сравнить число элементов

2) попытаться установить биекцию, т. е. взаимно однозначное соответствие между элементами этих множеств, иначе говоря, такое соответствие, при котором каждому элементу одного множества отвечает один и только один элемент другого,

и наоборот. Ясно, что взаимно однозначное соответствие между двумя конечными множествами можно установить тогда и только тогда, когда число элементов в них одинаково.

Например, сравнивая множество студентов 1 курса и множество стульев в аудитории № 1 можно подсчитать количество студентов и стульев, а можно рассадить студентов в аудитории, тем самым попробовав установить взаимно однозначное соответствие между этими множествами. Если мест хватит всем и не останется ни одного лишнего стула, т. е. если будет установлена биекция между этими двумя множествами, то это и будет означать, что число элементов в них одинаково.

Первый способ (подсчет числа элементов) годится лишь для сравнения конечных множеств, второй (установление взаимно однозначного соответствия) пригоден и для

Счетные и несчетные множества.

Назовем счетным множеством всякое множество, элементы которого можно биективно сопоставить со всеми натуральными числами. Иначе говоря, счетное множество — это такое множество, элементы которого можно занумеровать в бесконечную последовательность: а1. а2. а3. …

1. Множество всех целых чисел. Установим соответствие между всеми целыми и всеми натуральными числами по следующей схеме:

Счетное множество

вообще, неотрицательному числу n≥0 сопоставим нечетное число

2n + 1, а отрицательному n < 0 — четное число 2n:

Счетное множество

2. Множество всех четных положительных чисел. Соответствие

3. Множество 2,4, 8. 2 n. степеней числа 2. Здесь соответствие также очевидно. Каждому числу 2 n сопоставляется число n.

4. Множество рациональных чисел (см. п.10.3)

Пусть X — счетное множество, т. е. существует взаимно однозначное отображение (биекция) множества натуральных чисел N на множество X. Элемент множества X, соответствующий при этом отображении числу n, обозначим, как и в случае последовательности, хn и будем называть число n его номером. Поэтому можно сказать,

что множество является счетным, если его элементы можно перенумеровать натуральными числами.

Отличие определения счетного множества от последовательности состоит в том, что в случае последовательности рассматриваемое отображение множества натуральных чисел не обязано быть биекцией: не исключается случай, когда разным натуральным числам окажется поставленным в соответствие один и тот же элемент. Отсюда следует, что множество значений членов последовательности либо конечно, либо счетно, т. е. как говорят, не более чем счетно .

Любое бесконечное множество содержит бесконечное счетное подмножество.

Пусть X — бесконечное множество; тогда оно во всяком случае непусто, т. е. в нем существует по крайней мере один элемент, обозначим его через х1. Поскольку множество X бесконечно, то множество X \ 1 > также непусто, т. е. содержит по крайней мере один элемент, обозначим его х2. Продолжая этот процесс, на n-м шаге получим элемент хn. Поскольку X — бесконечное множество, то множество X \<х1 ,x2. хn > непусто, т. е. содержит по крайней мере один элемент, обозначим его хn+1 и т. д.

Множество < х1 ,x2. хn. > — искомое счетное подмножество множества X.

Любое бесконечное подмножество счетного множества счетно.

Пусть X — счетное множество: X = < х1 ,x2. хn …>и Счетное множество .

Обозначим через у1 элемент из У, имеющий наименьший номер в X, через y2 — элемент множества У, имеющий следующий ближайший номер, и т. д. Поскольку каждый элемент множества Y является некоторым элементом хn множества X и, следовательно, имеет номер n, то через конечное число шагов (не больше, чем n) он получает некоторый номер m и в множестве У, т. е. будет обозначен уm. причем, поскольку множество Y бесконечно, этот процесс может быть продолжен неограниченно. Таким образом, все элементы множества Y окажутся перенумерованными, что и означает счетность этого множества. |

Возникает естественный вопрос, существуют ли несчетные множества, т. е. бесконечные множества, не являющиеся счетными, а если существуют, то интересно построить пример несчетного множества. Соответствующий пример рассмотрен в п.10.4

§6. Счётные множества

Понятие равномощности множеств и его свойства позволяют выделить классы равномощных множеств. Интересно знать, как много существует неравномощных множеств и иметь в некотором смысле «эталонные множества», чтобы, сравнивая с ними другие, было легче устанавливать равномощность множеств или её отсутствие.

1. Конечных, но не равномощных множеств, бесконечно много. Их классов столько же, сколько натуральных чисел.

2. Бесконечных, но не равномощных множеств, также бесконечно много.

Возникает вопрос: есть ли среди бесконечных множеств множество наименьшей мощности? Да. Это счётные множества.

Определение 1. ПустьN — множество натуральных чисел. МножествоS называетсясчётным множеством, если оно равномощноN . то естьSN .

Мощность счётного множества имеет специальное обозначение: Счетное множество(первая буква алфавита иврит, читается «алеф-нуль»). Мы будем обозначать мощность счётного множества буквойа :

Примеры счётных множеств

4. Множество квадратов натуральных чисел.

Основные свойства счётных множеств

Теорема 1. Для того чтобы множествоS было счётным необходимо и достаточно, чтобы его элементы можно было занумеровать в последовательность, члены которой попарно различны:

Счетное множество.

Пусть S — счётное множество, тогда существует биекцияf:NS. В этой биекции образ элементаn обозначимаn . тем самым будут занумерованы все элементы множестваS. то естьСчетное множество. Так как все элементы множестваS различны, то и все члены последовательностиСчетное множествопопарно различны.

Пусть Счетное множество,аn попарно различны. Сопоставим элементуаn его номерn. Полученное соответствие изS вN является биекцией. Следовательно, по определениюS — счётное множество.

Теорема 2. Во всяком бесконечном множествеА имеется счётное подмножество.

Возьмём во множестве А произвольный элементСчетное множество. Множество Счетное множество бесконечное (доказывается от противного). Из множества Счетное множество выберем элементСчетное множество. Множество Счетное множество — бесконечное. Из множества Счетное множество выбираем элементСчетное множествои так далее. Так какА – бесконечное множество, то этот процесс продолжим до бесконечности. В результате получим последовательностьСчетное множество. Так как во множествеА все элементы попарно различны, по теореме 1S — счётное множество.

Следствие. Счётная мощность является наименьшей из мощностей бесконечных множеств.

Теорема3. Всякое бесконечное подмножествоВ счётного множестваS счётно:

Теорема 4. Бесконечное множествоВ счётно, если существует сюрьекцияf какого-нибудь счётного множестваS наВ .

Не умоляя общности доказательства можно считать, что S=N . По условиюf:N — сюрьекция (В – это образN при отображенииf. то естьf(N)=В ). Возьмём любой элементСчетное множество,b – образ какого-либо натурального числа. При отображенииf его прообразом является некоторое множество натуральных чиселf-1(b). состоящее из тех элементов, образ которых равенb. то естьf-1(в)=<nN:f(n)=b>. В этом множестве существует наименьшее натуральное числоСчетное множество. Рассмотрим множествоСчетное множество— бесконечное множество (От противного: пустьА конечно. Тогда для бесконечного числа элементовСчетное множествосуществует один элементСчетное множествоN . то есть одному элементуnN соответствует бесконечно много элементовСчетное множество. Это означает, что соответствиеN не является отображением. Получили противоречие с условием. Следовательно, предположение не верно.). Так какАN иА – бесконечное множество, то по теореме 3 множествоА счётно. Рассмотрим соответствиеСчетное множество, при которомСчетное множество. Это соответствие является биекцией. Следовательно,АВ иВ счётно.

Определение 2.Кортежем называется конечное множество элементов.

Теорема 5. МножествоК всевозможных кортежей, составленных из натуральных чисел, счётно.

Пусть Р — множество всех простых чисел, расположенных в порядке возрастания:

Счетное множество.

На основании теоремы о единственности разложения чисел на простые множители различным кортежам соответствуют различные натуральные числа, то есть если

Рассмотрим соответствие f:KА. гдеА – некоторое бесконечное подмножество множестваN . то естьА — счётно (по теореме 3). Указанное соответствие является биекцией. Так какА счётно и. тоK также счётно.

Определение 3.Декартовым произведением А1А2Аm называется множество, состоящее из кортежейСчетное множество, гдеСчетное множество.

Теорема 6. Декартово произведение конечного числа счётных множеств счётно.

Пусть А12,…,Аm — счётные множества. Докажем, чтоА1А2Аm =А — счётное множество. Счётные множестваАk ,Счетное множество, представим в виде последовательностей

Счетное множество;

Счетное множество;

Счетное множество;

Счетное множество.

Возьмём Счетное множество, поставим ему в соответствие кортеж из натуральных чиселСчетное множество. ОбозначимСчетное множество. Указанное соответствие является биекциейf1. Но1 – бесконечное подмножество счётного множества из теоремы 5. По теореме 31 счётно. Так какf — биекция, тоА счётно.

Теорема 7. Объединение конечной или счётной совокупности счётных множеств счётно.

Пусть А12,…,Аm,… — счётные множества. Докажем, чтоСчетное множество — счётное множество.

1. Пусть Счетное множество— объединение счётного числа счётных множеств. Счётные множестваАm представим в виде последовательностей

Счетное множество;

Счетное множество;

Счетное множество;

Счетное множество,

где Счетное множество— это элемент множестваСчетное множествос номеромСчетное множество. Рассмотрим множествоN2=N´N . Оно счётно по теореме 6. Возьмём любой элемент(p,q)ÎN2. Сопоставим ему элементСчетное множество. Так как любой элементСчетное множествопринадлежит хотя бы одному из множествАp и имеет в нём определённый номерq. то указанное соответствие является сюрьекциейf:N2®A. Так как множествоN2 счётно, то по теореме 4 множествоА счётно.

2. Пусть Счетное множество— объединение конечного числа счётных множеств. Положим

Счетное множество,

тогда Счетное множество. По первой части теоремы множествоА счётно.

Теорема 8. МножествоQ рациональных чисел счётно.

Представим множество Q в виде

Счетное множество=>,

Счетное множество,

где Qn — множество дробей видаСчетное множествос фиксируемым знаменателемСчетное множество. Очевидно, чтоQn . то естьQn счётное множество. Тогда по теореме 7 Счетное множество также счётно. НоQ+ является бесконечным подмножеством счётного множества Счетное множество. Тогда по теореме 3 множествоQ+ счётно. В силу того, чтоQ+

Q, заключаем, что множествоQ счётно. По теореме 7 множествоQ+Счетное множествоQ счётно, тогда по теореме 1 множествоQ счётно.

Теорема 9. Объединение счётной совокупности конечных множеств конечно или счётно.

Пусть Счетное множество— конечные множества,Счетное множество.

1. Множество А может быть конечным (например, если все множестваАk равны:Счетное множествоN ).

2. Рассмотрим случай, когда множество А — бесконечно. Пусть множествоАk имеетnk элементов. Присоединим к этому множеству все натуральные числа, большие чемnk . получим счётное множествоВk . Проделаем это для всехk. Рассмотрим множествоСчетное множество. По теореме 7 множествоВ счётно. НоА и является его бесконечным подмножеством. По теореме 3 множествоА счётно.

Теорема 10. Мощность бесконечного множества не изменяется, если к нему присоединить конечное или счётное множествоS .

Случай конечного множества S не интересен, так как является следствием теоремы 1. Рассмотрим случай счётного множестваS. Не нарушая общности доказательства будем считать, чтоСчетное множество=. По теореме 2 множествоВ можно представить в видеСчетное множество, гдеS1 — счётное множество множестваS. Тогда

Счетное множество.

Так как множества Счетное множествоиS1 — счётные множества, то существует биекцияf:Счетное множествоS1. Рассмотрим отображение. определяемое следующим образом:

Счетное множество

Это отображение является биекцией Счетное множество. Следовательно,Счетное множество, то естьСчетное множество.

Определение 4. Если бесконечное множество не является счётным, то оно называетсянесчётным.

Теорема 11. Мощность несчётного множестваМ не изменяется, если из него удалить конечное или счётное подмножествоS .

Пусть М – несчётное множество, тогдаМ \S – бесконечное множество (доказательство от противного). Тогда по теореме 10 Счетное множество.

Определение 5. Числоназываетсяалгебраическим, если оно является корнем некоторого многочлена с целыми коэффициентами.

Теорема 12. МножествоА всех алгебраических чисел счётно.

Пусть М – множество всех многочленов с целыми коэффициентами,Мn – множество многочленов с целыми коэффициентами и с фиксированной степеньюn. Возьмём любой многочленСчетное множество,Счетное множество, из множестваМn . Этому многочлену сопоставим кортеж из его коэффициентовn,…,а0). Множество таких кортежей обозначимТ. Очевидно, чтоТ=(Z\<0>)Zn. Построенное соответствие является биекциейf:МnT. Так как множествоZ счётно, то по теореме 3 множествоZ\<0> также счётно. Следовательно, по теореме 6 множествоТ счётно. Так какf – биекция, тоМn

T. то естьМn счётно. Так какСчетное множествои все множестваМn счётны, то по теореме 7 множествоМ счётно. Итак, множество всех многочленов с целыми коэффициентами счётно и любой многочлен имеет конечное число корней. Следовательно, множествоА представляет собой объединение счётного числа конечных множеств. Так какА – бесконечное множество, то по теореме 9 оно счётно.

Счётное множество это:

В теории множеств. счётное мно́жество есть бесконечное множество. элементы которого возможно пронумеровать натуральными числами. Более формально: множество Счетное множество является счётным, если существует биекция Счетное множество. где Счетное множество обозначает множество всех натуральных чисел. Другими словами, счётное множество — это множество, равномощное множеству натуральных чисел.

Счётное множество является «наименьшим» бесконечным множеством, то есть в любом бесконечном множестве найдётся счётное подмножество. Мощность множества всех натуральных чисел обозначается символом Счетное множество (произносится: «алеф -нуль»).

Содержание

  1. Любое подмножество счётного множества не более чем счётно (т.е. конечно или счётно). [1]
  2. Объединение конечного или счётного числа счётных множеств счётно. [1]
  3. Прямое произведение конечного числа счётных множеств счётно.
  4. Множество всех конечных подмножеств счётного множества счётно.
  5. Множество всех подмножеств счётного множества континуально и, в частности, не является счётным.

Связанные понятия

Несчётное множество  — такое бесконечное множество. которое не является счётным. Таким образом, любое множество является либо конечным, либо счётным, либо несчётным.

Счётные множества

  • Простые числа
  • Натуральные числа
  • Целые числа
  • Рациональные числа
  • Алгебраические числа
  • Кольцо периодов
  • Вычислимые числа
  • Арифметические числа
  • Множество всех конечных слов над конечным или счётным алфавитом
  • Любое бесконечное семейство непересекающихся открытых интервалов на действительной оси
  • Множество всех прямых на плоскости, каждая из которых содержит хотя бы 2 точки с рациональными координатами
  • Любое бесконечное множество точек на плоскости, все попарные расстояния между элементами которого рациональны

Несчётные множества

Примечания

Категория:

  • Теория множеств

Wikimedia Foundation. 2010 .

Смотреть что такое «Счётное множество» в других словарях:

счётное множество — понятие теории множеств, бесконечное множество, элементы которого возможно занумеровать натуральными числами. Множество всех рациональных чисел и даже множество всех алгебраических чисел счётны, однако множество всех действительных чисел несчётно … Энциклопедический словарь

Счётное множество — бесконечное множество, элементы которого можно занумеровать натуральными числами, то есть установить Взаимно однозначное соответствие между этим множеством и множеством всех натуральных чисел. Как доказал Г. Кантор, множество всех… … Большая советская энциклопедия

СЧЁТНОЕ МНОЖЕСТВО — понятие теории множеств, бесконечное множество, элементы к рого возможно занумеровать натуральными числами. Множество всех рациональных чисел и далее множество всех алгебр. чисел счётны, однако множество всех действит. чисел несчётно … Естествознание. Энциклопедический словарь

Несчётное множество — В теории множеств счётное множество есть бесконечное множество, элементы которого возможно пронумеровать натуральными числами. Более формально: множество X является счётным, если существует биекция. где обозначает множество всех натуральных… … Википедия

несчётное множество — понятие теории множеств; бесконечное множество, мощность которого больше, чем мощность счётного множества. Например, множество всех действительных чисел несчётное множество. * * * НЕСЧЕТНОЕ МНОЖЕСТВО НЕСЧЕТНОЕ МНОЖЕСТВО, понятие теории множеств; … Энциклопедический словарь

Счётная мера — в функциональном анализе это формальный эквивалент количества элементов множества. Определение Пусть измеримое пространство, такое что любая точка является измеримым множеством, то есть. Тогда мера. определённая следующим образом … Википедия

Множество Витали — Множество Витали  первый пример множества вещественных чисел, не имеющего меры Лебега. Этот пример, ставший классическим, опубликовал в 1905 году итальянский математик Дж. Витали в своей статье «Sul problema della misura dei gruppi di punti… … Википедия

МНОЖЕСТВО — набор, совокупность, собрание к. л. объектов, называемых его элементами, обладающих общим для всех них характеристич. свойством. Понятие M. принадлежит к числу первоначальных матем. понятий и может быть пояснено только при помощи примеров. Так,… … Физическая энциклопедия

Множество второй категории — Курсив обозначает ссылку на этот словарь # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш … Википедия

Множество первой категории — Курсив обозначает ссылку на этот словарь # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш … Википедия

  • Счётное множество. Джесси Рассел. Эта книга будет изготовлена в соответствии с Вашим заказом по технологии Print-on-Demand. High Quality Content by WIKIPEDIA articles! В теории множеств, счётное мно?жество есть бесконечное… Подробнее Купить за 1125 руб
  • Сепарабельное пространство. Джесси Рассел. Эта книга будет изготовлена в соответствии с Вашим заказом по технологии Print-on-Demand. High Quality Content by WIKIPEDIA articles! Сепара?бельное пространство (от лат. separabilis —… Подробнее Купить за 1125 руб

9. Счетные множества

Множества, равномощные множеству всех натуральных чисел, называют счетными, остальные же бесконечные множества — несчетными. Следовательно, счетное множество — это такое бесконечное множество, все

элементы которого можно перенумеровать с помощью натуральных чисел таким образом, чтобы каждому элементу множества соответствовал определенный номер и чтобы каждый номер соответствовал определенному и единственному элементу множества. Другими словами, элементы счетного множества можно расположить в виде бесконечной последовательности

по порядковым номерам (индексам). Обратно, множество всех членов любой данной бесконечной последовательности (с различными членами) является счетным.

Очевидно, что часть счетного множества, если она не является конечным множеством, будет счетным множеством. Это следует из того, что элементы любой части множества (1) можно расположить в виде последовательности в порядке возрастания индексов. Например, множества всех нечетных чисел, всех простых чисел, всех чисел, являющихся квадратами натуральных чисел, — счетны. О существовании взаимно однозначного соответствия между натуральными числами и их квадратами знал уже Галилей в первой половине XVII века.

Если плоскость разбить на прилегающие один к другому квадраты, то множество этих квадратов будет счетно. Перенумеровать все эти квадраты можно следующим образом (рис. 1):

Можно также доказать, что, разбив трехмерное пространство на равные кубы, мы получим счетное множество этих кубов. И в этом случае можно бы поочередно обходить кубы по ломаной, соединяющей центры смежных кубов.

Непустое множество мы называем конечным, если число его элементов может быть выражено каким-либо натуральным числом. Отсюда следует, что если данное множество бесконечно, т. е. не является ни пустым, ни конечным, то для любого натурального числа существует различных элементов, каждый из которых принадлежит Доказать это можно по индукции. Указанное предложение справедливо для числа так как, поскольку множество не пусто, в нем должен существовать какой-нибудь элемент Допустим теперь, что наше утверждение справедливо для некоторого натурального числа и что, следовательно, существует различных элементов каждый из которых принадлежит множеству Если бы, кроме этих элементов, множество не содержало никаких других элементов, то оно имело бы только элементов и было бы конечно, что противоречит условию. Следовательно, в множестве имеется какой-то элемент отличный от каждого из элементов Мы имеем,

следовательно, различных элементов, каждый из которых принадлежит множеству Утверждение иаше справедливо, следовательно, для числа Отсюда по индукции заключаем о справедливости утверждения для любого натурального числа

Казалось бы, что подобное рассуждение приводит к заключению, что каждое бесконечное множество содержит счетное подмножество (счетную часть). Имея разных элементов множества мы можем извлечь из него новый элемент отличный от каждого из элементов что приводит к бесконечному ряду различных элементов множества т. е. к некоторому его счетному подмножеству.

Но этому рассуждению можно предъявить следующий упрек. Образуя последовательность различных элементов множества мы вынуждены раз произвести выбор. Никто не сомневается в возможности осуществления любого конечного числа выборов. Но есть математики, которые считают, что нельзя производить бесконечно много выборов без указания закона или правила осуществления этих выборов (первым из таких математиков был Дж. Пеано). Без использования так называемой аксиомы выбора (сформулированной Э. Цермело) мы не сможем доказать ни то, что любое бесконечное множество содержит счетную часть, ни то, что каждое бесконечное множество равномощно некоторой своей правильной части.

То, что каждое счетное множество равномощно некоторой своей правильной части, очевидно, так как множество (1) равномощио множеству, которое мы получим, удалив из него первый член Но можно также доказать, не прибегая к аксиоме выбора, что каждое множество, равномощное некоторой своей правильной части, содержит счетное подмножество. Вот набросок этого доказательства. Допустим, что множество равномощно своей правильной части Т. Каждому элементу а множества соответствует определенный элемент множества Т таким образом, что разным элементам множества соответствуют различные элементы множества Т. Поскольку Т является правильной частью множества существует элемент а множества не принадлежащий Т. Теперь можно легко доказать, что члены бесконечной последовательности

являются различными элементами множества и, следовательно, образуют его счетное подмножество.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *