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

Объединение двух счётных множеств счётно.

Доказательство. Рассмотрим два счётных множества ${\displaystyle A}$ и ${\displaystyle B}$; каждое из них можно записать в последовательность:

${\displaystyle {\begin{matrix}a_{0},a_{1},a_{2},a_{3},...\\b_{0},b_{1},b_{2},b_{3},...\end{matrix}}}$ .

Запишем множество ${\displaystyle A\cup B}$ , чередуя элементы из ${\displaystyle A}$ с элементами из ${\displaystyle B}$: ${\displaystyle a_{0},b_{0},a_{1},b_{1},a_{2},b_{2},a_{3},b_{3},...}$ Если ${\displaystyle A}$ и ${\displaystyle B}$ не пересекаются, то на этом рассуждение заканчивается.

Если же множества пересекаются, то в этой последовательности общие элементы встретятся по два раза. Тогда, если очередной элемент уже встречался ранее (например, если элемент ${\displaystyle a_{j}}$ совпадает с элементом ${\displaystyle b_{i}}$ , где ${\displaystyle i<j}$), то его пропускают и второй раз не выписывают. ${\displaystyle \blacksquare }$

Всякое подмножество счётного множества конечно или счётно.

Доказательство. Рассмотрим счётное множество ${\displaystyle A}$ и его подмножество ${\displaystyle A'}$. Выпишем элементы ${\displaystyle A}$ в последовательность ${\displaystyle a_{0},a_{1},a_{2},a_{3},...}$ . Вычеркнем из этой последовательности те элементы, которые не лежат в ${\displaystyle A'}$. В результате останется последовательность элементов ${\displaystyle A'}$ — конечная или бесконечная. В первом случае множество будет конечным, во втором счётным. Формально говоря, для бесконечного подмножества ${\displaystyle A'\subset A}$ искомая биекция ${\displaystyle f:\mathbb {N} \rightarrow A'}$ ставит в соответствие числу ${\displaystyle n}$ элемент множества ${\displaystyle A'}$, который стоит ${\displaystyle n}$-м по счёту в последовательности (если считать только элементы ${\displaystyle A'}$). ${\displaystyle \blacksquare }$

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

Доказательство. Рассмотрим произвольное бесконечное множество ${\displaystyle A}$. Выпишем последовательность из некоторых его элементов, не обязательно всех. Первый элемент ${\displaystyle a_{0}}$ возьмём произвольно. Поскольку ${\displaystyle A}$ бесконечно, в нём есть ещё элементы (кроме ${\displaystyle a_{0}}$). В качестве ${\displaystyle a_{1}}$ возьмём любой из них. И так далее. В общем случае, когда необходимо выбрать очередной элемент ${\displaystyle a_{n}}$, мы рассматриваем подмножество {${\displaystyle a_{0},...,a_{n-1}}$}. Оно конечно, а значит, не совпадает со всем множеством ${\displaystyle A}$ (которое по предположению бесконечно). Значит, в ${\displaystyle A}$ есть элементы, не лежащие в этом подмножестве — и можно взять любой из них в качестве ${\displaystyle a_{n}}$. Получили бесконечную последовательность из элементов ${\displaystyle A}$, и множество элементов этой последовательности образует искомое счётное подмножество множества ${\displaystyle A}$.${\displaystyle \blacksquare }$

Множество рациональных чисел ${\displaystyle \mathbb {Q} }$ счётно.

Декартово произведение двух счётных множеств ${\displaystyle A}$ и ${\displaystyle B}$ cчётно.

Доказательство. По определению декартово произведение есть множество всех упорядоченных пар вида ${\displaystyle \langle a,b\rangle }$, в которых ${\displaystyle a\in A}$, ${\displaystyle b\in B}$. Разделим пары на группы, объединив пары с одинаковой первой компонентой (каждая группа имеет вид ${\displaystyle \{a\}\times B}$ для какого-то ${\displaystyle a\in A}$). Тогда каждая группа счётна, поскольку находится во взаимно однозначном соответствии с ${\displaystyle B}$ (пара определяется своим вторым элементом), и групп столько же, сколько элементов в ${\displaystyle A}$, то есть счётное число.${\displaystyle \blacksquare }$

Вместо натуральных чисел можно рассматривать элементы произвольного конечного или счётного множества ${\displaystyle A}$. Такое множество называют алфавитом, элементы ${\displaystyle A}$ называют буквами, или символами алфавита ${\displaystyle A}$, а конечные цепочки (последовательности) букв называют словами, или строками в алфавите ${\displaystyle A}$^[4].

Множество всех точек сегмента ${\displaystyle [0,1]}$ неcчётно.

Доказательство. Рассмотрим интервал ${\displaystyle (0,1)}$. Если доказать, что интервал ${\displaystyle (0,1)}$ несчётен, то и сегмент ${\displaystyle [0,1]}$ будет несчётен. Докажем, что множество точек интервала ${\displaystyle (0,1)}$ несчётно. Допустим противное, то есть предположим, что все вещественные числа интервала ${\displaystyle (0,1)}$ можно занумеровать.

Запишем все числа интервала ${\displaystyle (0,1)}$ в виде бесконечных десятичных дробей:

${\displaystyle {\begin{matrix}x_{1}=0,a_{11}a_{12}...a_{1n}...,\\x_{2}=0,a_{21}a_{22}...a_{2n}...,\\........\\x_{n}=0,a_{n1}a_{n2}...a_{nn}...,\\......\end{matrix}}}$

Рассмотрим на интервале ${\displaystyle (0,1)}$ вещественное число ${\displaystyle x_{1}=0,b_{1}b_{2}...b_{n}...,}$ где ${\displaystyle b_{1}}$ — любая цифра, отличная от ${\displaystyle a_{11}}$, ${\displaystyle 0}$ и ${\displaystyle 9}$; ${\displaystyle b_{2}}$ — любая цифра, отличная от ${\displaystyle a_{22}}$, ${\displaystyle 0}$ и ${\displaystyle 9}$; и т. д.; ${\displaystyle b_{n}}$ — любая цифра, отличная от ${\displaystyle a_{nn}}$, ${\displaystyle 0}$ и ${\displaystyle 9}$. Достаточно доказать, что число ${\displaystyle x}$ не совпадает ни с одним из чисел ${\displaystyle x_{1},x_{2},...,x_{n},...}$. Число ${\displaystyle x}$ не содержит после запятой нулей и девяток, то есть это число не принадлежит классу рациональных чисел, представимых двумя способами в виде бесконечных десятичных дробей. В таком случае число ${\displaystyle x}$ допускает единственное представление в виде бесконечной десятичной дроби, и оно отлично от всех чисел ${\displaystyle x_{1},x_{2},...,x_{n},...}$, ибо совпадение числа ${\displaystyle x}$ каким-либо числом ${\displaystyle x_{n}}$ означало бы совпадение ${\displaystyle b_{n}}$ и ${\displaystyle a_{nn}}$. Таким образом, интервал ${\displaystyle (0,1)}$, а вместе с ним и сегмент ${\displaystyle [0,1]}$ несчётен^[5].${\displaystyle \blacksquare }$

Счётными являются множества натуральных чисел ${\displaystyle \mathbb {N} }$, целых чисел ${\displaystyle \mathbb {Z} }$, рациональных чисел ${\displaystyle \mathbb {Q} }$, алгебраических чисел ${\displaystyle \mathbb {A} }$. Счётными являются объекты, получающиеся в результате рекурсивных процедур, в частности, таковы вычислимые числа, арифметические числа (как следствие, счётно и кольцо периодов, поскольку каждый период является вычислимым). Счётны множество всех конечных слов над счётным алфавитом и множество всех слов над конечным алфавитом. Любые объекты, которые можно определить со взаимно-однозначным сопоставлением со счётным множеством, счётны, например: любое бесконечное семейство непересекающихся открытых интервалов на вещественной оси; множество всех прямых на плоскости, каждая из которых содержит хотя бы две точки с рациональными координатами; любое бесконечное множество точек на плоскости, все попарные расстояния между элементами которого рациональны^[6].