2. Множества
Здесь мы будем говорить о множествах. Что будут содержать эти множества? Другие множества! Как куча картонных коробок, открыв которые, обнаруживаешь внутри только новыекартонные коробки, и так далее, до самого дна.
Вы можете спросить: «Какое отношение все это имеет к книге о квантовых вычислениях?»
Ну, будем надеяться, что кое-какие ответы на этот вопрос мы увидим чуть позже. Пока же достаточно сказать, что математика есть основа всякой человеческой мысли, а теория множеств — счетных, несчетных и др. — основа математики. Так что неважно, о чем у нас книга, в любом случае множества — прекрасная тема для начала.
Мне, вероятно, следует без обиняков сказать вам, что я собираюсь втиснуть весь курс математики в эту одну главу. С одной стороны, это означает, что я не рассчитываю всерьез, что вы все поймете. С другой стороны, в той мере, в какой поймете, — замечательно! Вы получаете целый курс математики в одной главе! Добро пожаловать.
Итак, начнем с пустого множества и посмотрим, как далеко нам удастся пройти.
Пустое множество
Вопросы есть?
На самом деле, прежде чем говорить о множествах, нам необходимо обзавестись языком для разговора о множествах. Язык, который придумали для этого Фреге, Рассел и другие, называется логикой первого порядка. Он включает в себя булевы функции (и, или, не), знак равенства, скобки, переменные, предикаты, кванторы («существует» и «для любого»[10]) — и, пожалуй, все. Говорят, что физики испытывают со всем этим сложности… Эй, потише, я просто пошутил. Если вы прежде не встречались с таким способом мышления, значит, не встречались, ничего страшного в этом нет. Но давайте все же пойдем навстречу физикам и пробежимся по основным правилам логики.
Правила логики первого порядка
Все правила здесь говорят о том, как составлять предложения, чтобы они были корректны — что, говоря по-простому, означает «тавтологически истинны» (верны для всех возможных подстановок переменных)[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. Как только мы все формализовали, можно запрограммировать компьютер и заставить его думать за нас:
o предположение 1: для любого x если A (x) истинно, то B (x) истинно;
o предположение 2: существует x такой, что A (x) истинно;
o вывод: существует x такой, что B (x) истинно.
В общем, идею вы поняли. Суть в том, что вывод из предположений извлекается посредством чисто синтаксической операции и не требует понимания того, что, собственно, означают все эти высказывания.
3. Помимо того что доказательства для нас будет искать компьютер, мы сможем работать с этими доказательствами как с математическими объектами, что откроет путь