Квантовые вычисления со времен Демокрита - Скотт Ааронсон

Это определенно одно из четырех или пяти величайших доказательств во всей математике — и опять же полезно посмотреть на него хотя бы раз в жизни.

Помимо кардинальных чисел полезно обсудить также ординальные, или порядковые, числа. Их, вместо того чтобы определять, проще проиллюстрировать. Начнем с натуральных чисел:

0, 1, 2, 3, …

Затем, говорим мы, определим нечто, что будет больше любого натурального числа:

ω.

Что идет после ω?

ω + 1, ω + 2, …

Далее, что идет после всего этого?

2ω.

Так, мы ухватили идею:

3ω, 4ω, …

Так, мы ухватили идею:

ω², ω³, …

Так, мы ухватили идею:

ωω, ωωω, …

В таком духе мы могли бы продолжать довольно долго! По существу, для любого множества ординальных чисел (конечного или бесконечного) мы уславливаемся, что существует некоторое первое ординальное число, которое стоит после всего, что содержится в этом множестве.

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

А теперь кое-что интересное. Все ординальные числа, которые я перечислил, обладают одним особым свойством: они имеют не более счетного количества (то есть не более ℵ0) предшественников. Что, если рассмотреть множество всех ординальных чисел с не более чем счетным числом предшественников? Ну, у такого множества тоже имеется следующий элемент, назовем его α. Но сколько предшественников у α, тоже ℵ0? Разумеется, нет, поскольку в противном случае α не был бы следующим элементом по отношению к нашему множеству, а входил бы в это множество! Множественно предшествующих α элементов обладает следующей возможной мощностью, которая называется ℵ1.

Такого рода рассуждения доказывают, что множество мощностей само по себе является вполне упорядоченным. После бесконечности целых существует «следующая по возрастанию бесконечность», а также «следующая за ней по возрастанию бесконечность» и т. п. Однако невозможно увидеть бесконечную уменьшающуюся последовательность бесконечностей, какую можно получить в случае действительных чисел.

Таким образом, начиная с ℵ0 (мощность множества целых чисел), мы уже видели два разных способа получить «большие бесконечности, чем бесконечность». Один из этих способов выдает мощность множества множеств целых чисел (или, что то же самое, мощность множества действительных чисел), которую мы обозначаем 2ℵ₀. Другой способ выдает ℵ1. Можно ли сказать, что 2ℵ0 равно ℵ1? Или скажем иначе: существует ли бесконечность промежуточного размера между бесконечностью целых чисел и бесконечностью действительных чисел?

Этот вопрос стоял первым в списке задач Давида Гильберта, предложенных им в 1900 г. Более полувека он оставался одной из великих нерешенных математических задач, пока не получил «решения» (оказавшегося несколько обескураживающим, как вы увидите).

Сам Кантор считал, что промежуточных бесконечностей не существует, и называл это утверждение континуум-гипотезой. Кантор очень сердился на себя за то, что никак не мог ее доказать.

Кроме континуум-гипотезы, существует еще одно утверждение касательно бесконечных множеств, которое никто не мог доказать или опровергнуть, исходя из аксиом Цермело — Френкеля. Это утверждение — печально известная аксиома выбора, в которой говорится, что если у вас имеется (возможно, бесконечное) множество множеств, то можно сформировать новое множество, взяв по одному элементу из каждого множества. Звучит разумно, не правда ли? Вот только если вы принимаете это утверждение, то вам придется признать также, что существует способ разрезать шар на конечное число кусочков, а затем собрать из этих же кусочков новый шар в тысячу раз большего размера. (Это «Парадокс Банаха — Тарского». Следует признать, что отрезать такие «части» ножом довольно проблематично…)

Но почему аксиома выбора приводит к таким драматическим последствиям? В основном потому, что утверждает, что некоторые множества существуют, но не дает никакого правила по формированию этих множеств. Как сказал по этому поводу Бертран Рассел, «чтобы взять по одному носку от каждой из бесконечного числа пар носков, требуется аксиома выбора, а для ботинок такой аксиомы не требуется». (Какая разница?)

Оказывается, аксиома выбора эквивалентна утверждению о том, что любое множество может быть вполне упорядоченным: иными словами, элементы любого множество можно попарно поставить в соответствие порядковым числам 0, 1, 2, …, ω, ω + 1, …, 2ω, 3ω, … вплоть до некоторого порядкового числа. Если подумать, к примеру, о множестве действительных чисел, это представляется далеко не очевидным.

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

Хотите убедиться в обратном? Почему аксиома выбора подразумевает, что любое множество можно полностью упорядочить? Да?

Хорошо! У нас имеется множество A, которое мы хотим полностью упорядочить. К каждому собственному[12] подмножеству B ⊂ A мы применим аксиому выбора, чтобы выбрать элемент f(B) ∈ A — B (где A — B означает множество всех элементов A, которые не являются также элементами B). Теперь мы можем начать упорядочение A так: пусть s0 = f({}), далее пусть s1 = f({s0}), s2 = f({s1}) и т. п.

Может ли этот процесс продолжаться до бесконечности? Нет, не может. Потому что если бы он продолжался