В соответствии с теоремой Кантора из п. 4.1, множество всех подмножеств натурального ряда имеет мощность большую, чем ℵ0, и, значит, не является счетным. Мы воспроизведем доказательство (с небольшими модификациями) для этого случая, чтобы подчеркнуть лежащую в основе доказательства важную идею диагонализации.
Сопоставим каждому множеству A⊂Nего характеристическую последовательность из нулей и единиц
α0, α1, α2, …
так, что αi=1, если i∈A, и αi=0, если i∉A. Всякая последовательность из нулей и единиц является характеристической для множества, элементы которого – номера мест, содержащих единицы. Таким образом между последовательностями из нулей и единиц и подмножествами множества Nустанавливается взаимно однозначное соответствие. Пусть A0, A1, A2, … – произвольный список подмножеств множества N. Покажем, что в Nнайдется подмножество, не попавшее в этот список. Рассмотрим список множеств A0, A1, A2, … вместе с их характеристическими последовательностями:
A0 = α00, α01, α02, α03, … ;
A1 = α10, α11, α12, α13, … ;
A2 = α20, α21, α22, α23, … ;
A3 = α30, α31, α32, α33, … ;
…………………………….
Составим «антидиагональную» последовательность
1−α00, 1−α11, 1−α22, 1−α33, … .
Эта последовательность отличается, по крайней мере, первым элементом от первой последовательности списка, вторым элементом – от второй, третьим элементом – от третьей, и т.д. Следовательно, «антидиагональная» последовательность, а вместе с ней и соответствующее ей множество, не содержатся в списке. Приведенное рассуждение показывает, что невозможно составить список, включающий все подмножества множества N, и, значит, множество всех подмножеств множества Nне является счетным.
Используя диагональный метод, покажем, что множество действительных чисел отрезка [0;1] не является счетным.
Доказательство. Всякое действительное число a из отрезка [0;1] может быть записано в виде бесконечной десятичной дроби
a = 0,α0α1α2… .
Для чисел, представимых конечными десятичными дробями, такая запись неоднозначна. Например, записи 0,1000… и 0,0999… представляют одно и то же число. Условимся не использовать записи второго вида, в которых, начиная с некоторого места, идут одни девятки. Тогда представление чисел десятичными дробями окажется однозначным. Пусть a0, a1, a2, … – произвольный список действительных чисел из отрезка [0;1]. Покажем, что на отрезке [0;1] найдется число, не попавшее в этот список. Рассмотрим список чисел a0, a1, a2, … вместе с их десятичными представлениями:
a0 = 0,α00α01α02α03… ;
a1 = 0,α10α11α12α13… ;
a2 = 0,α20α21α22α23… ;
a3 = 0,α30α31α32α33… ;
………………………
Положим βi=1, если, αi,i=2, и βi=2, если, αii≠2. Число
β = 0,β0β1β2β3… .
лежит на отрезке [0;1] и отличается, по крайней мере, первой цифрой после запятой от первого числа из списка, второй цифрой – от второго числа, третьей цифрой – от третьего и т.д. Следовательно, число β не содержится в списке. Таким образом, невозможно составить список, включающий все числа отрезка [0;1], и, значит, множество всех действительных чисел отрезка [0;1] несчетно.
Мощность множества чисел отрезка [0;1] называется континуум; множества, имеющие ту же мощность, называются континуальными. Континуальными являются: множество всех действительных чисел, множество точек прямой, множество точек плоскости, множество последовательностей действительных чисел и многие другие множества, встречающиеся в математической практике.
Проблема существования несчетных множеств, меньших по мощности, чем континуум (так называемая континуум-гипотеза), возникла в тории множеств практически с момента появления этой теории. Гедель доказал, что предположение об отрицательном решении континуум-гипотезы не противоречит аксиоматике теории множеств. Позднее Коэн установил, что этой аксиоматике не противоречит и предположение о положительном решении континуум-гипотезы. Наличие в теории множеств проблемы, которая, казалось бы, должна иметь решение типа «да» или «нет», но не имеет такового, в значительной степени стимулировало ту формализацию математики, о которой говорилось в предыдущей лекции.
