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

1. Ситуация изменится, как только мы начнем говорить не о целых числах, а о разных размерах бесконечности. Там формулирование аксиом и разбор следствий из них — это практически все наши инструменты!

2. Как только мы все формализовали, можно запрограммировать компьютер и заставить его думать за нас:

предположение 1: для любого x если A (x) истинно, то B (x) истинно;

предположение 2: существует x такой, что A (x) истинно;

вывод: существует x такой, что B (x) истинно.

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

3. Помимо того что доказательства для нас будет искать компьютер, мы сможем работать с этими доказательствами как с математическими объектами, что откроет путь к мета-математике.

В общем, хватит ходить вокруг да около. Посмотрим кое-какие аксиомы теории множеств. Я сформулирую их на обычном языке; перевод на язык логики первого порядка в большинстве случаев достается читателю в качестве упражнения.

Аксиомы теории множеств

В этих аксиомах фигурирует совокупность объектов, называемых «множествами», и отношения между множествами, которые характеризуются словами «является элементом», «содержится в» или «принадлежит к» и записываются с использованием символа ∈. Любая операция с множествами в конечном итоге определяется в терминах отношения принадлежности.

• Пустое множество: существует пустое множество, то есть множество x, для которого не существует такого y, что y ∈ x.

• Аксиома объемности: если в два множества входят одни и те же члены, то эти множества равны. То есть для любых x и y если (z ∈ x тогда и только тогда, когда z ∈ y для любого z), то x = y.

• Аксиома пары: для любых множеств x и y существует множество z = {x, y}, то есть множество z, такое, что для любого w w ∈ z тогда и только тогда, когда (w = x или w = y).

• Аксиома суммы: для любых множеств x существует множество, равное объединению всех множеств, содержащихся в x.

• Аксиома бесконечности: существует множество x, содержащее пустое множество и содержащее также {y} для любого y ∈ x. (Почему в этом x должно содержаться бесконечное число элементов?)

• Аксиома степени (множество всех подмножеств): для любого множества x существует множество, состоящее из всех подмножеств x.

• Аксиома замены (на самом деле бесконечное число аксиом, по одной для каждой функции A, устанавливающей соответствие одних множеств другим): для любого множества x существует множество z = {A(y) | y ∈ x}, которое образуется в результате применения A ко всем элементам x. (Технически следовало бы определить также, что подразумевается под «функцией, устанавливающей соответствие одних множеств другим»; сделать это можно, но я не буду здесь этим заниматься.)

• Фундирование (аксиома регулярности): в любом непустом множестве x имеется элемент y, такой, что для любого z либо z ∉ x, либо z ∉ y. (Это техническая аксиома, смысл которой в том, чтобы исключить такие множества, как {{{{…}}}}.)

Эти аксиомы, известные как аксиомы Цермело — Френкеля, служат фундаментом практически для всей математики. Поэтому я решил, что вам стоит посмотреть на них хотя бы раз в жизни.

Ну хорошо, один из самых базовых вопросов, которые мы можем задать о множестве, звучит так: насколько оно велико? Каков его размер, его мощность? В смысле, сколько в нем элементов? Вы можете сказать, что это просто: достаточно пересчитать элементы. Но что, если их бесконечно много? Скажите, целых чисел больше, чем нечетных целых чисел? Это приводит нас к Георгу Кантору (1845–1918) и первому из нескольких его громадных вкладов в копилку человеческого знания. Он сказал, что два множества равны по мощности тогда и только тогда, когда их элементы можно поставить в строгое соответствие попарно, то есть один к одному. И точка. А если, как бы вы ни пытались распределить элементы по парам, в одном из множеств все равно остаются лишние, значит, то множество, где остаются лишние элементы, большее из двух.

Какой может быть мощность множества, или, иначе, его кардинальное число? Разумеется, существуют множества конечной мощности, по одному на каждое натуральное число. Затем идет первая бесконечная мощность, мощность множества целых чисел, которую Кантор назвал ℵ0 («алеф-нуль»). Множество рациональных чисел обладает той же мощностью ℵ0; иначе этот факт можно выразить, сказав, что рациональные числа являются счетными — в том смысле, что их можно поставить в попарное соответствие с целыми числами. Иными словами, мы можем составить бесконечный список таким образом, что рано или поздно в нем появится каждое рациональное число.

Как доказывается, что множество рациональных чисел счетно? Вы никогда не видели этого доказательства? Ну хорошо. Для начала запишем 0 и добавим все рациональные числа, у которых сумма абсолютных значений числителя и знаменателя равна 2. Затем добавляем к списку все рациональные числа, у которых сумма абсолютных значений числителя и знаменателя равно 3. И так далее. Ясно, что любое рациональное число рано или поздно появится в этом списке. Следовательно, их бесконечное количество счетно. Что и требовалось доказать.

Но самый серьезный вклад Кантора заключался в том, что он показал, что не каждая бесконечность является счетной, — так что, к примеру, бесконечность действительных чисел больше, чем бесконечность целых чисел. В более общем плане: точно так же, как существует бесконечно много чисел, существует и бесконечно много бесконечностей.

С доказательством этого вы тоже не встречались? Ну хорошо, хорошо. Пусть у вас имеется бесконечное множество A. Мы покажем, как получить другое бесконечное множество B, которое будет больше, чем A. Просто возьмем в качестве множества B множество всех подмножеств A, которое гарантированно существует, согласно аксиоме о степенном множестве. Откуда мы знаем, что 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, и мы получили бесконечность большую, чем та, с