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

Излагаемый в этой брошюре способ доказательства теоремы Гёделя отличен от способа, предложенного самим Гёделем, и опирается на элементарные понятия теории алгоритмов. Все необходимые сведения из этой теории сообщаются по ходу дела, так что читатель одновременно знакомится с основными фактами теории алгоритмов. Брошюра написана на основе статьи автора в журнале "Успехи математических наук", 1974, том 29, выпуск 1 (175). Естественно, что изменение круга предполагаемых читателей сделало необходимой ее переработку. В частности, некоторые более специальные вопросы, а также библиографические ссылки на оригинальные публикации исключены, и любознательный читатель может найти их в упомянутой статье автора. Одновременно расширен раздел, посвященный связи между семантической и синтаксической формулировками теоремы о неполноте, а также добавлены приложения, посвященные теореме Тарского о невыразимости понятия истины и обоснованию аксиомы арифметичности.

План брошюры таков. В § 1 формулируется теорема о неполноте и уточняется ее формулировка, в частности вводится центральное для данной брошюры понятие дедуктики. В § 2 излагаются на неформальном уровне начальные понятия теории алгоритмов, и на их основе формулируются первые критерии полноты и неполноты. В § 3 продолжается исследование критериев неполноты. В § 4 описывается язык формальной арифметики, дается точное определение понятия истинности утверждения этого языка и точная формулировка теоремы Гёделя о неполноте для формальной арифметики. В § 5 на основе дальнейшего развития тех представлений об алгоритмах, которые были описаны в § 2,— развития, закрепляемого в виде трех аксиом теории алгоритмов, — завершается доказательство теоремы о неполноте формальной арифметики.

Брошюра снабжена шестью приложениями, написанными несколько более сжато, хотя по-прежнему не предполагающими никаких специальных знаний. В первом из них рассматривается вопрос о связи между наличием истинных недоказуемых утверждений и наличием утверждений, не являющихся ни доказуемыми, ни опровержимыми. Во втором доказывается некоторое усиление теоремы Гёделя — теорема Тарского о невыразимости понятия истины. Третье приложение посвящено обоснованию одной из аксиом теории алгоритмов, сформулированных в § 5, а именно, аксиомы арифметичности. С этой целью вводится некоторый конкретный класс алгоритмов — класс адресных программ — и проверяется арифметичность функций, вычисляемых алгоритмами этого класса. В четвертом приложении развитые в § 2 критерии полноты и неполноты применяются к языкам, связанным с так называемыми ассоциативными исчислениями. Пятое приложение посвящено первоначальной формулировке теоремы о неполноте, предложенной самим Гёделем. Шестое приложение содержит упражнения к некоторым из предыдущих разделов. Наконец, последнее приложение содержит ответы и указания к упражнениям. Приложения не зависят друг от друга и могут читаться в любом порядке, за исключением приложения В, отдельные места которого требуют знакомства с введенными в приложении Б понятиями.

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

1. Машины Тьюринга и рекурсивные фуккции. Эббинхауз Г.-Д., Якобс К., Ман Ф.-К., Хермес Г. — М.: Мир, 1972, 264 с. (Современная математика. Популярная серия.)

2. Ершов Ю. Л., Палютин Е. А. Математическая логика. — М.: Наука, 1979, 320 с..

3. Клини С. К. Введение в метаматематику. — М.: ИЛ, 1957, 526 с.

4. Клини С. К. Математическая логика. — М.: Мир, 1973, 480 с.

5. Коэн П. Дж. Теория множеств и континуум-гипотеза. — M.: Мир, 1969. Глава 1. Основы математической логики, с. 13–88.

6. Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. — М.: Наука, 1975, 240 с.

7. Линдон Р. Заметки по логике. — М.: Мир, 1968, 128 с. (Современная математика. Популярная серия.)

8. Мальцев А. И. Алгоритмы и рекурсивные функции. — M.: Наука, 1965, 391 с.

9. Манин Ю. И. Доказуемое и недоказуемое. — М.: Советское радио, 1979, 167 с.

10. Манин Ю. И. Вычислимое и невычислимое. — М.: Советское радио, 1980, 128 с.

11. Мендельсон Э. Введение в математическую логику. — 2-е издание. — М: Наука, 1976, 320 с.

12. Новиков П. С. Элементы математической логики. — 2-е издание, исправленное. — М.: Наука, 1973, 399 с.

13. Роджерс X. Теория рекурсивных функций и эффективная вычислимость. — М.: Мир, 1972, 624 с.

14. Фрейденталь X. Язык логики. — М.: Наука, 1969, 135 с.

© МЦНМО, 2003
© ФИЗМАТЛИТ, 2003