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

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

Теорема 2.1. Множество всех бесконечных бинарных последовательностей, т.е. состоящих из 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₂ – по крайней мере вторым и т.д. Таким образом, построенная последовательность отличается от любой из занумерованных последовательностей хотя бы одним элементом. Следовательно, множество всех бинарных последовательностей занумеровать невозможно, а это означает, что оно несчетно.

Другим важным примером бесконечного несчетного множества является множество вещественных (действительных) чисел R.

Перечислим основные свойства действительных чисел.

1. Любое вещественное число можно представить конечной или бесконечной десятичной дробью. И обратно, для любой десятичной дроби существует вещественное число, которое она представляет.

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

Задание. Доказать, что множество вещественных чисел несчетно. Указание: воспользоваться способом доказательства несчетности множества бинарных последовательностей.