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

множестве. Откуда мы знаем, что B больше, чем A? Ну предположим, что мы смогли каждому элементу a ∈ A поставить во взаимно однозначное соответствие элемент f (a) ∈ B, так что лишних элементов B не осталось. Тогда мы можем определить новое подмножество S ⊆ A, состоящее из всех a, которые не входят в подмножество f (a). Такое S также является элементом B. Но, заметьте, S не может соответствовать никакому a ∈ A, поскольку в противном случае a содержалось бы в f (a) тогда и только тогда, когда оно не содержалось бы в f (a). Получили противоречие. Следовательно, B больше A, и мы получили бесконечность большую, чем та, с которой мы начали.

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

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

0, 1, 2, 3, …

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

ω.

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

ω + 1, ω + 2, …

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

2ω.

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

3ω, 4ω, …

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

ω², ω³, …

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

ω^ω, _ωω^ω, …

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

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

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

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