2. Свойства счетных множеств
1. Всякое подмножество счетного множества конечно или счетно.
Доказательство. Пусть А – счетное множество и B А. Поскольку А счетно, то занумеруем его элементы и построим из них последовательность
a1, a2, a3, . . .
Из этой последовательности выделим все элементы, принадлежащие множеству B, т.е. рассмотрим подпоследовательность
Возможны следующие случаи:
1) Множество B конечно – тогда теорема верна.
2) Множество B бесконечно. Поскольку элементы множества B занумерованы, то в этом случае оно является счетным, что и требовалось доказать.
2. Объединение любого конечного или счетного множества счетных множеств снова является счетным.
Доказательство. Пусть множества А1, A2, . . . , Аn, . . . – счетные. Если их число не более, чем счетно, то множества можно занумеровать и расположить принадлежащие им элементы в таблицу
А1 = {a11, a12, a13, . . .}
А2 = {a21, a22, a23, . . .}
А3 = {a31, a32, a33, . . .}
. . . . . . . . . . . . . . . . .
Пусть
B
=
.
Построим последовательность подобно
тому, как это было сделано при доказательстве
счетности Q.
b1 = a11, b2 = a12, b3 = a21, b4 = a31, b5 = a22, . . . (1)
Если множества Аi попарно пересекаются (Аi Аj ), то в последовательность (1) не включаются те элементы, которые уже занумерованы. Таким образом, построено взаимно однозначное соответствие между множествами B и N. Следовательно, множество B счетно.
3. Всякое бесконечное множество содержит счетное подмножество.
Доказательство. Пусть М – произвольное бесконечное множество. Выберем в нем произвольный первый элемент и обозначим его a1 , затем – элемент a2 и т.д. Получаем последовательность a1, a2, . . . , которая не может оборваться на каком-то элементе, т.к. М бесконечно. Следовательно, данная последовательность образует счетное подмножество множества М.
Доказанная теорема позволяет утверждать, что среди бесконечных множеств счетное множество является самым "маленьким".
Если множество конечно или счетно то говорят, что оно не более, чем счетно. Такое множество называют ещё дискретным.
3. Примеры несчетных множеств
Рассмотренные примеры и свойства могут создать впечатление, что все бесконечные множества счетны. Однако, это далеко не так, и для доказательства этого достаточно построить контрпример, т.е. предъявить бесконечное множество, не являющееся счетным.
Теорема 2.1. Множество всех бесконечных бинарных последовательностей, т.е. состоящих из 0 и 1, несчетно.
Доказательство. Предположим противное, т.е. что эти последовательности можно занумеровать. Пусть P1, P2, . . . – последовательности, где
P1 = {a11, a12, a13, . . .}, P2 = {a21, a22, a23, . . .}
и т.д., где аij = 0 или аij = 1.
Построим последовательность P, не содержащуюся в этом списке. Такая последовательность существует, например, P ={1– a11, 1–a22, 1–a33, . . .}. Очевидно, что ее элементы равны 0 или 1, причем она не равна никакой другой последовательности из списка, потому что отличается от P1 по крайней мере первым элементом, от P2 – по крайней мере вторым и т.д. Таким образом, построенная последовательность отличается от любой из занумерованных последовательностей хотя бы одним элементом. Следовательно, множество всех бинарных последовательностей занумеровать невозможно, а это означает, что оно несчетно.
Другим важным примером бесконечного несчетного множества является множество вещественных (действительных) чисел R.
Перечислим основные свойства действительных чисел.
1. Любое вещественное число можно представить конечной или бесконечной десятичной дробью. И обратно, для любой десятичной дроби существует вещественное число, которое она представляет.
2. Множество вещественных чисел является непрерывным, т.е. оно сплошь заполняет числовую ось.
Задание. Доказать, что множество вещественных чисел несчетно. Указание: воспользоваться способом доказательства несчетности множества бинарных последовательностей.