Математическая логика

Ершов Ю.Л.
Палютин Е.А.

Математическая

логика

МОСКВА

ФИЗМАТЛИТ ®

УДК 510.6(075.8)
ББК 22.12
Е 80

Е р ш о в Ю. Л., П а л ю т и н Е. А. Математическая логика. — 6-е изд.,
испр. — М.: ФИЗМАТЛИТ, 2011. — 356 с. — ISBN 978-5-9221-1301-4.

В книге изложены основные классические исчисления математической
логики: исчисление высказываний и исчисление предикатов; имеется краткое
изложение основных понятий теории множеств и теории алгоритмов. Ряд
разделов книги — теория моделей и теория доказательств — изложены более
подробно, чем это предусмотрено программой.
Для студентов математических специальностей вузов. Может служить
пособием для специальных курсов.
Рекомендовано УМС по математике и механике УМО по классическому
университетскому образованию РФ в качестве учебного пособия для студентов
высших учебных заведений, обучающихся по направлениям и специальностям:
«Математика», «Прикладная математика и информатика», «Механика».

Учебное издание

ЕРШОВ Юрий Леонидович
ПАЛЮТИН Евгений Андреевич

МАТЕМАТИЧЕСКАЯ ЛОГИКА

Редактор И.Л. Легостаева
Оригинал-макет: И.Г. Андреева
Оформление переплета: Д.Б. Белуха

Подписано в печать 26.01.11. Формат 6090/16. Бумага офсетная. Печать офсетная.
Усл. печ. л. 22,25. Уч.-изд. л. 24,75. Тираж экз. Заказ №

Издательская фирма «Физико-математическая литература»
МАИК «Наука/Интерпериодика»
117997, Москва, ул. Профсоюзная, 90
E-mail: fizmat@maik.ru, fmlsale@maik.ru;
http://www.fml.ru

Отпечатано в ГУП
«ИПК Чувашия», 428019
г. Чебоксары, пр-т И.Яковлева, 13

ISBN 978-5-9221-1301-4

ISBN 978-5-9221-1301-4

c⃝ ФИЗМАТЛИТ, 2011

c⃝ Ю. Л. Ершов, Е. А. Палютин, 2011

ОГЛАВЛЕНИЕ

Предисловие к шестому изданию . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
5

Предисловие к первому изданию . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
6

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
8

Г л а в а 1.
Исчисление высказываний . . . . . . . . . . . . . . . . . . .. .. .. .
13
§ 1.1. Множества и слова . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
13
§ 1.2. Язык исчисления высказываний . . . . . . . . . . .. . . . . . . . . . .. .. .. .
17
§ 1.3. Система аксиом и правил вывода . . . . . . . . . . .. . . . . . . . . .. .. .. .
22
§ 1.4. Эквивалентность формул. . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
29
§ 1.5. Нормальные формы . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
32
§ 1.6. Семантика исчисления высказываний . . . . . . . . . . . . . . . . .. .. .. .
38
§ 1.7. Характеризация доказуемых формул . . . . . . . . .. . . . . . . . . .. .. .. .
43
§ 1.8. Исчисление высказываний гильбертовского типа. . . . . . . . . .. .. .. .
46
§ 1.9. Консервативные расширения исчислений . . . . . . .. . . . . . . . .. .. .. .
50

Г л а в а 2.
Теория множеств . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
60
§ 2.1. Предикаты и отображения. . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
60
§ 2.2. Частично упорядоченные множества . . . . . . . . .. . . . . . . . . .. .. .. .
65
§ 2.3. Фильтры булевой алгебры . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
75
§ 2.4. Мощность множества . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
80
§ 2.5. Ординалы и кардиналы. . . . . . . . . . . . . . .. . . . . . . . . . . . .. .. .. .
81
§ 2.6. Аксиоматическая теория множеств ZF и аксиома выбора. . . .. .. .. .
87

Г л а в а 3.
Истинность на алгебраических системах . . . . . . . . .. .. .. .
93
§ 3.1. Алгебраические системы . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
93
§ 3.2. Формулы сигнатуры Σ . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
99
§ 3.3. Теорема компактности . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
107

Г л а в а 4.
Исчисление предикатов . . . . . . . . . . . . . . . . . . . . .. .. .. .
114
§ 4.1. Аксиомы и правила вывода . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
114
§ 4.2. Эквивалентность формул. . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
122
§ 4.3. Нормальные формы . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
126
§ 4.4. Теорема о существовании модели . . . . . . . . . . . . . . . . . . . .. .. .. .
128
§ 4.5. Исчисление предикатов гильбертовского типа. . . . . . . . . . . .. .. .. .
135
§ 4.6. Чистое исчисление предикатов. . . . . . . . . . .. . . . . . . . . . . .. .. .. .
139

Оглавление

Г л а в а 5.
Теория моделей . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
144
§ 5.1. Элементарная эквивалентность. . . . . . . . . . . . . . . . . . . . . .. .. .. .
144
§ 5.2. Аксиоматизируемые классы . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
152
§ 5.3. Скулемовские функции . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
161
§ 5.4. Механизм совместности . . . . . . . . . . . . . .. . . . . . . . . . . . .. .. .. .
163
§ 5.5. Счетная однородность и универсальность. . . . . . . . . . . . . . .. .. .. .
175
§ 5.6. Категоричность . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .. .. .. .
182
§ 5.7. RQ-формулы и Σ-формулы . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
191
§ 5.8. Формульная определимость . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
202
§ 5.9. Позитивные формулы и монотонные операторы . . . . . . . . . . .. .. .. .
209

Г л а в а 6.
Теория доказательств. . . . . . . . . . . . . . . . . . . . . . .. .. .. .
215
§ 6.1. Генценовская система G . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
215
§ 6.2. Обратимость правил. . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
220

§ 6.3. Сравнение исчислений ИПΣ и G . . . . . . . . . . . . . . . . . . . .. .. .. .
225
§ 6.4. Теорема Эрбрана . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . .. .. .. .
232
§ 6.5. Исчисления резольвент. . . . . . . . . . . . . .. . . . . . . . . . . . . .. .. .. .
245

Г л а в а 7.
Вычислимость . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
251
§ 7.1. Понятие алгоритма. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . .. .. .. .
251
§ 7.2. Σ-предикаты и Σ-функции на Ω . . . . . . . . . . . . . . . . . . . . .. .. .. .
252
§ 7.3. Σ-определимость истинности Σ-формул на Ω . . . . . . . . . . . .. .. .. .
265
§ 7.4. Универсальные Σ-предикаты, универсальные частичные Σ-функции
277
§ 7.5. Теорема Чёрча и теорема Гёделя о неполноте . . . . . .. . . . . . .. .. .. .
283
§ 7.6. Машины Тьюринга. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . .. .. .. .
294
§ 7.7. Рекурсивные функции . . . . . . . . . . . . . . .. . . . . . . . . . . . .. .. .. .
297

Г л а в а 8.
Разрешимые и неразрешимые теории . . . . . . . . . . .. .. .. .
300
§ 8.1. Разрешимость теории одноместных предикатов. . . . . . . . . . .. .. .. .
300
§ 8.2. Элиминация кванторов и разрешимость теории алгебраически замкнутых полей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
303
§ 8.3. Элиминация кванторов и разрешимость теории вещественно замкнутых полей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
308
§ 8.4. Разрешимые теории абелевых групп . . . . . . . . . . . . . . . . . .. .. .. .
311
§ 8.5. Теории декартовых произведений . . . . . . . . . .. . . . . . . . . . .. .. .. .
328
§ 8.6. Неразрешимые теории . . . . . . . . . . . . . . .. . . . . . . . . . . . .. .. .. .
332

Предметный указатель . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . .. .. .. .
343

Указатель обозначений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
352

Предисловие к шестому изданию

Это издание является переработкой и дополнением 2-го издания
(издания 3–5 являются стереотипными). Изменения коснулись всех
глав книги. Наибольшей корректировке подверглась глава 7, на основании которой сформирована глава 8. В частности, за основу изложения
теории вычислимости выбрано понятие Σ-определимости. Этот подход
поможет естественному освоению теории вычислимости на допустимых
множествах.
Изменения относятся как к дополнениям материала, так и к более
подробному изложению мест в доказательствах, которые ранее были
более схематичны.
Благодарим С. В. Судоплатова за полезные замечания и помощь
в подготовке рукописи к изданию, а также М. А. Русалеева за компьютерный набор текста.
Настоящее шестое издание книги является первым в издательстве
«ФИЗМАТЛИТ».

Май 2010 г.
Ю. Л. Ершов
Е. А. Палютин

Предисловие к первому изданию

Настоящая книга представляет собой систематическое изложение
ряда разделов современной математической логики и теории алгоритмов. Написана она с целью использования ее в преподавании как
в качестве учебника по математической логике для университетов, так
и в качестве учебного пособия при чтении спецкурсов.
Разделы, соответствующие обязательной программе (§ 1–9 в гл. 1
(без мелкого шрифта), § 10–11 в гл. 2, § 15–16 в гл. 3, § 18–20, 22–23
в гл. 4 и § 35 в гл. 7), написаны более тщательно и подробно, чем
разделы, относящиеся к более специальным вопросам.
Изложение исчисления высказываний и исчисления предикатов не
является традиционным и начинается с изучения секвенциальных вариантов исчислений натурального вывода (хотя традиционные исчисления также появляются здесь под названием гильбертовских). Основанием к этому являются:

1) возможность хорошего объяснения смысла всех правил вывода;
2) возможность более быстрого приобретения навыка формальных
доказательств;
3) практическая возможность проделать все необходимые в курсе
формальные доказательства в таких исчислениях.

Многолетний опыт чтения старшим из авторов курса математической логики на математическом факультете Новосибирского государственного университета, на основе которого написаны главы 1–4, показывает, что указанные выше возможности вполне реализуются. Это
оправдывает использование такого способа изложения наряду с традиционными.
Более подробные сведения о содержании книги можно получить из
ее оглавления.
Ввиду учебного характера книги, несмотря на названия «Теория
множеств», «Теория моделей», «Теория доказательств» и «Алгоритмы
и рекурсивные функции», соответствующие главы, конечно, содержат
лишь малую часть содержания этих больших разделов современной
математической логики. Как и принято в учебниках, большинство
результатов приведено в данной книге без указания авторов.
В тексте имеется небольшое число упражнений почти после каждого параграфа книги. Однако этих упражнений явно недостаточно для
учебных целей. Мы рекомендуем использовать в качестве задачника
для данного курса следующий: Лавров И. А., Максимова Л. Л. Задачи

Предисловие к первому изданию
7

по теории множеств, математической логике и теории алгоритмов. —
М.: Наука, 1984. 1)
Сделаем несколько замечаний технического порядка. Нумерация
теорем — сквозная по главам, нумерация предложений и лемм —
своя в каждом параграфе. Выражение «предложение 12.2» («теорема 12.2», ...) означает «предложение 2 (теорема 2, ...) из § 12». При
ссылке на предложения и леммы внутри одного параграфа и часто при
ссылке на теоремы внутри одной главы параграф не указывается. Символ «=⇒» является сокращением для выражения «из ... следует ...»,
символ «⇐⇒» является сокращением для выражения «... равносильно ...». Символ «□» указывает на окончание доказательства.
Создание этой книги не было бы возможно без коллектива кафедры
алгебры и математической логики Новосибирского государственного
университета. Основатель этой кафедры — выдающийся советский математик академик А. И. Мальцев (1909–1967) — оказал решающее влияние на формирование научных интересов и педагогических взглядов
авторов. На разных этапах подготовки настоящей книги большую помощь и поддержку мы получали от М. И. Каргаполова, Н. В. Белякина,
И. А. Лаврова, Л. Л. Максимовой и многих других. Этим коллегам и
товарищам мы выражаем свою искреннюю признательность и благодарность.
При работе над данной книгой были использованы записи курсов
лекций А. И. Мальцева и Ю. Л. Ершова, книги: Ершов Ю. Л., Палютин Е. А., Тайцлин М. А. Математическая логика. — Новосибирск:
Изд-во НГУ, 1973; Куратовский К., Мостовский А. Теория множеств. — М.: Мир, 1970; Мальцев А. И. Алгебраические системы. —
М.: Наука, 1970; Марков А. А. Теория алгорифмов. — М.: Изд-во АН
СССР, 1954; Шенфилд Дж. Математическая логика. — М.: Наука,
1975, а также другие монографии и научные статьи.

Новосибирск
Академгородок
Ю. Л. Ершов
Е. А. Палютин

1) Последнее издание — M.: ФИЗМАТЛИТ, 2009. (Прим. ред.)

Введение

Математическая логика как самостоятельный раздел современной
математики сформировалась сравнительно недавно — на рубеже девятнадцатого — двадцатого веков. Возникновение и быстрое развитие
математической логики в начале двадцатого века было связано с так
называемым кризисом в основаниях математики. Поговорим об этом
чуть подробнее.
При любой попытке систематического изложения математики (как,
впрочем, и любой другой науки) возникает проблема выбора начальных
(исходных) понятий и принципов, которые будут положены в основу
всего изложения. Проблема выбора и обоснование этого выбора исходных данных лежит, как правило, вне самой научной дисциплины
и относится к философии и методологии научного познания. Систематизация математики в конце девятнадцатого века выявила, что весьма
перспективным является использование понятия множества в качестве единственного исходного понятия для всей математики. Работами
Б. Больцано, Р. Дедекинда и Г. Кантора была создана новая область
математики — теория множеств, которая красотой и силой своих построений и перспективами использования ее в основаниях математики
привлекла внимание многих ведущих математиков того времени. Была
проделана большая работа по теоретико-множественному осмыслению
математических и даже логических понятий. В этой связи большой
интерес представляют исследования Г. Фреге и Б. Рассела. Однако высокая степень абстрактности и «универсальность» понятия множества
не могли не привести в конце концов к трудностям, хорошо и давно известным в философии при работе с «универсалиями». Проявилось это
в появлении так называемых теоретико-множественных парадоксов.
Приведем один из наиболее типичных теоретико-множественных
парадоксов — парадокс Рассела. Для произвольного множества является вполне осмысленным вопрос, «будет ли это множество своим
элементом». Примером множества, которое содержит само себя в качестве элемента, могло бы служить, например, множество всех множеств.
Рассмотрим множество M0 всех множеств, для которых ответ на этот
вопрос отрицателен. Спросим теперь, является ли это множество своим
элементом? К своему (наивному) удивлению обнаружим, что если ответ
положительный, то имеем M0 /∈ M0, т. е. ответ должен быть отрицательным. Если же ответ отрицателен, то в силу определения множества
M0 ответ должен быть положительным. Этот парадокс показывает,
что если мы не хотим приходить к противоречиям, то необходимо
отказаться от приятной мысли, что любое осмысленное условие на

Введение
9

элементы определяет некоторое множество. К счастью, такого рода парадоксы можно получить лишь с «большими» или «неестественными»
множествами, без которых в математике можно вполне обойтись 1).
Появление таких парадоксов в теории множеств было воспринято
многими математиками очень болезненно и поэтому привлекло к вопросам оснований математики пристальное внимание практически всех
ведущих математиков того времени (назовем, к примеру, Д. Гильберта,
А. Пуанкаре, Г. Вейля). Было предложено несколько программ «спасения» математики от «ужаса» парадоксов, входить в детали которых
мы не будем. Укажем вкратце только две наиболее действенные программы, различные модификации которых обсуждаются и в настоящее
время. Отметим, что многообразие подходов к основаниям математики
остается и поныне. Однако прошедшие годы и безусловные достижения
математической логики, речь о которых еще впереди, сняли остроту
этой проблемы настолько, что большинство математиков, работающих
в других разделах математики, не уделяют особого внимания тем дискуссиям, которые ведут ныне специалисты по основаниям математики.
Одной из наиболее разработанных программ по основаниям математики является предложенная Д. Гильбертом программа финитарного
обоснования математики. Суть этой программы состоит в попытке
построения такой формализации математики, что средствами этой системы можно доказать свою собственную непротиворечивость. Другим
принципиальным требованием к такой формализации является условие, чтобы все простейшие, проверяемые непосредственно утверждения
о натуральных числах были истинными в этой формализации. Работа
над этой программой как самого Гильберта, так и его учеников и последователей оказалась весьма плодотворной для математической логики,
в частности, в разработке современного аксиоматического метода. Хотя
программа «финитизма» в своей исходной постановке оказалась невыполнимой, как показал в своих знаменитых работах К. Гёдель, однако
возможные модификации этой программы подвергаются полезному обсуждению и до настоящего времени.
Другой подход к основаниям математики был связан с критикой
ряда положений, которые использовались в математике без должного
обоснования. Это относится, в частности, к неограниченному использованию закона исключенного третьего и аксиомы выбора. Программа
построения математики при жестких ограничениях на использование
этих принципов получила название интуиционизма; ее создание и
развитие связано в первую очередь с именем Л. Э. Я. Брауэра. Развитый

1) Упоминаемые ниже формализации теории множеств — аксиоматические
теории множеств, — сохраняя все полезное, не допускают прямого проведения
всех известных «парадоксальных» рассуждений.

Введение

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

1. Явная формулировка исходных положений (аксиом) той или иной
теории.
2. Явная формулировка логических средств (правил вывода), которые допускаются для последовательного построения (развертывания) этой теории.
3. Использование искусственно построенных формальных языков
для изложения всех положений (теорем) рассматриваемой теории.

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