77 Теорема Гёделя о неполноте. —М.: Наука, 1982. —112 с. —(Популярные лекции по математике).— 15 к.
Брошюра посвящена одному из наиболее замечательных достижений математической логики — теореме Гёделя о неполноте Формальной арифметики. В ней излагается доказательство теоремы Гёделя опирающееся на теорию алгоритмов. Брошюра рассчитана на школьников старших классов, студентов младших курсов и, воебше всех интересующихся логическими проблемами математики.
СОДЕРЖАНИЕ
Предисловие >..................4
§ 1. Постановка задачи............... 7
§ 2. Начальные понятия теории алгоритмов и их применения 12 § 3. Простейшие критерии неполноты . . . . . . . . .21
§ 4. Язык арифметики........... .... 25
§ 5. Три аксиомы теории алгоритмов.........33
ПРИЛОЖЕНИЯ
A. Синтаксическая и семантическая формулировки теоремы
о неполноте..................43
Б. Арифметические множества и теорема Тарского о неариф-метичпости множества истинных формул языка арифметики.....................48
B. Язык адресных программ, расширенны» арифметический язык и аксиома арифметичности..........56
8.1. Язык адресных программ..........57
8.2. Расширенный арифметический язык.......62
8.3. Выразимость адресно вычислимых функций в расширенном арифметическом языке.......68
8.4. Сведение расширенного арифметического языка к обычному.................71
8.5. Первый способ построения арифметического кодирования — способ Гёделя............76
8.6. Второй способ построения арифметического кодирования— способ Смальяна........... 78
Г. Языки, связанные с ассоциативными исчислениями . . . ?3
Д. Исторические замечания.............°9
Е. Упражнения..................94
Упражнения к § 2...............95
Упражнения к § 3.............. . 95
Упражнения к § 4.............. . 97
Упражнения к § 5...............98
Упражнения к приложению А...........100
Упражнения к приложению Б.......... . 100
Упражнения к приложению В...........101
Упражнения к приложению Г . ,............ 102
Е. Ответы и указания к упражнениям ....... ..,103
ПРЕДИСЛОВИЕ
Есть в математике темы, пользующиеся достаточной известностью и в то же время признаваемые традицией слишком сложными (или маловажными) для включения в обязательное обучение: обычай относит их к занятиям факультативным, дополнительным, специальным и т. п. В перечне таких тем есть несколько, остающихся сейчас там исключительно в силу инерции. Одной из них является теорема Гёделя.
Несмотря на то, что очень многие математики (и нематематики) слышали о ней, мало кто из них может объяснить, в чем состоит утверждение теоремы Гёделя и тем более как она доказывается. Вместе с тем результат столь важен, а причины, вызывающие неустранимую неполноту (т. е. невозможность добиться того, чтобы каждое истинное утверждение было доказуемо), столь просты, что теорема Гёделя могла бы излагаться на самых младших курсах. Более того, для понимания доказательства необходимо лишь знакомство с простейшей терминологией теории множеств (словами «множество», «функция», «область определения» и тому подобными) и некоторая привычка к восприятию математических рассуждений, так что оно вполне доступно подготовленному школьнику.
Излагаемый в этой брошюре способ доказательства теоремы Гёделя отличен от способа, предложенного самим Гёделем, и опирается на элементарные понятия теории алгоритмов. Все необходимые сведения из этой теории сообщаются по ходу дела, так что читатель одновременно знакомится с основными фактами теории алгоритмов. Брошюра написана на основе статьи автора в журнале «Успехи математических наук», 1974, том 29, выпуск 1 (175), Естественно, что изменение круга предполагаемых читателей сделало
4
необходимой ее переработку. В частности, некоторые более специальные вопросы, а также библиографические ссылки на оригинальные публикации исключены, и любознательный читатель может найти их в упомянутой статье автора. Одновременно расширен раздел, посвященный связи между семантической и синтаксической формулировками теоремы о неполноте, а также добавлены приложения, посвященные теореме Тарско-го о невыразимости понятия истины и обоснованию аксиомы арифметичности.
План брошюры таков. В § 1 формулируется теорема о неполноте и уточняется ее формулировка, в частности вводится центральное для данной брошюры понятие дедуктики. В § 2 излагаются на неформальном уровне начальные понятия теории алгоритмов, и на их основе формулируются первые критерии полноты и неполноты. В § 3 продолжается исследование критериев неполноты. В § 4 описывается язык формальной арифметики, дается точное определение понятия истинности утверждения этого языка и точная формулировка теоремы Гёделя о неполноте для формальной арифметики. В § 5 на основе дальнейшего развития тех представлений об алгоритмах, которые были описаны в § 2, — развития, закрепляемого в виде трех аксиом теории алгоритмов, — завершается доказательство теоремы о неполноте формальной арифметики.
Брошюра снабжена шестью приложениями, написанными несколько более сжато, хотя по-прежнему не предполагающими никаких специальных знаний. В первом из них рассматривается вопрос о связи между наличием истинных недоказуемых утверждений и наличием утверждений, не являющихся ни доказуемыми, ни опровержимыми. Во втором доказывается некоторое усиление теоремы Гёделя — теорема Тарского о невыразимости понятия истины. Третье приложение посвящено обоснованию одной из аксиом теории алгоритмов, сформулированных в § 5, а именно, аксиомы арифметичности. С этой целью вводится некоторый конкретный класс алгоритмов — класс адресных программ— и проверяется арифметичность функций, вычисляемых алгоритмами этого класса. В четвертом приложении развитые в § 2 критерии полноты и неполноты применяются к языкам, связанным с так
Цена: 150руб.
