Если знаковая система (естественный язык, формальная логика) достаточно продвинута, то она найдет способ построить суждения, которые утверждают или отрицают нечто о самих себе. Следовательно, если знаковая система достаточно продвинута, то в ней неизбежны парадоксы (не путать с противоречиями). В этом и состоит смысл парадокса лжеца и теоремы Гёделя. Парадокс лжеца, показывает, что естественный язык – достаточно продвинутая знаковая система. Теорема Гёделя показывает, что уже формальная арифметика является такой продвинутой системой.

Я конечно, загнул, что умещусь в несколько строк. Итак.

Формальная арифметика

Чтобы рассуждать о том и сем, обычно достаточно естественного языка. В крайнем случае – математических формул плюс естественного языка. Но чтобы строго рассуждать о наших рассуждениях, этого оказывается недостаточно. Рассуждения, чтобы стать объектом строгого исследования, должны объективироваться, например, их можно формализовать. Математические рассуждения формализовать проще всего.

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

В дальнейшем изложении формализованную аксиоматическую теорию арифметики мы будем называть ФАТА. Теорема Гёделя – она про ФАТА.

В ФАТА имеется одна константа – 0 (ноль), одна операция – x’, что означает следующее за x или x+1, и одно отношение = (равенство двух целых чисел). Все остальные операции, свойства и отношения – сложение, умножение, степень, сравнение на больше/меньше, четное, нечетное и т.д. – сводятся к первым трем.

Среди аксиом имеются такие, как:

если x = y, то y = x
если x’ = y’, то x = y
0 ≠ x’

и другие в том же роде. Но самое главное – принцип математической индукции. Вооружившись таким мощным оружием ФАТА, как кажется, может доказать все.

Идея Гёделя состоит в следующем: а что если попытаться сформулировать аналог парадокса лжеца в рамках ФАТА и посмотреть, что получится. Однако, сразу же  возникает одна трудность: как может арифметическое суждение высказываться о самом себе, если оно вообще не высказывается о суждениях, а лишь о целых числам? Типа “это число четно” или “это число больше того”.

Шаг 1. Арифметизация

Оказывается, эта трудность довольно легко обходится, если вы используете достаточно продвинутый язык. Можно по форме говорить как будто о числах, а по существу – о чем-то совсем другом. Поясню простым примером.

В сериале “Теория большого взрыва” Пенни приходит к Шелдону Куперу за советом – продолжать ли ей работать представителем фармацевтической компании или еще раз попытаться построить карьеру актрисы. Шелдон категорически отказывается разговаривать с Пенни на эту тему. Он согласен говорить только о поездах. Тогда Пенни прибегает хитрости. Она спрашивает: “Если бы я стояла на вокзале, откуда один поезд вез бы меня к моей работе, а второй на кинопробы, на какой из них мне следовало бы сесть?”

В этом состоит первый шаг в доказательства теоремы Гёделя. Мы перенумеруем все возможные суждения ФАТА (т.е. присвоим им числовые коды), и если мы хотим высказать нечто об арифметическом суждении, мы будет высказываться о номере (коде) этого суждения. Например, “суждение с номером n является непосредственным следствием суждения с номером m”. Этот прием называется арифметизация: мы заменяем некие объекты целыми числами, а свойства объектов и отношения между объектами – свойствами и отношениями целых чисел. Кроме того мы, перенумеруем все последовательности суждений, а тем самым и все возможные доказательства, поскольку доказательство – это последовательность суждений, в которой… и т.д.

Шаг 2. Самоприменимость

Теперь, когда мы арифметизировали ФАТА, мы можем, наконец, применить ФАТА к самой ФАТА.

Рассмотрим какое-нибудь суждение о целом числе x. Например, x – четное число. Согласно идее арифметизации, данное суждение имеет номер – код. Путь, к примеру, этот код – 153728. Применим теперь наше суждение к коду самого суждения. “153728 – четное число”. Очевидно, это суждение истинно. Т.е. в данном примере суждение “x – четное число” самоприменимо – будучи применено к своему собственному номеру, оно оказалось истинным. Ясно, что любое суждение о целом числе является либо самоприменимым, либо нет.

Нас, однако, не устраивает такая трактовка самоприменимости – через истинность. Истинность нельзя выразить в ФАТА. Поэтому нам придется заменить истинность на доказуемость в ФАТА. В этом новом варианте самоприменимости через доказуемость – суждение самоприменимо , если будучи применено к своему номеру оно доказуемо, и несамоприменимо в противоположном случае. В частности, суждение “153728 – четно число” доказуемо в ФАТА, а потому суждение “x – четное число” ­– самоприменимо и в новом смысле.

Шаг 3. Самоприменимость несамоприменимости

Свойство самоприменимости и несамоприменимости суждений само оказывается выразимым в ФАФА. Знаток парадоксов лжеца и ему подобных сам мог бы попытаться выстроить цепочку дальнейших рассуждений.

Итак, у нас есть суждение “n – несамоприменимо”. Смысл его состоит в том, что если n – код суждения P(x) , то P(n) – недоказуемо.

Спрашивается самоприменима ли несамоприменимость? Ясно, что нет. Если бы она была самоприменима, то можно было бы доказать её несамоприменимость.

Итак, несамоприменимость несамоприменима. Но доказать это в рамках ФАТА невозможно, иначе она была бы самоприменима. Следовательно, ФАТА неполна. В ней есть истинные (с точки зрения математики), но не доказуемые (в рамках ФАТА) положения. Или, чтобы совсем избежать слова “истина”, в ней есть такие суждения, что недоказуемы ни сами эти суждения, ни их отрицания. В частности, суждение о самоприменимости несамоприменимости.