Сон разума. Математическая логика и ее парадоксы

Фресан Хавьер

* * *

НЕПРИБЫЛЬНАЯ МАТЕМАТИКА

Ключевой труд Рассела и Уайтхеда был опубликован издательством Cambridge University Press. Издательство смогло выделить на публикацию всего 300 фунтов, что составляло половину необходимой суммы. Недостающие 300 фунтов обязалось внести Лондонское королевское общество, членом которого был Рассел, однако в итоге было внесено лишь 200, а остаток Расселу и Уайтхеду пришлось заплатить из своего кармана. «Неплохой баланс, — шутил Рассел впоследствии, — за десять лет работы мы заработали минус пятьдесят фунтов на каждого».

* * *

В упрощенной версии формальная система арифметики, предложенная Расселом и Уайтхедом в «Началах математики», состояла из следующих основных символов: 0 (число ноль), s (функция следования), ¬ (отрицание), V (дизъюнкция «или»), 

(существование), = (равенство) и открывающая и закрывающая скобки. Позднее к этим символам были добавлены переменные х, у, z типа 0, которые обозначали натуральные числа, а также переменные А, В, С типа 1, то есть множества натуральных чисел, и т. д. по мере того, как требовались элементы все новых и новых типов. Возможно, внимательный читатель заметил отсутствие других символов,

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

. Мы действительно можем добавить к языку символ

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

можно выразить с помощью символов отрицания и существования.

Это же справедливо и для конъюнкции «и»: для ее обозначения существует символ

, однако он является избыточным, так как его можно заменить символами V и ¬. Чтобы доказать это, рассмотрим три операции теории множеств: дополнение, объединение и пересечение.

Для данного множества А, которое содержится в другом множестве В, дополнением множества А до В называют множество, состоящее из элементов, принадлежащих В, но не А. Например, дополнением множества гласных {а, е, i, о, и} английского алфавита является множество согласных. Рассмотрим операции объединения и пересечения. Для данных множеств X и Y их пересечение X 

 Y определяется как множество элементов, одновременно принадлежащих X и Y. Например, если X — множество четных чисел 0, 2, 4, 6, 8, 10…, а Y — множество чисел, кратных трем, 0, 3, 6, 9, 12, 15 …, то чтобы найти их пересечение, нужно определить их общие элементы: ими будут 0, 6, 12, 18…, то есть числа, кратные шести. Объединением множеств X U Y называется множество, которому принадлежат все элементы X и все элементы Y. В предыдущем примере первыми элементами объединения X и Y будут 0, 2, 3, 4, 6, 8, 9…

Похожесть символов, обозначающих пересечение двух множеств (

) и конъюнкцию двух высказываний (

), а также символов, обозначающих объединение двух множеств (U) и дизъюнкцию двух высказываний (V), вовсе не случайна. Если сопоставить свойствам Р и Q множества чисел, обладающих этими свойствами, например X и Y, то числа, обладающие свойствами Р и Q одновременно, будут элементами пересечения множеств X 

Y, а числа, обладающие свойством Р или Q, то есть как минимум одним из этих двух свойств, будут принадлежать объединению множеств X U Y. Дополнение множества, в свою очередь, соответствует отрицанию высказывания. Для представления дополнений, объединений и пересечений множеств очень удобно использовать диаграммы, созданные британским математиком и философом Джоном Венном в 1880 году. С их помощью можно доказать, что конъюнкция свойств Р и Q равносильна отрицанию дизъюнкции отрицаний Р и Q, иными словами, Р 

Q = ¬(¬Р V ¬Q). Это свойство позволяет выразить 

через V и ¬.

Рис. 1. Пересечение двух множеств, соответствующее конъюнкции P

 Q.

Рис. 2. Объединение двух множеств, соответствующее дизъюнкции Р V Q.

< image l:href="#"/>

Рис. 3. Дополнение множества, соответствующее отрицанию ¬Р.

Диаграммы Венна, на которых представлены операции пересечения (рис. 1), объединения (рис. 2) и дополнения (рис. 3) множеств.

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

и следующее за ним, которое будем обозначать через у. Вспомним, что число, следующее за данным, записывается с помощью буквы s, которая ставится перед этим числом, и выражается формулой у = sx, то есть «у равно числу, следующему за х». Следующий шаг заключается в том, что высказывание «каждое натуральное число» равносильно высказыванию «для всех натуральных чисел», и в этом контексте слово «имеет» означает «существует». Таким образом, аксиома принимает вид: «Для всякого натурального числа х существует натуральное число у такое, что у = sx». Если бы мы могли использовать символ

, то на этом можно было бы остановиться: аксиома записывалась бы как

x

y(y = sx) — скобки мы использовали, чтобы выделить свойство, которым обладают числа х и у. Так как этот символ применить нельзя, нужно выполнить еще одно действие: так как «для всякого натурального числа х существует натуральное число у такое, что у = sx» равносильно «не существует натурального числа х такого, что для него не существует натурального числа у такого, что у = sx», и вторая аксиома Пеано будет записываться так: ¬

х

у (у = sx). После столь подробных объяснений читатель может самостоятельно убедиться в том, что третья аксиома Пеано, «0 не следует ни за каким натуральным числом», соответствует выражению ¬

х (sx = 0).

* * *

ЧЕТВЕРТАЯ АКСИОМА ПЕАНО

Переведем в формальную систему арифметики четвертую аксиому Пеано, которая гласит: «за двумя различными натуральными числами следуют различные натуральные числа». Сначала определим переменные, используемые в высказывании: это два натуральных числа, х и у. Аксиома гласит, что не могут одновременно выполняться два следующих условия: х и у различны, следующие за ними числа совпадают. Иными словами, не существует чисел х и у таких, что:

1) х отличается от у;

2) число, следующее за х, равно числу, следующему за у.

Если бы символ конъюнкции был частью определенного нами языка, то эта аксиома записывалась бы так:

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

* * *

От языка — к метаязыку

Благодаря описанному выше процессу арифметика была очищена от значений и сведена к формальному каркасу. Теперь ее аксиомы являются исключительно последовательностями абстрактных символов, а доказательства превратились в упражнения по комбинаторике. Однако мы по-прежнему можем сформулировать высказывания со смыслом: например, мы можем сказать «вторая аксиома Пеано длиннее третьей», «квантор существования упоминается во второй аксиоме Пеано два раза» или «формула ¬(0 = 1) является теоремой арифметики». Важно, что здесь речь идет уже не о формализованных высказываниях языка L, а о фразах на русском языке, которые относятся к формулам L. В этих фразах говорится уже не о числах, а о высказываниях о числах, таким образом, они выходят за пределы математики в область метаматематики. Этот переход подобен ситуации, когда один из героев романа начинает писать свой роман. Подобно тому, как литература порой превращается в металитературу, математика может превратиться в метаматематику.

Одним из важнейших открытий Гильберта было проведение четкого различия между уровнями языка, к которым принадлежат различные высказывания. Представьте себе урок английского языка, на котором учитель по-русски объясняет тонкости значения какого-то слова. В этот момент используются два языка: английский, который изучают ученики, и русский, который они используют в качестве инструмента. Это же происходит и с фразой вида «формула ¬

х ¬

y (y = sx) длиннее, чем формула ¬

х (sx = 0)» — в ней сочетаются последовательности символов языка L и выражения «формула» и «длиннее», принадлежащие не к языку L, а к метаязыку, который мы используем, чтобы описать формальную систему, так сказать, извне. Термины «ноль», «следующее» и «равно» принадлежат к языку L, где они записываются как 0, s и = соответственно, однако слова «формула», «доказательство» и «истинный» принадлежат метаязыку и невыразимы на языке L.

Следовательно, при формализации арифметики все эти высказывания в рамках самой арифметики теряют смысл.

Но какое отношение все это имеет к парадоксам? Ведь целью программы Гильберта было избавить от них математику. Как мы отмечали в предыдущей главе, многие парадоксы связаны с самоотносимостью, которая вполне имеет право на существование в естественных языках, но нет никаких причин для того, чтобы она сохранялась в искусственных языках формальных систем. Когда мы озвучиваем парадокс Рассела на русском языке, нам кажется вполне логичным, что существует два класса множеств: одни принадлежат сами себе, другие — нет. Однако в формальной системе отношение принадлежности, примененное к двум переменным одного и того же типа, нарушает правила грамматики языка. Еще более интересным является парадокс лжеца: «эта фраза ложна». Чтобы эту фразу можно было рассматривать всерьез, формальная система должна не только допускать самоотносимость, но и содержать свойство «быть истинным», которое можно будет выразить средствами самого языка, а не только метаязыка. Гильберт ожидал, что эти две ситуации никогда не произойдут одновременно, если формализация арифметики будет проведена должным образом.