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

до бесконечности, то посредством так называемой «трансфинитной индукции» мы могли бы запихнуть в A произвольно большие бесконечные кардинальные числа. А множество A хотя и бесконечно, но имеет не более чем фиксированный бесконечный размер! Так что процесс этот должен где-то остановиться. Но где? На некотором собственном подмножестве B множества A? Нет, это тоже невозможно, поскольку если бы это было так, то мы просто продолжили бы процесс добавлением f(B). Так что единственное место, где он может остановиться, это само A. Следовательно, A может быть полностью упорядочено.

Ранее я упоминал некие математические сложности, изначально присущие континууму, и есть у меня одна головоломка, некоторым образом связанная с ними.

Вы ведь знаете действительную числовую прямую? Пусть нам нужно объединение открытых отрезков, или интервалов (возможно, бесконечного их числа), которое перекрывает все рациональные точки. Вопрос: обязательно ли сумма длин таких интервалов должна быть бесконечной? Казалось бы, это совершенно естественно, это первое, что приходит в голову! В конце концов, рациональные числа у нас всюду!

На самом деле сумма длин таких интервалов может быть не просто конечной, она может быть сколь угодно близкой к нулю! Просто пронумеруем рациональные числа: r0, r1, r2, и т. п. Затем для каждого i окружим каждое из чисел ri интервалом протяженностью ε/2i.

А вот задачка посложнее: мы хотим иметь подмножество S точек (x, y) в единичном квадрате [0, 1]², такое, что для любого действительного числа x ∈ [0, 1] существует лишь счетное количество значений y из [0, 1], таких, что (x, y) попадает в S. Можно ли выбрать S так, что для любого (x, y) ∈ [0, 1]², или (x, y) ∈ S, или (y, x) ∈ S?

Я дам вам два ответа: что такое невозможно и что такое все же возможно.

Начнем с того, почему такое невозможно. Для этого я предположу, что континуум-гипотеза ошибочна. Далее, существует некоторое собственное подмножество A ⊂ [0, 1] мощностью ℵ1. Пусть B — множество всех y, которые фигурируют в точках (x, y) ∈ S на всех x ∈ A. Поскольку для любого x существует счетное количество таких y, мощность множества B также равна ℵ1. Поэтому, раз мы предположили, что ℵ1 меньше чем, 2ℵ₀ должно существовать некоторое y0 ∈ [0, 1], не входящее в B. Отметим, что существует ℵ1 действительных чисел x ∈ A, но ни одно из них не удовлетворяет условию (x, y0) ∈ S, и лишь ℵ0 < ℵ1 из них может удовлетворять условию (y0, x) ∈ S, так что существует некоторое x0, для которого (x0, y0) и (y0, x0) не входят в S.

А теперь посмотрим, почему это возможно. Для этого я хочу предположить, что и аксиома выбора, и континуум-гипотеза верны. Согласно континуум-гипотезе, в отрезке [0, 1] имеется только ℵ1 действительных чисел. Тогда, по аксиоме выбора, мы можем вполне упорядочить эти действительные числа и сделать это таким способом, чтобы каждое число имело не более ℵ0 предшественников. Далее, пусть (x, y) входит в S тогда и только тогда, когда y ≤ x, где ≤ означает сравнение по отношению к полной упорядоченности (а не к обычному порядку действительных чисел). Тогда для любого (x, y) ясно, что либо (x, y) ∈ S, либо (y, x) ∈ S.

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

3. Гёдель, Тьюринг и все-все-все

В предыдущей главе мы говорили о правилах логики первого порядка. Существует поразительная штука, известная как теорема Гёделя о полноте, в которой говорится, что, кроме этих правил, вам ничего и не нужно. Иными словами: если, отталкиваясь от некоторого набора аксиом, вы не можете с использованием этих правил вывести никакого противоречия, то аксиомы эти должны иметь модель (то есть быть внутренне согласованными). И наоборот: если аксиомы несогласованны, то их несогласованность может быть доказана с использованием только этих правил.

Подумайте, что это означает. А означает это, что великую теорему Ферма, гипотезу Пуанкаре или любую другую математическую загадку, которая только придет вам в голову, можно доказать, начав с аксиом теории множеств, а затем применяя эти простенькие правила раз за разом, снова и снова. Вероятно, делать это придется 300 миллионов раз, но все же…

Как же Гёдель доказывает свою теорему о полноте? Доказательство описывают как «вывод семантики из синтаксиса». Мы просто придумываем объекты на заказ по мере того, как их требуют аксиомы! И если мы когда-нибудь наткнемся на несогласованность, то случиться это может лишь по одной причине: что несогласованность присутствовала и в первоначальных аксиомах.

Одним из немедленных следствий теоремы о полноте является теорема Лёвенгейма — Скулема: любой непротиворечивый набор аксиом имеет модель не более чем счетной мощности. (Заметим в скобках: если у вас в фамилии есть умляут, как у Лёвенгейма, — это одно из лучших предзнаменований успеха в математической логике.) Почему? Потому что процесс придумывания объектов, которые требуют аксиомы, может продолжаться даже если бесконечное, то все-таки счетное число шагов!

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

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

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

Но погодите! Разве теорема о неполноте не противоречит теореме о полноте, согласно которой, любое утверждение, которое следует из аксиом, может быть доказано исходя из этих аксиом? Придержите этот вопрос; мы проясним его чуть позже.

А сначала давайте посмотрим, как доказывается теорема о неполноте. Обычно говорят, что «доказательство теоремы о неполноте — это высший пилотаж математики, оно занимает 30 страниц и требует сложных построений с привлечением простых чисел», и т. п. Невероятно, но