5. Свойства счетных множеств

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

ДОКАЗАТЕЛЬСТВО. Пусть А– счетное множество и BА. Поскольку А счетно, то занумеруем его элементы и построим из них последовательность

a₁, a₂, a₃, . . .

Из этой последовательности выделим все элементы, принадлежащие множеству B, т.е. рассмотрим последовательность

a_n1, a_n2, a_n3, . . .

Возможны следующие случаи:

1) множество B конечно;

2) множество B бесконечно.

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

2. Объединение любого конечного или счетного множества счетных множеств снова является счетным.

ДОКАЗАТЕЛЬСТВО. Пусть множества А₁, A₂, . . . , А_n, . . . – счетные. Если их число не более, чем счетно, то множества можно занумеровать и расположить принадлежащие им элементы в таблицу

А₁={a₁₁, a₁₂, a₁₃, . . .}

А₂={a₂₁, a₂₂, a₂₃, . . .}

А₃={a₃₁, a₃₂, a₃₃, . . .}

. . . . . . . . . . . . . . . . .

Пусть B=. Построим последовательность подобно тому, как это было сделано в п. 4 при доказательстве счетностиQ.

b₁ = a₁₁, b₂ = a₁₂, b₃ = a₂₁, b₄ = a₃₁, b₅ = a₂₂, . . . (1)

Если множества А_i попарно пересекаются (А_i А_j  ), то в последовательность (1) не включаются те элементы, которые уже занумерованы. Таким образом, построено взаимно однозначное соответствие между множествами B и N. Следовательно, множество B счетно.

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

ДОКАЗАТЕЛЬСТВО. Пусть М – произвольное бесконечное множество. Выберем в нем произвольный первый элемент и обозначим его a₁ , затем – элемент a₂ и т.д. Получаем последовательность a₁, a₂, . . . , которая не может оборваться на каком-то элементе, так как М бесконечно. Следовательно, данная после-

довательность образует счетное подмножество множества М.

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

Если множество конечно или счетно то говорят, что оно не более, чем счетно.

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

ТЕОРЕМА. Множество всех бесконечных бинарных последовательностей, т.е. состоящих из 0 и 1, несчетно.

ДОКАЗАТЕЛЬСТВО. Предположим противное, т.е. что эти последовательности можно занумеровать. Пусть P₁, P₂, . . . – последовательности, где P₁ = {a₁₁, a₁₂, a₁₃, . . .}, P₂ = {a₂₁, a₂₂, a₂₃, . . .} и т.д., где а_ij = 0 или а_ij = 1.

Построим последовательность P, не содержащуюся в этом списке. Такая последовательность существует, например, P ={1– – a₁₁, 1–a₂₂, 1–a₃₃, . . .}. Очевидно, что ее элементы равны  0 или 1, причем она не равна никакой другой из списка, потому что отличается от последовательности P₁ по крайней мере первым элементом, от P₂ – по крайней мере вторым и т.д. Таким образом, построенная последовательность отличается от любой из занумерованных последовательностей хотя бы одним элементом. Следовательно, множество всех бинарных последовательностей занумеровать невозможно, а это означает, что оно несчетно.