122

множеств. Аналогично устанавливается счетность любого конечного семейства счетных множеств.

6. Пусть L = {a,b, …, } счетный алфавит. Тогда множество слов над алфавитом L (то есть конечных упорядоченных наборов символов алфавита) счетно.

Доказательство. Множество n-буквенных слов можно естественным образом отождествить с Ln, счетность которого следует из утверждения 5. Теперь достаточно сослаться на утверждение 4: множество всех слов представляет собой объединение счетного семейства счетных множеств: слов из одной буквы; слов из двух букв, и т. д.

4.3.Диагональный метод Кантора

Всоответствии с теоремой Кантора из п. 4.1, множество всех подмножеств натурального ряда имеет мощность большую, чем 0, и, значит, не является счетным. Мы воспроизведем доказательство (с небольшими модификациями) для этого случая, чтобы подчеркнуть лежащую в основе доказательства важную идею диагонализации.

Сопоставим каждому множеству A N его характеристическую последовательность из нулей и единиц

α0, α1, α2, …

так, что αi=1, если i A, и αi=0, если i A. Всякая последовательность из нулей и единиц является

123

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

Эта последовательность отличается, по крайней мере, первым элементом от первой последовательности списка, вторым элементом – от второй, третьим элементом – от третьей, и т.д. Следовательно, «антидиагональная» последовательность,

авместе с ней и соответствующее ей множество, не содержатся

всписке. Приведенное рассуждение показывает, что невозможно составить список, включающий все подмножества

124

множества 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… ;

………………………

125

Положим βi=1, если, αi,i=2, и βi=2, если, αii≠2. Число

β = 0,β0β1β2β3… .

лежит на отрезке [0;1] и отличается, по крайней мере, первой цифрой после запятой от первого числа из списка, второй цифрой – от второго числа, третьей цифрой – от третьего и т.д.

Следовательно, число β не содержится в списке. Таким образом, невозможно составить список, включающий все числа отрезка [0;1], и, значит, множество всех действительных чисел отрезка [0;1] несчетно.

Мощность множества чисел отрезка [0;1] называется континуум; множества, имеющие ту же мощность, называются континуальными. Континуальными являются: множество всех действительных чисел, множество точек прямой, множество точек плоскости, множество последовательностей действительных чисел и многие другие множества, встречающиеся в математической практике.

Проблема существования несчетных множеств, меньших по мощности, чем континуум (так называемая континуумгипотеза), возникла в тории множеств практически с момента появления этой теории. Гедель доказал, что предположение об отрицательном решении континуум-гипотезы не противоречит аксиоматике теории множеств. Позднее Коэн установил, что этой аксиоматике не противоречит и предположение о положительном решении континуум-гипотезы. Наличие в теории множеств проблемы, которая, казалось бы, должна