Квантовые вычисления со времен Демокрита
Шрифт:
Правила логики первого порядка
Все правила здесь говорят о том, как составлять предложения, чтобы они были корректны – что, говоря по-простому, означает «тавтологически истинны» (верны для всех возможных подстановок переменных) [11] , но что мы пока можем представить просто как комбинаторное свойство определенных символьных строк. Я буду печатать логические предложения другим шрифтом, чтобы их было легко отличить от окружающего текста.
11
Упрощая, автор использует далее как
• Пропозициональные тавтологии: 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, то сколько ни
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.