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

взаимно-однозначное
соответствие между элементами любого непустого множества и элементами его степени, что очевидно для конечных множеств, но не так
очевидно для бесконечных. Теперь этот факт известен как теорема
Кантора, и он был главным результатом его статьи 1891 года, в которой предложен метод диагонализации. Как и то, что множество может
иметь степень множества, a степень множества – свою собственную
степень множества и т. д. Все эти множества имеют разные мощности.
Кантор выяснил, что мощность континуума – это следующее за ‫אּ‬0
трансфинитное число, которое он назвал ‫אּ‬1. Это предположение называют континуум-гипотезой Кантора, и оно может быть выражено
математически так:

‫אּ‬1 = 2‫ אּ‬.
0

Кантор изо всех сил пытался доказать свою гипотезу, но так никогда и не смог этого сделать. Проблема заключалась в том, что между ‫אּ‬0
и мощностью континуума могло быть какое-то другое трансфинитное число2.
1

2

Может также показаться, что мы наткнулись на метод перечисления всех
вещественных чисел от 0 до 1. Закономерность уже понятна – первая цифра после запятой меняется с 0 на 1, вторая цифра меняется со скоростью,
вдвое меньшей, и т. д. – и мы могли бы легко продолжать этот список настолько долго, насколько пожелаем. Однако ошибка в том, что список никогда не будет содержать трансцендентное число. Каждое число в списке
имеет конечное число ненулевых цифр после запятой.
Существование множества этой промежуточной мощности – это так называмая континуум-гипотеза – первая из 23 проблем Гильберта, о которых
он доложил на II Математическом конгрессе в 1900 году. В 1940 году Гёдель
доказал, что отрицание континуум-гипотезы недоказуемо, а в 1963 году
Коэн доказал недоказуемость континуум-гипотезы. – прим. перев.

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

51

Несмотря ни на что, глубокий смысл всего этого состоит в том, что
мощность перечислимых множеств не просто меньше мощности континуума

‫אּ‬0 < 2‫ אּ‬,
0

а много, много, много, много, много меньше:

‫אּ‬0 --">