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

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

Итак, начнем с пустого множества и посмотрим, как далеко нам удастся пройти.

Вопросы есть?

На самом деле, прежде чем говорить о множествах, нам необходимо обзавестись языком для разговора о множествах. Язык, который придумали для этого Фреге, Рассел и другие, называется логикой первого порядка . Он включает в себя булевы функции (и, или, не), знак равенства, скобки, переменные, предикаты, кванторы («существует» и «для любого» [10] У автора – «для всех» (for all). – Прим. пер. ) – и, пожалуй, все. Говорят, что физики испытывают со всем этим сложности… Эй, потише, я просто пошутил. Если вы прежде не встречались с таким способом мышления, значит, не встречались, ничего страшного в этом нет. Но давайте все же пойдем навстречу физикам и пробежимся по основным правилам логики.

Все правила здесь говорят о том, как составлять предложения, чтобы они были корректны – что, говоря по-простому, означает «тавтологически истинны» (верны для всех возможных подстановок переменных) [11] Упрощая, автор использует далее как синонимы слова valid, которое описывает корректность (выводимость) логической формулы, и true, характеризующее истинность конкретного высказывания. – Прим. пер. , но что мы пока можем представить просто как комбинаторное свойство определенных символьных строк. Я буду печатать логические предложения другим шрифтом, чтобы их было легко отличить от окружающего текста.

• Пропозициональные тавтологии:A или не A, не (A и не A) и т. п. – истинны.

• Modus ponens (правило отделения):если A истинно и из A следует B истинно, то B истинно.

• Правила равенства:высказывания x = x; из x = y следует y = x; если x = y и y = z, то x = z; и из x = y следует f (x) = f (y) – истинны.

• Замена переменных:при изменении имен переменных высказывание остается истинным.

• Исключение квантора:если для всех x A (x) истинно, то A (y) истинно для любого y.

• Добавление квантора:если истинно A (y), где y – переменная без ограничений, то для всех x, A (x) истинно.

• Правило квантификации:если не (для любого x, A (x)) истинно, то существует такой x, что не (A (x)) истинно.

Приведем в качестве примера аксиомы Пеано для неотрицательных целых чисел, записанные в терминах логики первого порядка. В них S ( x ) – это функция следования, интуитивно S ( x ) = x + 1, и я предполагаю, что функции определены заранее.

• Нуль существует:существует такое z , что для любого x, S ( x ) не равно z . (Это z принимается за 0.)

• Каждое целое число имеет не более одного предшественника:для любых x, y если S(x) = S(y), то x = y.

Сами неотрицательные целые числа называют моделью этих аксиом: в логике слово «модель» означает всего лишь любой набор объектов и функций этих объектов, удовлетворяющий условиям аксиом. Интересно, однако, что точно так же, как аксиомам теории групп удовлетворяет множество разных групп, так и неотрицательные целые числа – не единственная модель аксиом Пеано. К примеру, вы можете убедиться, что добавление к этой модели дополнительных искусственных целых чисел, недостижимых от 0, – чисел, лежащих «за бесконечностью», так сказать, – даст нам еще одну полноценную модель. При этом, как только вы добавите к модели одно такое целое число, вам придется добавить их бесконечно много, поскольку у каждого целого числа должно быть число, непосредственно за ним следующее.

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

Так вот, именно поэтому я и не считаю , что аксиомы и формальную логику можно использовать для подведения под арифметику более надежного фундамента. Если вы почему-то не согласны с тем, что 1 + 1 = 2, то сколько ни изучай математическую логику, понятнее это не станет! Тем не менее все эти штучки безумно интересны не менее чем по трем причинам.