У интуиции есть своя логика. Гёдель. Теоремы о неполноте.

Вспомним, что число (отличное от единицы) является простым, если делится только на единицу и само на себя. Можно выразить это понятие по-другому: 2 — простое число, поскольку единственный способ представить его в виде произведения двух чисел тривиален: 2 = 2 x 1 (запись 2 = 1 x 2 считается совпадающей с ней, так как в ней используются те же числа). А вот число 15 не является простым, поскольку его можно представить, помимо тривиального способа 15 = 1 х 15, также как 15 = = 3 x 5.

Но точно ли единственный способ записать число 2 в виде произведения — это 2 = 2 х 1? В мире натуральных чисел — да. Но существуют и другие миры.

Расширим наш числовой мир и включим в него все числа, которые получаются умножением √2 на натуральное число (и на нуль), а затем прибавлением другого натурального числа (или нуля). Например, этот мир содержит числа 3 + 4 √2 или 7 √2. Также в нем содержится само число √2, которое записывается как 0+1 √2, и все натуральные числа, которые могут быть записаны как:

1 = 1 + 0 √2

2 = 2 + 0 √2

3 = 3 + 0 √2.

Итак, в этом мире 2 — не простое число, поскольку может быть записано как 2 = √2 х √2. Высказывание "2 — простое число" верно среди натуральных чисел, но ложно в мире, который мы определили по-другому (см. схему).

Какова связь между непротиворечивостью и истинностью? Ответ дан теоремой Лёвенгейма — Скулема (доказанной в 1915 году Леопольдом Лёвенгеймом для частного случая и в 1920 году Туральфом Скулемом для общего случая): множество аксиом является непротиворечивым, если существует какой-нибудь мир, в котором все аксиомы являются истинными высказываниями. Следовательно, множество, образованное двумя аксиомами:

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

Для любого х справедливо, что х + 0 = х; 2 не является простым числом

Но можем ли мы принять "2 не является простым числом" за аксиому? Не должны ли аксиомы быть очевидными сами по себе? В чисто синтаксическом мире, в котором истинности и ложности не существует, нет смысла говорить об очевидных высказываниях. Любое из них может быть взято за аксиому. Почему основополагающей является непротиворечивость? Что произойдет, если множество аксиом будет противоречивым? С семантической точки зрения это означает, что нет ни одного возможного мира, в котором все высказывания одновременно истинны. Но у противоречивости системы аксиом есть и синтаксическое следствие, поскольку если множество аксиом противоречиво, то на его основе можно доказать любое высказывание.

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

а) из "Р" всегда выводится "не-Q => Р";

б) из "не-Q => Р" выводится "не-Р => Q";

в) из "Р" и "Р ^ Q" выводится "Q" (это правило вывода, modus ponens).

Заметим, что все они сформулированы синтаксически и апеллируют к форме высказываний, а не к их значению. Предположим, как мы сказали, что Р и не-Р доказуемы. Получается следующее.

1. Р доказуемо, по гипотезе.

2. Выводится, что "не-<2=" Р" доказуемо, по правилу "а".

3. Следовательно, "не-Р=> Q" доказуемо, по правилу "б".

4. Не-P доказуемо, по гипотезе.

5. Из не-Р (пункт 4) и "не-Р =" Q" (пункт 3), по правилу вывода, выводится Q.

6. Следовательно, Q доказуемо.

Поскольку Q было произвольным высказыванием, можно сделать вывод, что любое высказывание доказуемо на основе аксиом. То есть любое высказывание доказуемо на основе противоречивого множества аксиом.

Заметим, что проделанные нами рассуждения чисто синтаксические и не затрагивают ни значения Р или Q, ни таких семантических понятий, как "истинно" или "ложно". Мы основывались только на синтаксических правилах логики и на виде высказываний. Таким типом аргументов Гёдель воспользовался для изложения доказательства своей теоремы.

Бертран Рассел в своем парадоксе на самом деле показал, что система аксиом, которую предложил Фреге, противоречива. Рассмотрим эту идею более подробно. Вспомним, что Рассел определил множество R, образованное всеми множествами, не являющимися членами самих себя.

Если R является членом самого себя, то выводится, что оно им не является. Это противоречие, которое возникает от предположения, что R — член самого себя, дает основание допустить: R не является членом самого себя. Но если предположить это, то логическим путем можно прийти к выводу, что все-таки является. Тогда получается, что R является членом самого себя. Парадокс Рассела на самом деле демонстрирует: существует такое высказывание, что и оно, и его отрицание доказуемы на основе аксиом Фреге. Другими словами, как уже говорилось, это демонстрирует противоречивость аксиом Фреге.

ПРИМЕР РАССЕЛА