Коллектив авторов - Теорема Геделя о неполноте [Фейк]

Далее, нам необходимо уточнить к какого рода формальным системам приложима теорема Геделя. Это так называемые "исчисления" или "дедуктивные системы". По существу, это ничто иное, как формализованные описания тех или иных дедуктивных математических теорий (например, формализованной арифметики, геометрии и т.п.).

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

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

Далее из множества выражений выделяют подмножество формул. Содержательно формулы - это выражения, которые что-то утверждают (например, утверждают нечто о свойствах чисел или геометрических фигур). Формулы также определяются индуктивно.

Далее выделяют множество замкнутых формул или выражений. Это формулы, которые не имеют свободных параметров (т.е. параметров, которые могут принимать различные значения и не связаны кванторами всеобщности или существования). Это такие формулы, которым можно приписать определенное значение "истина" или "ложь". Обозначим множество замкнутых формул данного языка символом Б*.

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

Всякое формализованное доказательство - это некоторое слово формального языка, представляющее собой цепочку формул, в которой каждая формула - это либо аксиома, либо получена их аксиом посредством применения тех или иных правил вывода. Последняя формула в цепочке - это и есть доказанное утверждение (теорема). Обозначим множество всех доказательств символом D*, а множество всех доказанных формул Иd*. Через И* - обозначим множество содержательно истинных замкнутых формул данного языка.

Теорема Геделя о неполноте формальных систем утверждает, что для любой достаточно выразительно богатой формальной системы выполняется условие И* > Иd* и, следовательно, существует истинная недоказуемая формула. Это верно при условии, что заданная дедуктика непротиворечива, т.е. не позволяет одновременно доказывать некоторое утверждение и его отрицание.

Итак, теорема Геделя утверждает, что для любого достаточно выразительно богатого языка и для любой непротиворечивой дедуктики, заданной на этом языке, множество истинных формул всегда больше множества доказуемых формул. Это весьма нетривиальный вывод.

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

Каким же образом доказывается теорема Геделя? Мы рассмотрим здесь лишь общую схему доказательства (12).

Идея доказательства заключается в том, чтобы построить пример формулы, которая была бы недоказуема и, вместе с тем, содержательно истинна. Таковой являлась бы формула, содержательный смысл которой заключается в том, что она утверждает свою собственную недоказуемость, т.е. невыводимость из аксиом рассматриваемой формальной системы.