3.5.2. Вторая теорема Геделя (1931 г.): неполнота арифметики

Арифметизацию можно выполнить для любой формальной системы. В частности, можно закодировать с ее помощью и такие формальные системы, как исчисление высказываний и исчисление предикатов первого порядка, а также и саму формальную арифметику! Доказательство Геделя навеяно этим автоморфизмом, который установил в формальной арифметике своего рода вариант “парадокса” лжеца. Этот парадокс происхождением обязан Эвбулиду (диалектику), принадлежавшему к Мегарской школе (4 век), основанной Евклидом Сократиком. Парадокс формулируется следующим образом:

“Эпименид говорит: “Критяне - лжецы”,

Однако Эпименид сам критяиин...”

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

В последующем в течение длительного периода времени в логике не было получено новых фундаментальных результатов, пока Лейбниц и затем уже современные логики, которые вновь исследовали результаты древних авторов, не систематизировали их и не ввели в логику математические методы. В результате этого появилась вторая теорема Геделя: формальной арифметике существуют формулы такие, что ни ни не являются доказуемыми».

Доказательство этой теоремы в данной книге следует в основном доказательству Ладриера, приведенному в книге «Внутренние ограничения формализмов» (Nauwelaerts et Gauthier Villars, 1957 г.), и подходу Д. Хофштедтера. Однако вначале приведем результат, который недавно был получен на основе идей К. Геделя. Речь идет о методе “диагонали” (или диагональном рассуждении) Кантора, который в 1873 г. показал, что множество действительных чисел не может быть перенумеровано с помощью целых чисел. В процессе доказательства Кантор ограничился рассмотрением действительных чисел, заключенных в промежутке между нулем и единицей. Его идея состояла в том, чтобы построить бесконечный список из таких чисел в виде десятичных дробей и в предположении, что этот список может быть пронумерован. Список выглядит следующим образом:

Сформируем теперь число такого же типа, которое однако наверняка не является частью данного списка. Для этого достаточно в качестве значения разряда этой десятичной дроби принять увеличенное на единицу значение разряда дроби, находящейся в строке списка . В результате такого построения мы получаем действительное число

которое, однако, по построению и в силу свойств использованных при этом десятичных дробей, отличается от любого числа, входящего в список Таким образом, доказательство возможности перечисления с помощью натуральных чисел всех действительных чисел не может существовать. Отметим, что идея доказательства состоит в том, чтобы “заставить” один и тот же номер одновременно выполнять две роли. Действительно, при

построении нашего диагонального числа номер использовался одновременно и как индекс (вертикальный) действительного числа в списке и как номер позиции (горизонтальный) какой-то цифры в десятичном представлении числа. Из такого использования “диагонального” k и родилось доказательство Кантора.

Существует другой парадокс, связанный с методом диагонали Кантора, который в большей степени приблизит нас к подходу Геделя.

Этот парадокс получил название парадокса Ришара (1907). Он в отличие от парадокса Эвбулида связан не с понятием истинности, а с понятием определения. Рассмотрим, как определяются на обычном языке натуральные числа. Каждое такое число может быть однозначно описано с помощью конечного множества символов: букв, цифр, знаков препинания. Одно и то же число может иметь несколько различных определений. Договоримся, что в качестве определения данного числа будет использоваться наиболее короткое (т. е. содержащее наименьшее число символов) из всех его определений.

Теперь рассмотрим подмножество С целых чисел, определенных менее 100 символами. Это подмножество С является конечным, поскольку существует лишь конечное число комбинаций, которые можно составить из конечного множества символов. Однако, поскольку множество всех натуральных чисел является бесконечным, существуют целые числа, которые не принадлежат подмножеству С. Пусть число является наименьшим среди них. Тогда можно дать следующее определение для натурального числа : “наименьшее натуральное число, которое не может быть определено, используя менее 100 символов”. Однако именно это определение и сделано в предыдущей фразе с использованием менее 100 символов. В этом и заключаются противоречие и парадокс, связанный с “зацикливанием” определения.

Первый этап доказательства Геделя состоит в эффективном кодировании числами всех условий, входящих в определение формальной арифметики. Построение “парадоксального” условия приведет в конце концов к знаменитой второй теореме Геделя: “Система формальной арифметики содержит некоторое выражение такое, что ни и ни не являются доказуемыми в формальной арифметике”.