Чарльз Петцольд - Читаем Тьюринга

со списком алгебраических чисел? Мы уже знаем, как пронумеровать алгебраические
числа, так что это не проблема. Построив диагональ и изменив все ее
цифры, мы получим число не из списка. Это значит, что полученное
число не алгебраическое. Оно – трансцендентное.
По-разному упорядочивая список алгебраических чисел и устанавливая разные правила выделения в нем уникальной диагонали, мы
каждый раз будем получать еще одно трансцендентное число.
Для обозначения мощности множества натуральных чисел (и, следовательно, всякого перечислимого бесконечного множества) Кантор в 1895 году выбрал первую букву еврейского алфавита с нулевым
нижним индексом – ‫אּ‬0 (произносится как «алеф нуль»). Кантор назвал его первым трансфинитным числом. Он объединил его с другими трансфинитными числами (‫אּ‬1, ‫אּ‬2, ‫אּ‬3 и т. д.), чтобы создать целостную трансфинитную математику.
Если мощность перечислимых множеств – ‫אּ‬0, то какова мощность
неперечислимого множества вещественных чисел? Можно ли хотя
бы представить такую мощность?
Можно. Давайте начнем с примера конечных множеств. Вот множество всего из трех элементов:
{a, b, c}.

48  Часть I. Основы
Сколько всего подмножеств у этого множества? (Множество всех
подмножеств множества называется степенью множества.) Попробуем сделать это вручную, не забывая только о пустом множестве и
самом множестве из трех элементов:
{}
{a}
{b}
{c}

{a, b}
{a, c}
{b, c}
{a, b, c}

У множества из трех элементов – восемь подмножеств, и не случайно:
23 = 8.
Показатель степени – число элементов исходного множества. Результат – число подмножеств этого множества. Множество из 4 элементов имеет 16, или 24, подмножеств. У множества из 5 элементов –
32 подмножества.
Существует более систематический способ подсчета этих подмножеств, который лучше раскрывает данное соотношение. Давайте составим таблицу, столбцы которой – это 3 элемента исходного множества, а цифры 0 и 1 в столбцах – признак вхождения этого элемента
в подмножество:
a
0
0
0
0
1
1
1
1

b
0
0
1
1
0
0
1
1

c
0
1
0
1
0
1
0
1

Подмножество
{}
{c}
{b}
{b, c}
{a}
{a, c}
{a, b}
{a, b, c}

Наборы из 0 и 1 в трех первых столбцах – это те же двоичные числа
от 0 до 7. Три бита порождают 8 двоичных чисел, а общее правило:
Мощность степени множества = 2мощность исходного множества.
Степень множества из 10 элементов состоит из 1024 элементов.
Степень множества из 100 элементов состоит из 1 267 650 600 228 22
9 401 496 703 205 376 элементов.

Глава 2. Иррациональные и трансцендентные числа 

49

Теперь рассмотрим натуральный ряд, включающий для этой цели
также 0:
{0, 1, 2, 3, 4, 5,…}.
Мощность этого множества – ‫אּ‬0. Сколько у него подмножеств?
Иными словами, какова мощность его степени? По аналогии она
должна быть
2‫אּ‬0.
Наверное, нужны дополнительные разъяснения. Давайте построим таблицу, как для конечного множества (но, конечно, не такую полную). Над столбцами – все элементы множества натуральных чисел.
В столбце – признак (0 или 1) вхождения натурального числа в конкретное подмножество, указанное справа:
0
0
1
0
1
0
1
0
1
…

1
0
0
1
1
0
0
1
1
…

2
0
0
0
0
1
1
1
1
…

3
0
0
0
0
0
0
0
0
…

4
0
0
0
0
0
0
0
0
…

5
0
0
0
0
0
0
0
0
…

…
…
…
…
…
…
…
…
…
…

Подмножество
{}
{0}
{1}
{0, 1}
{2}
{0, 2}
{1, 2}
{0, 1, 2}
…

То, чего мы, в сущности, добиваемся, – это список всевозможных бесконечных комбинаций из 0 и 1. Давайте поместим десятичную запятую (и нуль. – прим. перев.) перед каждой цепочкой цифр
списка:
0,000000…
0,100000…
0,010000…
0,110000…
0,001000…
0,101000…
0,011000…
0,111000…
…

50  Часть I. Основы
Тогда все они – двоичные числа в диапазоне от 0 до 1, причем (судя
по способу их создания) все двоичные числа от 0 до 1 и, следовательно, все вещественные числа от 0 до 11. Ранее было показано, что вещественные числа из диапазона от 0 до 1 могут быть поставлены
в соответствие всем вещественным числам, что означает, что вещественные числа могут быть поставлены в соответствие элементам степени множества натуральных чисел. Поэтому эта степень множества
имеет ту же мощность, что континуум.
Таким образом, мощность континуума
2‫אּ‬0,
где ‫אּ‬0 – мощность множества натуральных чисел.
Кантор доказал, что невозможно установить --">