Множество P - положительных рациональных чисел (то есть дробей вида , где a и b - натуральные числа) - счетно.
Подчеркнем, что нумерация числового множества Р не имеет ничего общего с упорядочением элементов по величине. В множестве Р нет ни наименьшего элемента, ни двух соседних по величине элементов, однако есть элементы с наименьшим номером и с соседними номерами).
Утверждение 4:
Множество и вообще для любого натурального k - счетно.
Доказательство: аналогично (3).
Утверждение 5:
Объединение конечного числа счетных множеств - счетно, то есть счетно , где - конечное число.
Доказательство:
Перенумеруем сначала все первые элементы множеств, затем все вторые и т. д.
Утверждение 6:
Объединение счетного множества конечных множеств - счетно.
Доказательство:
Нумеруем сначала все элементы первого множества, затем все элементы второго и т. д., т. е. счетно , где - конечное число.
Следствие (из Утверждения 6):
Множество всех слов конечного алфавита - счетно.
А - алфавит, - множество всех слов, - конечное число.
|
|
Так как , то каждое из этих множеств имеет конечную мощность. Введем обозначение , тогда
,
то есть выполняется утверждение - счетное объединение конечных множеств - счетно. - объединение счетного числа множеств, так как между и множеством натуральных чисел можно установить взаимно однозначное соответствие.
Утверждение 7:
Объединение счетного множества счетных множеств - счетно, т. е. - счетное число и - счетное число.
Пример: Объединением счетного множества счетных множеств является, например, - множество всех векторов с натуральными компонентами.
- счетное множество, и для любого i - счетно.
Теорема Кантора:
Множество всех действительных чисел отрезка [0, 1] не является счетным.
Доказательство:
При доказательстве используется так называемый диагональный метод Кантора. Докажем от противного.
Пусть это множество точек отрезка счетно, и существует его нумерация (взаимно однозначное соответствие с N). Расположим все числа, изображенные бесконечными десятичными дробями в порядке этой нумерации.
Рассмотрим любую бесконечную десятичную дробь такую, что
Эта дробь не может войти в указанную последовательность, так как от первого числа она отличается первой цифрой, от второго - второй и т. д. Таким образом, все числа отрезка [0, 1] не могут быть пронумерованы, следовательно, множество всех действительных чисел отрезка [0, 1] несчетно.
Определение: Мощность несчетного множества называется континуум.
Континуальные множества - множества мощности континуум (то есть несчетные множества).
Следствие из теоремы Кантора:
|
|
Множество всех подмножеств счетного множества континуально.
Доказательство: - счетное множество. - некоторое его подмножество.
Воспользуемся, как в теореме о числе подмножеств конечного множества, представлением подмножества в виде последовательности (но теперь уже бесконечной!) нулей и единиц.
На i - месте последовательности стоит 1, если входит в данное подмножество.
На i - месте последовательности стоит 0, если не входит в данное подмножество. Получаем (соответствует), где следующим образом:
.
Причем, каждый такой вектор единственным образом соответствует десятичной дроби отрезка [0, 1] по принципу: если данную последовательность считать дробной частью двоичного представления числа, то найти его значение в десятичной системе счисления можно по формуле
0,101011...» ...
Это взаимно однозначное соответствие между подмножествами счетного множества А и правильными двоичными дробями , которые, в свою очередь, взаимно однозначно соответствуют континуальному множеству чисел отрезка [0, 1] приводит к выводу о том, что мощность множества V- есть континуум, а, значит, континуальным является и множество подмножеств счетного множества А.