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

а) из "Р" всегда выводится "не-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 является членом самого себя. Парадокс Рассела на самом деле демонстрирует: существует такое высказывание, что и оно, и его отрицание доказуемы на основе аксиом Фреге. Другими словами, как уже говорилось, это демонстрирует противоречивость аксиом Фреге.

Как-то раз, читая лекцию для широкой публики, Бертран Рассел упомянул, что если множество аксиом противоречиво, то любое утверждение доказуемо на их основе. Рассел объявил об этом в семантическом виде, говоря, что исходя из ложной предпосылки можно доказать любую вещь. Аудитория сразу же предложила ученому доказать, что Смит (один из слушателей) является Папой Римским, исходя из ложной предпосылки о том, что 1 = 0. Рассел рассуждал так: если 1 = 0, то при прибавлении 1 к обоим членам мы делаем вывод, что 2 = 1. Теперь подумаем о множестве, образованном Смитом и Папой. У этого множества два члена, но так как 2 = 1, то мы можем сказать, что у множества только один член. То есть Смит и Папа — это одно и то же лицо.

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

Тогда мы можем утверждать, что любое противоречивое множество аксиом является полным, поскольку при любом высказывании Р как Р, так и не-Р доказуемы. Но речь идет о тривиальной полноте, которая не дает никакой информации, поскольку абсолютно все доказуемо, даже те высказывания, которые противоречат сами себе, например "для любого х справедливо то, что х отличается сам от себя".

Более интересно рассмотреть множество аксиом, являющееся одновременно полным и непротиворечивым. Множество аксиом с такой характеристикой приблизилось бы к выполнению цели программы Гильберта. Действительно, если система непротиворечива, то ее высказывания истинны в каком-нибудь мире, а если она полна, то все истины, относящиеся к этому миру, доказуемы (см. схему).

Но в программе Гильберта искали аксиомы для арифметики, а не произвольного мира. Есть ли какой-нибудь синтаксический способ сформулировать эту цель? Да, такой способ есть.

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