Гёдель. Теоремы о неполноте

ГЛАВА 2 Первая теорема Гёделя

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

После окончания Первой мировой войны Австро-Венгерская империя была разделена на части. Некоторые из них, такие как Австрия, Венгрия, Югославия и Чехословакия, стали отдельными странами. Другие вошли в состав уже существовавших государств, таких как Италия или Румыния. После этого раздела город Брно, в котором жила семья Гёделя, был присоединен к Чехословакии. Курт вспоминал, что с этого момента его отец всегда чувствовал себя австрийцем в изгнании. Возможно, это ощущение в какой-то степени повлияло на решение послать обоих сыновей учиться в Венский университет, чтобы они хотя бы таким образом могли вернуться на родину.

Гёдель поступил в Венский университет в 1923 году с намерением изучать физику. Можно предположить, что врожденное любопытство с самого раннего детства привело его к вопросам о том, почему вещи, подброшенные вверх, падают, или почему некоторые предметы плавают, а другие нет, или почему светит Солнце, — все они связаны с физикой. Однако основная причина, по которой он решил посвятить себя этой науке, по- видимому, сформировалась, когда Гёделю было 15 лет, после того как он прочитал о теории цвета Гёте и о противостоянии подходу Ньютона.

Очень мало известно о личной жизни Гёделя в студенческие годы. Он едва не женился на женщине, которая была на десять лет его старше, но родители воспротивились, и Курт отказался от своего намерения. Нет информации о других личных отношениях или близкой дружбе. По-видимому, юноша посвящал большую часть времени учебе. Но в университете его намерение посвятить себя физике вскоре пропало. В те годы в Вене преподавал Филипп Фуртвенглер, немецкий математик, специализировавшийся на высшей арифметике. Он родился в 1869 году в Эльце (Германия), в 1896-м защитил докторскую диссертацию в Геттингене под руководством Феликса Клейна, одного из самых выдающихся математиков конца XIX века.

Занятия Филиппа Фуртвенглера отличались блеском и ясностью. Число студентов, которые записывались на его курс, было таким большим (оно доходило до 400 человек одновременно), что ученики были вынуждены делиться на две группы, и урок проводился дважды, для каждой из них. У Фуртвенглера был поперечный паралич, и он со своего кресла на колесах диктовал помощнику, что тот должен написать на доске.

Иоганн Вольфганг фон Гёте (1749- 1832) — немецкий романист, драматург и поэт, один из главных представителей романтизма. Помимо литературного творчества, Гёте также занимался наукой и стал автором работ по физике, зоологии и ботанике.

Многие его идеи вызвали споры, некоторые из них разрешились в последующие десятилетия. Например, его классификация растений и понятия о морфологии животных были использованы Чарльзом Дарвином и другими натуралистами XIX века. В книге Zur Farbenlehre («К теории цвета»), написанной в 1810 году, Гёте утверждал, что изучение цвета не должно сводиться к физическим аспектам света, но также должно включать в себя размышления о человеческом восприятии. Для Гёте оптика Ньютона была неполной и представляла собой только частный случай в рамках его собственной теории. Идеи Гёте о свете не заинтересовали физиков его времени; обычно они даже не включаются в работы по истории науки. Однако сегодня признано, что Гёте был прав, различая оптический аспект в том виде, как его изучал Ньютон, и более широкое явление — восприятие цветов человеком.

Портрет Гёте руки немецкого художника Йозефа Карла Штилера.

На юного Курта так подействовали занятия Фуртвенглера, что он оставил решение изучать физику и обратился к математике. Это, без сомнения, выдающийся пример того, как преподаватель может повлиять на жизнь ученика. Только через 25 лет в Принстоне у Гёделя появится возможность вспомнить о своей любви к физике. В 1949 и 1950 годах он опубликовал две важные работы по теории относительности — эти труды Гёделя, единственные не связанные с математической логикой, безусловно, стали результатом его бесед с Эйнштейном.

Небольшое совпадение: Филипп Фуртвенглер закончил обучение в Геттингене в 1896 году и оставался там до 1912-го, когда переехал в Венский университет. Между тем в 1895 году в Геттинген прибыл Давид Гильберт, считавшийся молодой надеждой немецкой математики. Хотя точных сведений об этом нет, мы уверены, что они были знакомы — Филипп Фуртвенглер, благодаря которому Гёдель посвятил себя математике, и Давид Гильберт, чья математическая работа 1920-х годов была «разрушена» теоремами Гёделя. Узнал ли когда-нибудь Фуртвенглер, что именно он вдохновил Гёделя посвятить себя математике? Нам это неизвестно.

Вернемся к Гёделю и его университетским годам. В то время, в начале 1920-х годов, интеллектуальная жизнь Вены протекала более или менее неформально, в виде кружков (Kreise). Такие группы (которых, вероятно, были десятки, и многие из них назывались одинаково) собирались еженедельно в городских кафе, чтобы обсуждать различные темы, касающиеся философии, политики или психоанализа (в те годы в Вене жил и работал Фрейд).

Самый важный кружок был основан в 1922 году Морицем Шликом, который, кроме того, преподавал Гёделю философию науки. Сначала Шлик дал группе название «Ассоциация Эрнста Маха», но позже она была известна просто как «Венский кружок» (Der Wiener Kreis). В состав группы входили, среди прочих, философы Рудольф Карнап и Людвиг Витгенштейн, а также философ и математик Ханс Хан (который руководил докторской диссертацией Гёделя). Карл Поппер также участвовал в некоторых дискуссиях. Одна из его самых важных работ, Logik der Forschung («Логика научного исследования»), впервые появилась среди публикаций кружка.

Вступить в группу можно было строго по приглашению; Гёдель получил его от Шлика в 1926 году и регулярно ходил на встречи до 1928 года — только как слушатель. Когда Гёдель получил приглашение присоединиться к кружку, он был еще студентом, и это много говорит об авторитете, который он имел среди преподавателей.

Темы обсуждений в Венском кружке касались философии науки в целом и языка науки в частности. Также обсуждали математику, в особенности решения проблемы кризиса оснований, предложенные Расселом, Брауэром и Гильбертом. Явно именно там Гёдель приобрел первые глубокие знания о формальной программе.

Участие Гёделя в Венском кружке привело его в 1928 году к окончательному решению посвятить себя математической логике. На следующий год он закончил свою докторскую диссертацию о проблеме, связанной с программой Гильберта (хотя речь еще не шла о знаменитой теореме о неполноте, которую он представил в сентябре 1930 года на конгрессе в Кёнигсберге).

Мориц Шлик — немецкий философ, родился в 1882 году. Он изучал физику вместе с Максом Планком в Берлинском университете; его докторская диссертация, представленная в 1904 году, называлась «Об отражении света в неоднородной среде». Однако Шлинк посвятил свою жизнь не физике, а философии. Его первая научная работа, «Мудрость жизни», была опубликована в 1908 году, а через два года появилось эссе Das Wesen der Wahrheit nach der modernen Logik («Природа истины согласно современной логике»). Через некоторое время Шлинк переключил свое внимание на эпистемологию и философию

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

Гёдель представил свою диссертацию в Венском университете 6 февраля 1930 года. В том же году он опубликовал ее в виде статьи. Эта его первая научная публикация появилась в томе 37 (1930) журнала Monatshefte für Mathematik und Physik под заголовком «Полнота аксиом логического функционального исчисления». Теорема, которая в ней доказана, сегодня известна как теорема Гёделя о полноте. В то время она была воспринята как знак выполнимости программы Гильберта.

Чтобы понять теорему Гёделя о полноте, мы должны прежде углубиться в теорию математического доказательства по программе Гильберта. Напомним, что согласно ей нужно найти множество аксиом, которые позволили бы доказать все арифметические истины с помощью рассуждений, проверяемых алгоритмически. Но что точно представляет собой арифметика? Каковы истины, которые мы хотим доказать?

Цель моей теории — установить раз и навсегда определенность математических методов.

Давид Гильберт, «О бесконечности»· (1925)

Арифметика — это область математики, в которой говорится о свойствах сложения и умножения натуральных чисел: 1, 2, 3, 4, 5, 6, 7,...; она включает в себя такие понятия, как простые, совершенные, треугольные или четные числа. Теория образована всеми утверждениями (также называемыми предложениями, или высказываниями), связанными с этими понятиями, например «1 + 1 = 2», «2 — четное число», «5 — простое число», «любое число, делящееся на 4, четное» или «сумма двух нечетных чисел дает в результате четное число». Аксиомы, которые искал Гильберт, были бы множеством базовых истин, из которых можно вывести, при уже изложенных условиях, все остальные истинные арифметические утверждения, в том числе упомянутые выше.

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

В целом проверка правильности математического доказательства — непростая работа, иногда даже для специалистов. Например, когда в 1995 году Эндрю Уайлс представил свое доказательство последней теоремы Ферма, которому он посвятил семь лет, специалисты, его проверявшие, нашли логический пробел — шаг, который, насколько они понимали, не был должным образом обоснован. Уайлс, естественно, этой ошибки не заметил, и ему потребовался год на ее исправление. В конце концов в 1996 году он представил полное доказательство.

Продемонстрируем менее сложный пример. Пусть а и b — два числа, которые мы считаем равными и при этом отличными от нуля. На основе того факта, что а = b, мы можем получить «доказательство» того, что 1 = 2 (для большей ясности пронумеруем логические шаги рассуждения).

Очевидно, что это рассуждение неверно, но где ошибка? Она находится в переходе от шага 5 к шагу 6. В равенстве

а · (b - а) = (b + а) · (b - а)

мы сокращаем скобки (b - а) и делаем вывод, что а = b + а. Это ошибочно, потому что (b - а) равно 0 (поскольку а = b), а 0 нельзя делить. Если представить это в виде чисел и предположить, например, что а и b равны 2, переход от 5 к 6 соответствует тому, чтобы сказать, что из 2 · 0 = 4 · 0 (что истинно) следует 2 = 4.

Но как мы можем научить компьютер обнаруживать ошибки такого типа? Компьютер — это только машина; он не рассуждает, а слепо следует программе, записанной в его памяти. Для того чтобы компьютер мог проверить правильность математического рассуждения, необходимо перевести это рассуждение в последовательность высказываний, каждое из которых либо аксиома, либо выводится из предыдущих высказываний посредством применения точных и заранее установленных логических правил.

Рассмотрим пример математического доказательства, выраженного таким образом. Для начала нам нужны некоторые аксиомы, которые будут служить нам отправной точкой. В 1889 году, задолго до открытия парадокса Рассела, итальянский математик Джузеппе Пеано предложил набор аксиом, которые (как он предполагал) позволяют доказать все арифметические истины. Эти аксиомы основывались на операциях сложения (+), произведения (·), а также понятии последующего элемента (обозначаемого буквой S).

Пеано понимал, что последовательность натуральных чисел получается на основе числа 1 посредством повторного применения функции последующего элемента. Таким образом, 2 определяется как последующий элемент для 1, что обозначается S (1) = 2; 3, по определению, — последующий элемент для 2, то есть S (2) = 3; и так до бесконечности.

Для нашего примера достаточно взять две аксиомы Пеано, относящиеся к сложению.

Аксиома 1: каким бы ни было число х, х + 1 = S(x).

Аксиома 2: какими бы ни были числа х и у, S(x + у) = х + S(у).

В первой аксиоме говорится, что последующий элемент числа х всегда получается прибавлением к нему 1. Вторую аксиому можно воспринимать как (x+y) + 1 = x + (y +1). На основе этих двух аксиом докажем, что 4 = 2 + 2.

Логическая структура доказательства того, что 4*2 + 2. Стрелки показывают применения правил вывода.

Но действительно ли нужно доказывать, что 4 = 2 + 2? Разве это не очевидный факт? Хотя это действительно очевидно, по программе Гильберта любое истинное утверждение, не являющееся аксиомой, должно доказываться на их основе. За исключением высказываний, которые явно указаны как аксиомы, нет других утверждений, которые сами по себе считаются истинными.

Итак, докажем, что 4 = 2 + 2, но запишем рассуждение таким образом, чтобы его мог обработать компьютер. Добавим несколько комментариев, чтобы мы, люди, могли следить за идеей (см. схему).

1. S(x + у) = х + S(y) Аксиома 2.

2. S(2 + 1) = 2 + S(1) Подставили х=2 и у= 1 в аксиому 2.

3. S(2 + 1) = 2 + 2 Заменили S(1) на 2 в предыдущем шаге.

Комментарий: в следующих трех шагах представлено небольшое поддоказательство того, что 2 + 1 = 3; таким образом, в шаге 3 мы можем заменить S(2 + 1) на S(3).

4. х +1 = S(x) Аксиома 1.

5. 2 + 1 = S(2) Подставили = 2 в аксиому 1.

6. 2 + 1 = 3 В предыдущем шаге заменили 5(2) на З.

Комментарий: теперь мы можем заменить 5(2 + 1) на 3 в третьем шаге.

7. S( 3) = 2 + 2

8. 4 = 2 + 2 Заменили S(3) на 4 в предыдущем шаге.

Нужна ли такая точность для доказательства того, что два плюс два равно четыре? Да, это необходимо, если мы хотим, чтобы компьютер был способен проверять правильность рассуждений. Компьютер не думает; следовательно, мы должны вести его за руку, шаг за шагом показывая ему, используя заранее установленные правила, что именно мы сделали на каждом этапе рассуждений.

Действительный мир есть мир, постоянно изменяющийся. [...] Но такие изменения, независимо от их силы, никогда не разрушат истинности отдельного логического или арифметического закона.

Рудольф Карнап. «Философские основания физики»

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

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

После первой проверки машина переходит ко второму высказыванию, S(2 + 1) = 2 + S(1), и проверяет, что это не аксиома (поскольку ее нет в списке). Тогда это второе высказывание должно сводиться к первому с помощью какого-либо логического правила. Чтобы осуществить эту проверку, в память компьютера должен быть загружен список правил логики, то есть правил, которые показывают, какие выводы можно сделать из определенных предпосылок (см. схему).

В случае нашего доказательства правило, позволяющее перейти от шага 1 к шагу 2, заключается в том, что если высказывание начинается с «какими бы ни были числа х и y...», то в следующем выражении буквы х и у могут быть свободно заменены любыми числами. В нашем примере буква х заменена числом 2, а у — числом 1.

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

Мы уже упомянули одно из этих правил. Другие примеры: «если х = у, то у = х» и «если два числовых выражения равны, то любое из них может быть заменено на другое». Именно это — последнее — правило оправдывает переход от шага 2 к шагу 3, где S(1) заменяется на 2.

Схема механической проверки доказательства.

Но когда существует потенциально бесконечное число универсально справедливых высказываний, как мы можем загрузить их все в память компьютера? Если это нельзя сделать, то компьютер неспособен проверить справедливость любого рассуждения, и, следовательно, программа Гильберта оказывается неосуществимой. При этом ни один компьютер не способен содержать бесконечное число высказываний.

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

Квантор всеобщности , читается «для каждого». Указывает, что обозначаемое свойство справедливо для любого числа.

=>: Символ импликации; «Р => Q» означает «если Р, то Q».

┐:Символ отрицания;"┐ Р" означает "не-Р".

=: Знак равенства.

1: Число один.

S: Означает "последующий элемент".

+; Символ суммы.

(·): Символ произведения.

(): Скобки.

х₁ х₂, х₃,...: Переменные.

В некоторых представлениях предпочитается брать в качестве первого элемента 0, но это не является существенным. При использовании символов, которые мы привели, число 2 записывается как S(1), то есть следующий за 1. Число 3 записывается как S[S(1)], то есть следующий за следующим за 1. И так далее.

К счастью, в теореме о полноте Гёдель доказал, что хотя количество логических правил потенциально бесконечно, любое рассуждение можно осуществить, используя только 12 из них. Если загрузить в память компьютера эти 12 правил, он будет способен проверить правильность любого доказательства.

Когда в начале 1930 года эта теорема была опубликована, казалось, что необходимая логическая основа для программы Гильберта обеспечена: можно механически проверить правильность арифметических доказательств. Проблема, которую оставалось решить, состояла в том, чтобы найти множество аксиом, которое (на основе этих 12 правил) позволило бы доказать все арифметические истины.

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

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

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

Гёдель доказал эту теорему в 1930 году и, как мы уже знаем, впервые открыто изложил ее на конгрессе в Кёнигсберге 7 сентября того же года. Статья с выведением доказательства была послана в журнал Monatshefte für Mathematik und Physik ("Ежемесячник по математике и физике") в ноябре и появилась в томе 38 (1931). Значение этой публикации для логики сравнимо только с "Метафизикой" Аристотеля. Изложение доказательства было таким ясным и прозрачным, что не вызвало ни малейшей полемики.

В своей докторской диссертации, представленной в 1930 году, Гёдель доказал, что любое рассуждение, которое можно проверить алгоритмически, может быть построено всего на 12 логических правилах, которые мы приводим ниже. Далее выражение "Р => Q" означает "если Р, то Q", а " x Р(х)" — "каждое х выполняет свойство Р".

1. Если справедливо высказывание Q, то, каким бы ни было Р, справедливо высказывание "Р => Q".

2. Если справедливо "Р => (Q => R)" и также справедливо "Р => Q", то справедливо "Р=> R".

3. Если справедливо "не-Q => не-Р", то также справедливо "Р => О".

4. Если справедливо" x P(x)", то справедливо "Р(n)", где n — любое число.

5. Если справедливо " x Р => Q(x)", то справедливо "Р => [ x Q(x)]", если только х не используется в Р.

6. Каким бы ни было число х, справедливо, что х = х.

7. Какими бы ни были числа х и у, справедливо, что если х = у, то у = х.

8. Какими бы ни были числа х, у, z, справедливо, что если х = у и у = z, то х = z.

9. Если х = у, то можно заменить х на у в любом числовом выражении.

10. Если х = у, то можно заменить х на у в любом высказывании.

11. Если справедливо Р и справедливо "Р => Q", то справедливо Q.

12. Если справедливо Р(х) для произвольного х, то справедливо" x P(х)".

В целом первые десять правил представлены как универсально справедливые высказывания, в то время как два последних представлены отдельно как правила вывода. Это разграничение чисто техническое и не имеет значения для наших целей.

Но как можно доказать факт такого масштаба? Как можно доказать, что каким бы ни было множество выбранных аксиом (если рассуждения проверяются алгоритмически), то всегда найдется истина, недоказуемая на их основе? Сейчас мы перейдем к объяснению доказательства и для этого рассмотрим, шаг за шагом, основные моменты рассуждений Гёделя.

Ханс Хан, руководитель докторской диссертации Гёделя. Этот австрийский философ и математик внес значительный вклад в формирование Венского кружка.

Немецкий математик Филипп Фуртвенглер, преподаватель Гёделя в Венском университете.

Курт Гёдель в 1935 году, через пять лет после защиты докторской диссертации в Венском университете.

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

Главная идея доказательства состоит в том, чтобы получить высказывание G, в котором будет говориться: "G недоказуемо". Другими словами, G может быть записано так: "Это утверждение недоказуемо".

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

Для начала заметим, что G либо истинно, либо ложно. Если бы G было ложно, в связи с тем, что в G говорится о самом себе, можно было бы сделать вывод, что G доказуемо. Следовательно, G было бы одновременно ложным и доказуемым, но это невозможно (ведь мы сказали, что исходя из истинных аксиом можно доказать только истинные высказывания). Следовательно, G не может быть ложным.

Следовательно, G истинно, и согласно тому, что оно говорит о самом себе, оно недоказуемо. Так мы делаем вывод, что G — истинное и недоказуемое высказывание (см. схему).

Предыдущая идея, хотя и правильная в целом, имеет одну проблему: G должно быть арифметическим утверждением. Но арифметические высказывания относятся к свойствам натуральных чисел, в них не говорится о других высказываниях и тем более о самих себе. Как мы можем преодолеть это ограничение и сделать так, чтобы арифметическое высказывание относилось к другому высказыванию? Если в высказываниях говорится о числах, а нам надо, чтобы в них говорилось о других утверждениях, то нужно приравнять числа к утверждениям:

Числа ↔ Утверждения.

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

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

"4 = 2 + 2" ↔ код 67

"2 — четное число" ↔ код 223

"162 делится на 18" ↔ код 103

"4 — нечетное число" ↔ код 149

"171 — четное число" ↔ код 61.

Мы настаиваем: коды не назначаются наугад или произвольно. Напротив, существует алгоритм, который при заданном высказывании позволяет точно вычислить его код. Также существует обратный алгоритм, который при заданном коде может восстановить высказывание, которому он соответствует. Более того, в действительности коды, если их правильно вычислить, могут содержать десятки цифр. Например, при реальном вычислении утверждению "1 = 1" соответствует код 2187000000000.

Заметим, что в нашем примере два последних высказывания ложны. Это показывает, что числа Гёделя назначаются всем высказываниям, как истинным, так и ложным. С технической целью числа Гёделя также назначаются общим выражениям, таким как "х — четное число" или "х делится на 18". Они относятся не к конкретному числу, а к переменному числу х. Эти выражения Бертран Рассел называл пропозициональными функциями.

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

Мы уже сказали, что каждой пропозициональной функции также назначается число Гёделя (как и для высказываний, эти коды вычисляются с помощью установленного алгоритма). Например, мы можем представить, что:

"х делится на 18" ↔ код 162

"х — четное число" ↔ код 171.

Заметим, что "х — четное число" назначается код 171, в то время как высказыванию "2 — четное число" соответствует код 223. Коды разные, и это правильно, поскольку речь идет о разных лингвистических объектах. Точно так же "1 — четное число", "3 — четное число", "4 — четное число" имеют разные числа Гёделя.

Наконец, число Гёделя также назначается каждой конечной последовательности высказываний (которое вычисляется на основе кодов высказываний, образующих последовательность). Идея этого назначения в том, чтобы гарантировать, что каждое доказательство также можно будет идентифицировать по его коду. Например, следующему доказательству того, что "4 = 2 + 2" на основе аксиом "S(x + у) = х + S(y)" и "х + 1 = = S(x)":

S(x + y)=x + S(y) 173

S(2 + 1)-2+ S(1) 199

S(2 + 1) = 2+ 2 13

х + 1 = 5(х) 37

2 + 1 = 5(2) 83

2 + 1=3 7

S(3) = 2+ 2 251

4 = 2 + 2 67

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

Как в действительности определяется нумерация Гёделя? Чтобы определить ее, каждое высказывание и каждая пропозициональная функция должны быть выражены с помощью символов формального языка. Ученый назначил каждому символу этого языка нечетное число.

1

=> 3

┐ 5

= 7

1 9

S 11

+ 13

· 15

( 17

) 19

x₁ 21

х₂ 23

х₃ 25

Количество переменных потенциально бесконечно. Оставшимся (х₄, х₅, ...) соответствуют числа 27, 29 и так далее. Гёдель назначил коды высказываний и пропозициональных функций. Для большей ясности объясним метод на конкретном примере. Какой код соответствует, например, высказыванию "1 = 1"? Шаги для его вычисления следующие.

1. Сначала остановимся на кодах символов, образующих высказывание: 9, 7,9.

2. Поскольку есть три символа, теперь возьмем по порядку три первых простых числа: 2, 3, 5.

3. Тогда код следующий: 2⁹ · З⁷ · 5⁹ = 2187 000 000 000. (Заметьте, что простые числа — это основания степеней, а коды символов — показатели степеней.)

Для вычисления числа Гёделя конечной последовательности высказываний поступают похожим образом, только на шаге 1 берутся по порядку коды высказываний, образующих последовательность, а на последнем шаге они становятся показателями степеней простых чисел.

Конечно же, как и в предыдущих случаях, должен существовать механический способ, указывающий, как вычислить код последовательности высказываний, и другой, обратный способ, который при заданном коде позволил бы восстановить последовательность соответствующих ему высказываний. Наше правило вычисления кода последовательности как произведения индивидуальных кодов неверно, потому что игнорируется порядок высказываний (при перестановке высказываний местами код конечной последовательности остается тем же самым, но этого не должно происходить, так как при перестановке на самом деле получается другая последовательность). Однако, поскольку речь идет только о гипотетическом примере, мы не будем останавливаться на этом вопросе.

Коды, или числа Гёделя, приводят не только к тому, что арифметическое высказывание можно связать с другим высказыванием, но и к возможности говорить о доказуемости этого высказывания. Например, при заданном утверждении Р мы можем записать арифметическое высказывание, в котором говорилось бы, что "Р недоказуемо". Посмотрим, как достичь этой цели.

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

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

Подчеркнем: именно эта часть аргументации Гёделя зависит в основном от того факта, что программа Гильберта допускает только доказательства, проверяемые алгоритмически. Если бы были разрешены другие методы рассуждения (поговорим о них в следующей главе), то не было бы возможности гарантировать, что свойство "х — это код доказуемого высказывания" может быть выражено в арифметических терминах.

Все принципы математики сводятся к принципам логики.

Уиллард ван Орман Куайн. "С точки зрения логики"

Как Гёдель доказал, что понятие доказуемости можно выразить? Для начала он доказал, что любое числовое свойство, проверяемое алгоритмически (например, "быть простым числом", "быть четным" или "делиться на 9"), всегда можно выразить с помощью сумм, произведений и логических операций.

Итак, то, что высказывание Р доказуемо, означает, что существует доказательство (принимаемое программой Гильберта), в котором Р — это конечное высказывание. В качестве примера мы уже приводили доказательство того, что "4 = 2 + 2" на основе аксиом "S(x + у) = х + S(y)" и "х + 1 = S(x)". Вспомним, что этому доказательству, с учетом последовательности высказываний, соответствует число Гёделя 2414871965597. Вспомним также, что "4 = 2 + 2" соответствует число 67. В переводе на язык кодов доказуемость "4 = 2 + 2" означает, что существует конечная последовательность высказываний (ее код 2414871965597), являющаяся доказательством, в котором конечное высказывание имеет код 67.

"Быть кодом доказательства" — это свойство, проверяемое алгоритмически, поскольку при заданном коде для осуществления проверки компьютер сначала использовал бы программу, восстанавливающую последовательность высказываний, соответствующую этому коду, а затем применил бы к этой последовательности высказываний алгоритм, который определяет, идет ли речь о доказательстве:

Код последовательности → Последовательность высказываний → Это доказательство?

Теория доказательства ставит две проблемы, которые хоть и схожи, но не должны смешиваться. Первая заключается в том, чтобы при данном высказывании Р найти его доказательство (или доказать, что его не существует). Вторая — в том, чтобы определить, верно ли предложенное доказательство. Вторая проблема может быть сложной, но первая намного сложнее. Если методы доказательства подходящие, то вторая проблема может быть решена алгоритмически. Проблема нахождения доказательства, наоборот, неразрешима таким образом.

Британский математик Эндрю Уайлс.

В качестве примера можно рассмотреть последнюю теорему Ферма.

В 1637 году Пьер Ферма записал, что если n > 2, то уравнение хⁿ + уⁿ = zⁿ не имеет решений для натуральных чисел. Ферма уверял, что у него есть доказательство этого факта, но так и не привел его. Проблема нахождения доказательства последней теоремы Ферма стала широко известной и в конце концов была решена Эндрю Уайлсом в 1996 году (он представил первое доказательство в 1995 году, но выяснилось, что в нем содержится ошибка, которая была исправлена почти через год). Определение правильности доказательства Уайлса потребовало несколько дней усилий; но для нахождения доказательства понадобилось более 350 лет.

Каждый шаг может осуществляться алгоритмически.

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

Наконец, делаем вывод, что выражение "существует некое у у являющееся кодом доказательства, заканчивающегося высказыванием с кодом х" также можно выразить арифметическими терминами. Фактически в этом утверждении говорится, что существует некое доказательство высказывания с кодом х_у другими словами — что высказывание с кодом х доказуемо. Так мы приходим к выводу, что пропозициональную функцию "х — это код доказуемого высказывания" можно выразить арифметическими терминами.

Обычно этот арифметический перевод так сложен, что его явная структура может занять десятки страниц. Поэтому, чтобы понять идею доказательства Гёделя, предположим в качестве гипотетического примера, что свойство, характеризующее коды доказуемых высказываний, — это свойство "быть простым числом, которое может быть записано как сумма или разность трех последовательных простых чисел". Тогда мы допускаем, что "х — это код доказуемого высказывания" равносильно "х — это простое число, которое может быть записано как сумма или разность трех последовательных простых чисел".

Прежде чем продолжить, разберем это свойство. Простые числа — это числа, которые делятся только на единицу и на самих себя. Существует бесконечное число простых чисел: 2,3,5, 7,11,13,17, 19, 23,... (как уже говорилось в предыдущей главе, по техническим причинам число 1 не считается простым).

Число 23, например, простое и может быть записано как сумма или разность трех последовательных простых чисел, поскольку 23 =17 +19 -13 (заметим, что 13, 17 и 19 идут друг за другом в цепочке простых чисел, при выполнении операций их записали в другом порядке). В нашем примере мы можем убедиться, что 23 — это код доказуемого высказывания. Наоборот, 149 — это простое число, которое не может быть записано как сумма или разность трех последовательных простых чисел. Но 149 в нашем гипотетическом примере — это код высказывания "4 — нечетное число". Следовательно, говорить, что "149 не является простым числом, которое можно записать как сумму или разность трех последовательных простых чисел" равносильно тому, чтобы сказать: "высказывание о том, что 4 — нечетное число, является недоказуемым" (и действительно, оно недоказуемо, потому что мы предположили: аксиомы — это истинные высказывания, следовательно, всякое ложное высказывание недоказуемо). Повторим это понятие, поскольку это сердце доказательства Гёделя. Высказывание:

"149 не является простым числом, которое может быть записано как сумма или разность трех последовательных простых чисел" — это, для начала, утверждение арифметического свойства, связанного с числом 149. Но используя нумерацию Гёделя, этому же высказыванию мы можем приписать значение:

"высказывание о том, что 4 — нечетное число, является недоказуемым".

Существует два уровня прочтения "149 не является простым числом, которое можно записать как сумму или разность трех последовательных простых чисел". С одной стороны, чисто арифметически это дословный уровень, на котором мы истолковываем высказывание, выражая свойства числа 149. С другой стороны, у нас есть высший уровень прочтения, метаматематический, зависящий от нумерации Гёделя, и на нем мы истолковываем высказывание, говоря, что утверждение "4 — нечетное число" недоказуемо.

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

Предположим, что 101 — это код некоего высказывания Q. При таком предположении высказывание "101 — нечетное число" относится к Q и означает "код высказывания Q нечетный". Теперь представим себе, что мы ищем, какому высказыванию соответствует код 101 (то есть задаемся вопросом, что такое Q), и выясняем, что 101 — это число Гёделя для "101 — нечетное число". В этом случае "101 — нечетное число" действительно относится к самому себе и может быть переведено как "мой код — нечетное число".

Да, так и есть, можно построить высказывание, относящееся к его собственному коду. В своей статье Гёдель изложил систематический метод, позволяющий записать арифметические высказывания, относящиеся к собственному коду. Если Р — это любое арифметическое свойство (такое, как "быть четным числом" или "быть простым числом"), то этот метод — метод самореференции — объясняет, как записать высказывание, которое может означать "мой код выполняет свойство Р". Основной инструмент этого метода — функция d(x), которую Гёдель назвал диагональной.

Функция — это правило, которое каждому числу х ставит в соответствие другое число. Оно может совпадать с х или отличаться, но вычисляется однозначно (одному и тому же х не могут соответствовать два разных числа). Правилами могут быть "умножить число х само на себя" или "прибавить 3 к числу х". Для числа 2 первая функция даст значение 4, а вторая — 5. В частности, нас интересуют функции, которые могут быть выражены в терминах сумм, произведений и логических операций.

Пропозициональные функции получили это название, потому что они похожи на функции, но ставят в соответствие не числа, а высказывания. Например, пропозициональная функция "х — четное число" сопоставляет числу 2 высказывание "2 — четное число".

В запись пропозициональных функций мы можем ввести числовые функции, если только они могут быть выражены в терминах сумм, произведений и логических операций. Так, мы можем записать: "х + 3 — простое число" или даже "х² делится на 18", и в обоих случаях это полноправные пропозициональные функции.

Теперь рассмотрим определение функции d(x), которая на самом деле вычисляется только для чисел, являющихся кодами пропозициональных функций. Поясним определение на примере. Возьмем код пропозициональной функции, например 171, который, как мы предположили, является числом Гёделя выражения "х — четное число". Далее в этой пропозициональной функции заменим х числом 171. Мы получим высказывание "171 — четное число". Код этого высказывания — d( 171), число, которое диагональная функция назначает числу 171:

171 → соответствует "х — четное число" → заменяем х на 171 → "171 — четное число" → d(171) — код "171 — четное число".

В первых примерах мы указали, что "171 — четное число" имеет код, равный 61. Следовательно, d(171) = 61. Диагональная функция сопоставляет числу 171 значение 61.

Во втором примере вычислим d(162), где 162 — это код "отделится на 18":

162 → соответствует "х делится на 18" → заменяем х на 162 → "162 делится на 18" → d(162) — это код "162 делится на 18".

Так как "162 делится на 18" имеет код 103, то d(162) = 103. Все шаги, определяющие диагональную функцию, могут быть вычислены алгоритмически, следовательно, ее определение можно выразить с помощью сумм, произведений и логических операций. Это обстоятельство дает нам право ввести числовую функцию d(x) в выражение пропозициональной функции, точно так же как в предыдущих примерах мы это делали с х² или х + 3. Таким образом мы можем рассмотреть выражение "d(x) — четное".

Предположим, что "d(x) — четное" соответствует код 423, и применим эту процедуру для вычисления d(423):

423 —> соответствует "d(x) — четное" -" заменяем х на 423 —" —" "d(423) — четное" —> d(423) — код "d(423) — четное".

Возьмем любое натуральное число, например 25. На его основе построим последовательность чисел, называемую последовательностью Гудстейна для числа 25 (названа в честь Рубена Луиса Гудстейна (1912-1985), английского математика, который впервые ее определил). Для получения второго числа последовательности запишем 25 как сумму степеней числа 2 так, чтобы каждая степень появлялась ровно один раз (1 — это тоже степень числа 2, поскольку 2⁰ = 1):

25 = 2⁴+2³+1.

И запишем также каждый показатель степени как сумму степеней числа 2:

25 = 2^2² +2²⁺¹ + 1.

Второй член последовательности получается, если заменить каждое 2 на 3 в выражении 222 + 2²⁺¹ +1 и затем вычесть 1:

(З^3³ + З³⁺¹ +1) - 1 = З^3³ + З³⁺¹ = 7625597485068

Второе число последовательности Гудстейна для числа 25 — это 7625597485068. Для получения третьего числа заменяем каждое 3 на 4 в З^3³ + З³⁺¹ и вычитаем 1. Получается 4^4⁴ + 4⁴⁺¹ - 1, операция, которая в результате дает число из 155 цифр. Прежде чем перейти к следующему шагу, надо записать 4^4⁴ + 4⁴⁺¹ - 1 как сумму степеней числа 4, в которой каждая степень появляется самое большое 3 раза и в которой показатели степени также являются суммой степеней числа 4. Заметьте, что 4^4⁴ + 4⁴⁺¹ - 1 не записано таким образом, поскольку присутствует вычитание. Правильная запись:

4^4⁴ + 4⁴ + 4⁴ + 4⁴ + 4¹⁺¹⁺¹ + 4¹⁺¹⁺¹ + 4¹⁺¹⁺¹ + 4¹⁺¹ + 4¹⁺¹ + 4¹⁺¹ + 4 + 4 + 4 + 1 + 1 + 1.

Чтобы получить четвертое число, заменим каждое 4 на 5 и вычтем 1. То есть:

5^5⁵ + 5⁵ + 5⁵ + 5⁵ + 5¹⁺¹⁺¹ + 5¹⁺¹⁺¹ + 5¹⁺¹⁺¹ + 5¹⁺¹ + 5¹⁺¹ + 5¹⁺¹ + 5 + 5 + 5 + 1 + 1.

Результат последнего вычисления состоит из более чем 2000 цифр. Для получения следующего числа заменим каждое 5 на 6 и вычтем 1, и так далее. Кажется, что последовательность растет до бесконечности. Однако в теореме Гудстейна, доказанной им около 1950 года, утверждается, что вне зависимости от исходного числа последовательность всегда за конечное количество шагов достигнет 0. В доказательстве Гудстейна были использованы понятия теории множеств и оставалась открытой возможность того, что оно неосуществимо на основе аксиом Пеано. Это было подтверждено в 1982 году Лори Кирби и Джеффом Пэрисом, которые доказали, что теорема Гудстейна действительно недоказуема на основе аксиом Пеано с помощью рассуждений, проверяемых алгоритмически.

Посмотрим внимательно на последний шаг: d(423) — это код "d(423) — четное". То есть "d(423) — четное число" может читаться как самореферентное высказывание, говорящее о своем собственном коде следующее: "мой код — четное число". Если бы у "d(423) — четное число" кодом было 503, то высказывание можно было бы записать как "503 — четное число" и в нем бы ложно утверждалось, что его собственный код — четное число.

Метод самореференции говорит, что эта процедура может применяться к любому арифметическому свойству Р Возьмем пропозициональную функцию "х выполняет свойство Р" и трансформируем ее в "d(x) выполняет свойство Р". Если код последнего выражения — число я, то "d(n) выполняет свойство Р" может быть прочитано посредством кодификации Гёделя как самореферентное высказывание, гласящее: "мой код выполняет свойство Р". Теперь посмотрим, как этот метод приведет нас в итоге к искомому высказыванию G.

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

"x: не является кодом доказуемого высказывания", что, как говорится в методе самореференции, превращается в: "d(x) не является кодом доказуемого высказывания". Если его код — число т, то:

G: "d(m) не является кодом доказуемого высказывания"

имеет в качестве кода число d(m) и может рассматриваться как самореферентное высказывание, говорящее о своем коде следующее: "мой собственный код не соответствует доказуемому высказыванию". Другими словами, в G говорится:

"G недоказуемо".

Как мы видели в начале доказательства, это высказывание является истинным и одновременно недоказуемым (вспомним, что "доказуемый" всегда означает "доказуемый на основе предложенных аксиом"). Мы доказали, что существует высказывание G, являющееся истинным и недоказуемым, и описали шаги, необходимые для того, чтобы записать его. Этим завершается доказательство первой теоремы Гёделя о неполноте.

Один из самых древних известных парадоксов — это так называемый парадокс лжеца. Он возникает, если поставить вопрос, является ли утверждение "это предложение ложное" истинным или ложным. Если утверждение истинно, то, судя по его смыслу, оно оказывается ложным. Но если оно ложно, то оно получается истинным. Так мы сталкиваемся с бессмыслицей, порочным кругом, который снова и снова приводит нас от истинности к ложности и от ложности к истинности. В своей статье 1931 года Гёдель объяснил, что его доказательство найдено под влиянием парадокса лжеца, только вместо того чтобы написать высказывание, говорящее о собственной ложности, Гёдель написал высказывание, говорящее о собственной недоказуемости. Высказывание "это предложение ложно" — парадоксальная бессмыслица. Но высказывание "это предложение недоказуемо на основе предложенных аксиом" — недоказуемая истина.

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

Как выглядело бы высказывание G в нашем гипотетическом примере? Вспомним, что в этом примере свойство, характеризующее коды доказуемых высказываний, — это "быть простым числом, которое может быть записано как сумма или разность трех последовательных простых чисел". Возьмем пропозициональную функцию "х не является простым числом, которое может быть записано как сумма или разность трех последовательных простых чисел" и трансформируем ее в "d(x) не является простым числом, которое может быть записано как сумма или разность трех последовательных простых чисел". Предположим, что последнему выражению соответствует число 909.

Тогда высказывание G формулируется как

"d(909) не является простым числом, которое может быть записано как сумма или разность трех последовательных простых чисел".

Также предположим, что d(909) — это число 43. Следовательно, G примет вид

"43 не является простым числом, которое может быть записано как сумма или разность трех последовательных простых чисел".

Как уже было указано раньше, G имеет два уровня прочтения. На элементарном уровне это выражение арифметического свойства числа 43. Только когда мы смотрим на него через призму кодификации Гёделя, оно превращается в самореферентное и может читаться как говорящее о самом себе, что оно недоказуемо. Во второй главе мы увидим, что это замечание о различных уровнях прочтения позволяет преодолеть видимый парадокс, который возникает из анализа второй теоремы Гёделя.

В связи с первой теоремой о неполноте обычно возникает вопрос: если G — недоказуемая истина, как мы можем быть уверены в ее истинности?

Ответ заключается в том, что "доказуемый" — относительное понятие. Если задано множество аксиом Л, существует истинное высказывание G, которое недоказуемо на основе этих аксиом (с использованием методов доказательства, принятых в программе Гильберта). Но ничто не мешает G быть доказуемым на основе других аксиом или с помощью других методов.

Хотя это пока точно не известно, последняя теорема Ферма может быть примером истины, недоказуемой на основе аксиом Пеано. В этой теореме, впервые предложенной Пьером

Ферма в 1637 году, утверждается, что если n > 2, то хⁿ + уⁿ + zⁿ не имеет решений среди натуральных чисел. После многочисленных попыток теорема наконец была доказана Эндрю Уайлсом в 1996 году.

Однако доказательство Уайлса во многом выходит за пределы обычных методов или аксиом арифметики. Последняя теорема Ферма истинна (Уайлс доказал это), но доказуема ли она, например, на основе аксиом Пеано с помощью методов программы Гильберта? Сегодня ответ на этот вопрос неизвестен, но наиболее разумное предположение заключается в том, что последняя теорема Ферма недоказуема на основе аксиом Пеано посредством рассуждений, проверяемых алгоритмически.

Однако если G недоказуемо на основе множества A аксиом, вполне возможно добавить во множество А новую аксиому, так что G станет доказуемым на основе этой расширенной системы, которую обозначим А'. Конечно, для А также справедлива теорема Гёделя, и, следовательно, будет существовать арифметическое утверждение G', которое является недоказуемым на ее основе.

Мы можем добавить в А новую аксиому, которая позволит доказать G\ и так получим множество A", где G будет доказуемым. Но для А' существует новое недоказуемое высказывание G". Мы можем добавить новую аксиому в А", но тогда существует недоказуемое G""... И так до бесконечности...

A —> G недоказуемо.

А' = А + другая аксиома —> G доказуемо, но G' — нет.

А" = А' + другая аксиома —> G и G" доказуемы, но G" — нет.

А"' + другая аксиома —> G, G и G" доказуемы, но G'" — нет.

Добавляя аксиомы по одной, никогда не удастся достигнуть полноты (то есть возможности доказать все истины). Но можно ли добиться этого другими средствами? Обратимся к этому вопросу в следующей главе.