Логика от А до Г

18

П. Халмои

Логика от А до Г

Описание механического помещника математика
с вольными замечаниями математика-исследователья

Чем является и чем не является логика

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

Перевод с английского Л. Савиной статьи из Mathematics Magazine, т. 50 (1977), № 1, с. 5—11.

Нормальный, здоровый человек владает всем «законами мышления», которые когда-либо были изобретены, и нет ничего такого, чем логики могли бы его научить по части мышления и способов избегать ошибок. Это не означает, что человек знает, как он думает, и это не означает, что он никогда не делает ошибок. То же самое относится к органам движения, с которыхрождается все нормальные, здоровые люди. Я не знаю, как я хочу, но я делаю это. Иногда я спотыкаюсь. Законы ходьбы могли бы представлять интерес для физологов и физков, а все, что хочу я, — это продолжать ходить.

Предмет математической логики, который является темой этой статьи, не претендует на открытие законов мышления и обучение им. Этот пред-

Аксиломы
Грамматика

20

вым анализом важнейших слов все и некоторые. (Между прочим, мы сейчас достигли начала алфавита: буква А в названия «Логика от А до Γ» обозначает, конечно, Аристотеля.) Для них использовются следующие сокращения: ∀ и ∃. Чтобы проиллюстрировать использование этих символов, рассмотрим предложение «Кто заколебался, тот пропал»*. На педагогном математическом языке это может быть сказано следующим образом: «Для всех X, если X заколебется, то X пропал». Используя K(X) и Π(X) в качестве сокращений для «X заколебется» и «X пропал», мы можем написать (∀ X) (K(X) ⇒ Π(X)).

Если мы сомневаемся в этом утверждении, то есть если мы склонны верить, что в полне возможно колебание без последующей гибели, мы можем выразить наш скептицзм в виде (∃ X) (K(X) & (∏ Π(X)).

И, наконец, Фреге и много кванторов
Важной частью аристотелевских сокращений является использование дополнительных символов, подобных вышеприведному символу X. Такие символы в языке логики играют местоимений. Вспомните, что в вышеприведном примере X занало место слова «он». Символы, используемые таким образом, называются индивидальным переменными. Следующей исторической фигурой, заслуживающей упоминания, является человек, который первым решился их использовать. Его имя Фреге, и он тоже жил в XIX веке. Сегодня мы ценим его за то, что именно он подчерknул: одна переменная, то есть одно местоимение, — список убогий инструкмент для большинства научных и математических целей. Например, если мы хотим выразить очень скромное утверждение, что имеет больше чем два числа, то есть что существует по крайней мере три различных числа, мы можем сделать это следующим образом:

(∀ X) (∃ X’) (∃ X’’) (∃ X’’’) (∃ X’’’’)
(X = (X’ × X’) + ((X’’ × X’’’) +

• ((X’’’’ × X’’’’’) + (X’’’’’ × X’’’’’’)))).

На самом деле, можно навести некоторую экономию; некоторые символы можно легко и естественно

*) Буквалный перевод английского варианта нашей поговорки «Промедление смерти подобно». (Прим. пер.)

Совершенно очевидно, что для этой целли нужны по крайней мере три переменные. Чтобы сказать, что имеется больше чем десять чисел, нужно по крайней мере одиннадцать переменных. Чтобы продолжать любое нетривиальное количество расчетов, нужно (по крайней мере потенциально) бесконечный запас переменных. Эффективный способ создания такой запас (обычно алфавиты имеют слишком конечное число букв) состоит в том, чтобы использовать одну букву, скажем X, и один дополнительный символ, скажем штириx. И затем использовать в роли переменных символы
X, X’, X’’’, X’’’’’, X’’’’’,…

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

Сколько символов?
Оказывается, очень большая математика, а именно все аргументы, может быть выражена с помощью символов, которые я перечислил до сих пор. Например, знаменитая теорема Эйлера*): каждое целое положительное число есть сумма четырех квадратов — может быть записана следующим образом:
(∀ X) (∃ X’) (∃ X’’) (∃ X’’’) (∃ X’’’’)
(X = (X’ × X’) + ((X’’ × X’’’) +

• ((X’’’’ × X’’’’’) + (X’’’’’ × X’’’’’’)))).

На самом деле, можно навести некоторую экономию; некоторые символы можно легко и естественно

*) В русской математической литературе ее называют теоремой Лагранжа. (Прим. ред.)

21

определенть через другие. Наш список можно без труда уменьшить до джинны, а именно:

$$\& + \times 0 \exists X' = ()$$

Чтобы снова получить $V$, заметьте, что $P \vee Q$ есть не что иное, как $(\cap P \& \cap Q)$. Чтобы получить $\Rightarrow$, заметьте, что $P \Rightarrow Q$ есть то же самое, что и $(\vee X) P(X)$. Чтобы получить $\vee$, заметьте, что $(\exists X) (\cap P(X))$. Так, словами, высказывание «Все не навидят шпинат» означает то же самое, что отрицание того, что есть кто-то, кто его любит. В таких сокращениях есть неокоторое техническое премиущество в принципе, но нет смысла связать себя ими на практике. Всякий раз, когда удобно, я буду использовать $V$, $\Rightarrow$, и я даже буду использовать $Y, Z, U, V$ и т. п. в качестве переменных. Чтобы установить эти отклонения от наших правил, достаточно заменить $V$, $\Rightarrow$, $\vee$ и т. п. на их определения, а также заменить $Y, Z, U, V$ и т. п. на $X', X''', X''''$ и т. д.

Сделаем пару любопытных замечаний. Во-первых, все, что мы делаем для элементарной арифметики, с таким же успехом может быть сделано для всех существующих разделов математики. Технический аппарат, то есть символка и правила, управляющие его, даже не стали бы сложнее: единственная разница состоит в том, что нам пришлось бы думать немного больше. Но ясно, что это не желательно, поэтому я собираюсь ограничиться элементарной арифметкой. Во-вторых, в числе «двенадцать» нет ничего магического. Дюжина символов достаточно для арифметики и фактически для всей математики (хотя в этом случае мы, возможно, должны были бы найти другую дюжину). Более того, потравив незначительные условия, можно обойтись и более скупными средствами. Налучший возможный результат, на который вы могли надеться в самых фантастических местах, оказався верным, а именно, что достаточно даже двух символов*). Получить через другие. Наш список можно без труда уменьшить до джинны, а именно:

$$\& + \times 0 \exists X' = ()$$

Чтобы снова получить $V$, заметьте, что $P \vee Q$ есть не что иное, как $(\cap P \& \cap Q)$. Чтобы получить $\Rightarrow$, заметьте, что $P \Rightarrow Q$ есть то же самое, что и $(\vee X) P(X)$. Чтобы получить $\vee$, заметьте, что $(\exists X) (\cap P(X))$. Так, словами, высказывание «Все не навидят шпинат» означает то же самое, что отрицание того, что есть кто-то, кто его любит. В таких сокращениях есть неокоторое техническое премиущество в принципе, но нет смысла связать себя ими на практике. Всякий раз, когда удобно, я буду использовать $V$, $\Rightarrow$, и я даже буду использовать $Y, Z, U, V$ и т. п. в качестве переменных. Чтобы установить эти отклонения от наших правил, достаточно заменить $V$, $\Rightarrow$, $\vee$ и т. п. на их определения, а также заменить $Y, Z, U, V$ и т. п. на $X', X''', X''''$ и т. д.

Сделаем пару любопытных замечаний. Во-первых, все, что мы делаем для элементарной арифметики, с таким жеUCCESSION для всей математики (хотя в этом случае мы, возможно, должны были бы найти другую дюжину). Более того, потравив незначительные условия, можно обойтись и более скупными средствами. Налучший возможный результат, на котором вы могли надеться в самых фантастических местах, оказався верным, а именно, что достаточно заменить $V$, $\Rightarrow$, $\vee$ и т. п. на их определения, а также заменить $Y, Z, U, V$ и т. п. на $X', X''', X''''$ и т. д.

Механический математик

Давайте, теперь приступим к созданию механического математика, который положит конец всем математикам. Достоинства этой воображаемой машины чисто умозрительные; мы не утверждаем, что создание механического математика принесет какую-либо практическую выгоду. Он никогда не сможет заменить живого математика.

Начнем строить машину. Для этого нам понадобится лента для пшуших машинок, дожина клавишей (на каждом находится один из джинны основных символов) и потенциально бесконечно длиной рулон бумаги для печати. Идея машины состоит в том, что после нажатия пусковой кнопки машина должна печать все, что она когда-либо может напечать. Один из способов запрограммировать это такое: расположим джинну символов в произвольном порядке (назовем его алфавитным) и затем даим указание машине печать первые две надцать символов («букв») алфавита, потом печать 144 «слова» из двух букв, затем 1728 «слов» из трех букв и т. д. до бесконечности. Машина, сконструированная таким образом, напечатает много чепухи, например:

$$= = = ((0 + ')$$

и много лжи, например

$$(\exists X) ((0 \times X) = 1)$$

но она рано или поздно напечатает любое арифметическое утверждение.

Потребуем соблюдения грамматики

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

23

рых она обязана начинать. Будем называть эти предложения аксюмами. Я опять не указываю здесь точно, какие предложения должны быть аксюмами арфметики, но приведу несколько примеров. (Полное определение понятия «аксюма» в элементарной.arifметике не очень длинно или сложно. Просто здесь не время и не место вдаться в обсуждение технических частностей.) Ну, хорошо: машину можно было бы научить, что всякий раз, когда P и Q — предложения, тогда предложение

$$P \Rightarrow P \lor Q$$

должно печататься красной краской. Идея состоит в том, что каждое такое предложение нужно считать аксюмой. Аналогично, мы можем сказать, что если $P(X)$ и $Q(X)$ — фразы (содержание «висящее» местимение X, но никаких других), то предложение

$$(\exists X)(P(X) \lor Q(X)) \Rightarrow (\exists X)P(X) \lor (\exists X)Q(X)$$

должно печатся красным. Последний пример: такое предложение, как $(\forall X)(\forall Y)(X+Y=Y+X)$, (С)

может быть аксюмой элементарной.arifметики. (Пояснительные примеры: (A) Если погода теляя, то или солнце светит, или погода теляя, или же и то и другое вместе. (B) Если кто-то любит или шпинат или капусту, то или кто-то любит шпинат, или кто-то любит капусту. (C) $2+3=3+2$.

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

Запрограммируем процедуру

Выше я сказал, что никто не может доказать что-то из ничего, по этой причине я надело механического математика некоторыми исходными предложениями. Но также верно, что никто не может доказать что-то при помощи печатать предложения черным и красным, и если аксюмы были выбраны в соответствии с пожеланиями разумного существа, то предложения, напечатанные красным (аксюмы), будут верны. Тем не менее машина может печатать много ложных штуковин, и она все еще не имеет средства для создания новых правилных предложений из старых.

Теперь процесс обучения машины доступен этапа. На этом этапе машина должна научиться распознавать определенные комбинации предложений и за это вознаграждается тем, что ей разрешается использовать большее красной печатнойкраски. Общий список таких правил процедуры не длинный, список из двух примеров таких правил, который я собираюсь дать, даже еще короче. Возможное правило номер 1: если $P$ — красное предложение и если $P \Rightarrow Q$ — красное предложение, то печатей $Q$ красным. (Объяснение: если «Солнце светит» — аксюма или было уже доказано, так же как и высказывание «Если солнце светит, то погода теляя», тогда мы можем считать доказанным, что «Погода теляя».) Возможное правило номер 2: если неполная фраза $P(X)$, содержащая «висящее» местимение $X$ (и никаких других), такова, что предложение $P(0)$ — красное ($P(0)$ — предложение, полученное из $P(X)$ подстановкой 0 вместе $X$), то печатей предложение $(\exists X)P(X)$ красным. (Объяснение: если мы подставим 0 вместе $X$ в $(1+X)=1$, мы получим $(1+0=1)$. Если это предложение — аксюма или уже было доказано, то мы можем считать доказанным $(1+X=1$ для неокоторого $X$).)

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

24

тать теоремы, которые она может вывести из этих аспектов. Машина может делать это в некоторых систематическом порядке, скажем в алфавитном.

Наступил золотой век. Механический математик закончен. Нажмите кнопку и, откинулись на спинку стула, можете бездельничать. На ленте будут появляться одна за другой теоремы элементарной арифметики. Если подходить достаточно долго, то рано или поздно перед вашими глазами пройти все теоремы. Машина никакda не говорит непроведей и никакda не говорит непроведы. Вы будете считать, что машина несколько скучноваata, часто повторяет одно и то же, работает очень медленно с точки зрения человека. Но это не ее вина.

Есть ли противоречия?
Мы ввели в машину все, что мы сами, ее создали, знаем об элементарной арифметике. Внутренняя работа машины и есть элементарная арифметика. Теория такой машины, ее конструкция, ее структуры свойства является частью другой дисциплины, часто называемой metamатематикой (или, в нашем случае, метаариметикой). Следующий вопрос является типичным вопросом, задаваемым в метаматематике: «Напечатает ли машина когда-либо как предложение $P$, так и его отрицание $\neg P$?» Если бы она когда-либо сделала это, то мы бы, верятоно, выразили неудовольствие таким состоянием дел, сказав, что элементарная арифметика противоречива. К счастью, это не так: арифметика не противоречива. Доказательство этого зависит от очень утонченного, не элементарного изучения той машины, которую мы описали. Изучение является «незелементным» в нескольких смыслах этого слова. В самом томом техническом смысле дело в том, что доказательство того, что машина непротиворечива, не является одной из теорем, которое машина сама может доказать. Повторим это иначе: машина никакda не будет противоречить сама себе, но она не может доказать это.

Может ли все быть доказано?

Другим интересным вопросом метаматематики является следующий: «Является ли машина полной в том смысле, что она либо доказывает, либо проверяет каждое предложение элементарной арифметики?» В существии, я уже dal ответ на этот вопрос, но все-taki стоит его повторить. При создавшемся положении в каждой в каждой все то, что машина написает, она доказывает. Если я занитересован в каком-то конкретном арифметическом предложении, я могу написать это предложение на кусочке бумаги и затем после включения машины сравнить все последующей текст, печатающая машиной, с помощью заготовленным бланком. Если на бумаге утверждается $P$ и если на какой-то стадии машина также печатает $P$, то я удаляюсь с победой; мое утверждение $P$ доказано. Если на бумаге утверждается $P$, но на какой-то стадии машина печатает $\neg P$, то я удаляюсь с победом: мое $P$ провергнут. Однако нет ли здесь третий возможность? Не может ли так служить, что машина никакda не написает $P$, а также никакda не написает $\neg P$? Не может ли так служить, что машина никакda не разрешит спора между $P$ и $\neg P$? На самом деле может, и тем самым доступили конца нашего анализа арифметической машины, что существует утверждения (и таких много), которые машина никакda не разрешит. Это доказательство является оно дает полную инструкцию для записи не-