У интуиции есть своя логика. Гёдель. Теоремы о неполноте - [29]
Например, следующие финитные высказывания
"2 + 3 = 5"
"3 х 7 = 21"
"45 делится на 9"
"2 — простое число"
истинны (во всех этих случаях мы рассматриваем мир натуральных чисел), а "2 х 3 = 10" — финитное и ложное. Высказывание "Любое четное число, большее 2, является суммой двух простых чисел" не является финитным, поскольку предполагает бесконечное число случаев. Действительно, это равносильно "4 — сумма двух простых чисел, и 6 — сумма двух простых чисел, и 8 — сумма двух простых чисел (и так далее)".
Заметим, что "36 — сумма двух простых чисел" является финитным высказыванием. Действительно, если 36 — сумма двух простых чисел, то они обязательно меньше 36. Существует всего 11 простых чисел, меньших 36 (это 2,3,5, 7,11,13,17,19, 23, 29, 31), и 55 пар, которые из них можно образовать. Чтобы посмотреть, истинно ли высказывание, достаточно проверить одну за другой эти 55 пар и убедиться, даст ли какая-нибудь в сумме 36. Высказывание истинно, поскольку 36 = 5 + 31.
Напротив, для высказывания "43 является суммой или разностью трех последовательных простых чисел" тот факт, что мы говорим о сумме или разности, предполагает: задействованные простые числа могут быть настолько большими, насколько мы захотим. Поиск простых чисел потенциально бесконечен, поэтому высказывание не финитное.
Утверждение о том, что любое четное число является суммой двух простых, известно как гипотеза Гольдбаха. Он сформулировал ее в 1742 году в письме знаменитому швейцарскому математику Леонарду Эйлеру (1707-1783).
До сих пор неизвестно, верна ли эта гипотеза. Она выполняется для большого числа четных чисел, но до сих пор никто не нашел доказательства для всех возможных случаев, так же как и не нашли примера, при котором гипотеза была бы ложной.
Итак, если мы предложим множество аксиом арифметики, то наименьшее, чего мы можем от него требовать — это способности доказать все финитные истинные высказывания. Следует заметить: во всем, что мы только что сказали, слово "истинное" связано с финитными высказываниями. В этом ограниченном контексте "истинное" и "ложное" становятся синтаксическими условиями, поскольку они проверяются механически за конечное число шагов. С точки зрения синтаксиса программа Гильберта предполагала нахождение непротиворечивого и полного множества аксиом арифметики, которое было бы способно доказать все финитные истинные высказывания. В первой теореме Гёделя о неполноте доказывается как раз то, что эта цель недостижима.
Так мы дошли до синтаксической формулировки первой теоремы Гёделя о неполноте:
если множество арифметических аксиом непротиворечиво и позволяет доказать все финитные истинные высказывания, то оно неполное, то есть существует такое высказывание G, что ни Gy ни не-G (ни одно из двух) недоказуемо. (Мы все время помним, что допускаются только доказательства, проверяемые алгоритмически.)
В этой версии теоремы появляются только синтаксические понятия ("непротиворечивый", "неполный", "высказывание" и "доказуемый"). Понятие "истинность" связано с финитными высказываниями, то есть появляется в более ограниченной, синтаксической версии.
Эту синтаксическую формулировку Гёдель представил в своей статье 1931 года, и синтаксическими также были аргументы, которые он использовал для доказательства. Далее вспомним рассмотренное в предыдущей главе доказательство и посмотрим, как его можно реализовать на основе исключительно синтаксических аргументов.
— Шаг 1. Предположим, что у нас есть непротиворечивое множество арифметических аксиом, позволяющих доказать все финитные истинные высказывания (мы не указываем на то, что это истинные высказывания, поскольку апеллируем только к синтаксическим понятиям). Нам нужно доказать, что существует такое высказывание G, что ни Gy ни не-G недоказуемы. Как мы увидели в предыдущей главе, каждому высказыванию и каждой пропозициональной функции назначается код (или число Гёделя), но сейчас мы должны подчеркнуть, что назначение происходит чисто синтаксически, на основе символов, образующих высказывание или функцию, вне зависимости от того, каково их значение. Точно так же, синтаксически, назначается код каждой последовательности высказываний и, в частности, каждому доказательству.
— Шаг 2: Гёдель доказал, что пропозициональная функция
"у — код доказательства высказывания с кодом х"
может быть представлена как арифметическое свойство, связывающее числа х и у. Кроме того, он доказал, что какими бы ни были числа n и r, высказывание
"я — код доказательства высказывания с кодом r"
всегда финитно.
— Шаг 3: Гёдель определил пропозициональную функцию
"Не существует у, которое было бы кодом доказательства высказывания с кодом х".
— Шаг 4: Гёдель определил диагональную функцию. Если n — код пропозициональной функции Р(х), то d(n) — код Р(n). Следовательно, определение диагональной функции, которое основывается на механизме назначения кодов, синтаксическое.
— Шаг 5: На основе шагов 3 и 4 метод самореференции позволил Гёделю записать высказывание G:
"Не существует у, которое было бы кодом доказательства высказывания с кодом m",
