Для наших целей будет достаточно считать, что язык задан полностью своим алфавитом L и множеством истинных утверждений Т - подмножеством множества L?. Мы будем называть любую такую пару фундаментальной парой языка.
1.2. "Недоказуемые"
"Недоказуемые" значит не имеющие доказательства.
Доказательство
Несмотря на то что термин "доказательство" является, возможно, одним из важнейших в математике (Бурбаки начинают свою книгу "Основания математики" словами: "Со времени древних греков сказать "математика" значило то же, что сказать "доказательство""), он не имеет своей точной дефиниции. В целом, понятие доказательства со всеми его смысловыми ответвлениями относится, скорей, к области психологии, нежели к математике. Но как бы то ни было, доказательство - это просто аргумент, который мы сами находим вполне убедительным для того, чтобы убедить всех остальных.
1.3.1.
Будучи записано, доказательство становится словом в некотором алфавите Р, так же как любой английский текст является словом алфавита L, пример которого был приведен выше. Множество всех доказательств образуют подмножество (и довольно-таки обширное подмножество) множества Р?. Мы не будем пытаться дать точное определение этой одновременно "наивной" и "абсолютной" концепции доказательства, или - что равносильно - дать определение соответствующему подмножеству Р?. Вместо этого мы рассмотрим формальный аналог этого смутного понятия, для обозначения которого в дальнейшем мы все же будем пользоваться термином "доказательство". Этот аналог имеет две весьма важные особенности, кои отличают его от интуитивного понятия (хотя интуитивная идея доказательства все же отражает в некоторой степени эти особенности). Прежде всего мы допустим, что существуют разные концепции доказательства, то есть - допустимы разные подмножества доказательств в Р?, и даже больше того: мы, на деле, будем допускать, что сам алфавит доказательств Р может изменяться. Далее мы потребуем, чтобы для каждой такой концепции доказательства существовал эффективный метод, другими словами, алгоритм, который бы с необходимостью определял, является ли данное слово алфавита Р доказательством или нет. Мы также предположим, что существует алгоритм, с помощью которого всегда можно определить, какое именно утверждение доказывает данное доказательство. (Во многих ситуациях доказываемым утверждением просто является последнее утверждение в последовательности шагов, образующих доказательство.)
1.3.2.
Таким образом, наша окончательная формулировка определения выглядит следующим образом:
(1) У нас имеются алфавит L (алфавит языка) и алфавит Р (алфавит доказательства).
(2) Нам дано множество Р, являющееся подмножеством Р?, и чьи элементы называются "доказательствами". В дальнейшем мы будем предполагать, что также у нас имеется алгоритм, который позволяет нам определить является ли произвольное слово алфавита Р элементом множества Р, то есть доказательством, или нет.
(3) Также у нас есть функция? (для нахождения того, что именно было доказано), чья область определения? удовлетворяет условию Р???Р?, и чья область значений находится в Р?. Мы предполагаем, что у нас есть алгоритм, который вычисляет эту функцию (точное значение слов "алгоритм вычисляет функцию" следующее: значения функции получаются при помощи этого алгоритма - набора специальных правил преобразования). Мы будем говорить, что элемент р? Р есть доказательство слова?(р) алфавита L.
1.3.3.
Тройка <Р, Р,?>, удовлетворяющая условиям (1)-(3) называется дедуктивной системой над алфавитом L.
1.3.4.
Для читателя, знакомого с обычным способом определения "доказательства" в терминах "аксиома" и "правило вывода", мы сейчас поясним, как этот метод может рассматриваться в качестве специального случая определения, данного в параграфе 1.3.2. То есть - доказательство обычно определяется как последовательность таких выражений языка, каждое из которых является либо аксиомой, либо ранее полученным из уже существующих утверждений при помощи одного из правил вывода. Если мы добавим новое слово * к алфавиту нашего языка, то мы сможем записать такое доказательство в виде слова составленного при помощи полученного в результате такой модификации алфавита: последовательность выражений становится словом C1*C2*...*Cn. В таком случае, функция, определяющая, что именно было доказано, своим значением имеет часть этого слова, стоящую сразу за последней в последовательности буквой *. Алгоритм, существование которого требуется в части 1.3.2. определения, может легко быть сконструирован, как только мы точно определим какое-либо из принятых значений слов "аксиома" и "правила вывода".
1.4.Попытки точной формулировки теоремы о неполноте
1.4.1. Первая попытка
"При определенных условиях для фундаментальной пары языка алфавита L и дедуктивной системы <Р, Р,?> над L - всегда существует слово в Т, не имеющее доказательства". Этот вариант все еще выглядит смутным. В частности, мы могли бы запросто придумать сколько угодно дедуктивных систем, имеющих очень немного доказуемых слов. Например, в пустой дедуктивной системе (где Р =?) совсем нет слов, у которых были бы доказательства.
1.4.2. Вторая попытка
Есть другой, более естественный подход. Предположим, нам задан язык - в том смысле, что нам задана фундаментальная пара этого языка. Теперь мы будем искать такую дедуктивную систему над L (интуитивно, мы ищем технику доказательства), при помощи которой мы могли бы доказать как можно больше слов из Т, в пределе все слова из Т. Теорема Геделя описывает ситуацию, в которой такая дедуктивная система (посредством коей, каждое слово в Т было бы доказуемо) не существует. Таким образом, нам бы хотелось сформулировать следующее утверждение:
"При определенных условиях относительно фундаментальной пары не существует такой дедуктивной системы, в которой бы каждое слово из Т имело бы доказательство".
Однако такое утверждение, очевидно, ложно, так как необходимо лишь взять такую дедуктивную систему, в которой Р = L, Р = Р? и?(р) = р для всех р из Р?; тогда каждое слово из L? является тривиально доказуемым. Следовательно, нам нужно принять некоторое ограничение на то, какими дедуктивными системами мы пользуемся.
1.5. Непротиворечивость
Было бы вполне естественно потребовать, что только "истинные утверждения", то есть только слова из Т, могут быть доказаны. Мы будем говорить, что дедуктивная система <Р, Р,?> является непротиворечивой относительно фундаментальной пары, если?(Р)?Т. Во всех последующих рассуждениях нас будут интересовать только такие непротиворечивые дедуктивные системы. Если же нам задан язык, то было бы чрезвычайно соблазнительно найти такую непротиворечивую дедуктивную систему, в которой каждое истинное утверждение имело бы доказательство. Интересующий нас вариант теоремы Геделя в точности утверждает, что при определенных условиях относительно фундаментальной пары, невозможно найти такую дедуктивную систему.
1.6. Полнота
Говорится, что дедуктивная система <Р,Р,?> полна относительно фундаментальной пары, при условии если?(Р)?Т. Тогда наша формулировка теоремы о неполноте приобретает следующий вид:
При определенных условиях относительно фундаментальной пары, не существует такой дедуктивной системы <Р,Р,?> над L, которая была бы одновременно полна и непротиворечива относительно.