Читать онлайн «Теорема Геделя о неполноте»
Автор Владимир Успенский
ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ
ВЫПУСК 57
В. А. УСПЕНСКИЙ
ТЕОРЕМА ГЁДЕЛЯ
О НЕПОЛНОТЕ
МОСКВА «НАУКА»
ГЛАВНАЯ РЕДАКЦИЯ
ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ
1982
22. 12
У 77
УДК 517. 11
Успенский В. А. У 77 Теорема Гёделя о неполноте. — М/. Наука, 1982. — 112 с.
— (Популярные лекции по математике). — 15 к. Брошюра посвящена одному из наиболее замечательных до-
стижений математической логики — теореме Гёделя о неполно-
те формальной арифметики. В ней излагается доказательство
теоремы Гёделя, опирающееся на теорию алгоритмов. Брошюра
рассчитана на школьников старших классов, студентов млад-
ших курсов и, вообше, всех интересующихся логическими про-
блемами математики. У 1702020000−021
053(02)−82
82 − 81
ББК 22. 12
517. 8
У 1702020000−021
053(02)−82
82 − 81
Издательство «Наука»
Главная редакция
физико-математической
литературы, 1982
Содержание
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . 4
§1. Постановка задачи . . . . . . . . . . . . . . . . . . 7
§2. Начальные понятия теории алгоритмов и их при-
менения . . . . . . . . . . . . . . . . . . . . . . . . 11
§3. Простейшие критерии неполноты . . . . . . . . . 21
§4. Язык арифметики . . . . . . . . . . . . . . . . . . 24
§5. Три аксиомы теории алгоритмов . . . . . . .
. . 31
ПРИЛОЖЕНИЯ 43
A. Синтаксическая и семантическая формулировки
теоремы о неполноте . . . . . . . . . . . . . . . . 45
Б. Арифметические множества и теорема Тарского о
неарифметичности множества истинных формул
языка арифметики . . . . . . . . . . . . . . . . . . 49
В. Язык адресных программ, расширенный арифмети-
ческий язык и аксиома арифметичности . . . . . 57
В. 1. Язык адресных программ . . . . . . . . . . . 59
В. 2. Расширенный арифметический язык . . . . . 64
В. 3. Выразимость адресно вычислимых функций
в расширенном арифметическом языке . . 70
В. 4. Сведение расширенного арифметического язы-
ка к обычному . . . . . . . . . . . . . . . . 73
В. 5. Первый способ построения арифметического
кодирования — способ Гёделя . . . . . . . 77
В. 6. Второй способ построения арифметического
кодирования — способ Смальяна . . . . . 80
Г. Языки, связанные с ассоциативными исчислениями 85
Д. Исторические замечания . . . . . . . . . . . . . . . 91
Е.
