1 Preface

Version: Draft B.2.e.
Sam Buss
August 14, 2023
Copyright 2022, 2023.

Эта книга представляет собой введение в пропозициональную и предикатную логику с акцентом на математическую строгость и развитие формальных доказательств. Первые главы (главы I–IV) охватывают теоремы полноты и корректности для пропозициональной и логики первого порядка. Следующие три главы посвящены алгоритмам и машинам Тьюринга, а затем излагается вторая теорема о неполноте Гёделя. Последняя, ещё не написанная, глава ?? будет посвящена теореме Гервранда в качестве дополнительной темы. Также планируется приложение — оно ещё не написано — в котором будут рассмотрены примитивно рекурсивные и частично рекурсивные функции.

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

Моя цель при написании этой книги заключалась в том, чтобы создать простое и доступное введение в классическую логику, при этом сохраняющее математическую строгость. Системы доказательств, используемые в книге, являются традиционными (обозначаемыми как “PL” и “FO”), где основными правилами вывода выступают модус поненс и правило обобщения. Безусловно, возможны и другие системы доказательств, но PL и FO, пожалуй, являются наиболее прямолинейными и традиционными. Были приложены значительные усилия, чтобы упростить изложение без ущерба для строгости. Рассматриваются только счётные языки, но в некоторых упражнениях упоминаются и несчётные.

1.1 Благодарности

Эта книга в значительной степени опирается на предыдущие учебники. В частности, я преподавал аналогичные курсы, используя книги Эндертона [5], Булоса, Бёрджесса и Джеффри [1], а также Мендельсона [13], и использовал учебник Ходела [10] как дополнительный источник при написании этой книги. Я изучал математическую логику по книге Шёнфелда [18], и это также существенно повлияло на выбор тем.

Текст был первоначально написан в ходе преподавания курса по математической логике в Калифорнийском университете в Сан-Диего осенью 2021 года и зимой 2022 года. Большая часть курса проходила очно, но некоторые занятия проводились онлайн из-за ограничений, связанных с COVID-19. Я выражаю благодарность участникам курса не только за вдохновение при написании этого текста, но и за полезные отзывы. Особая благодарность студентам Марку Барбону, Майклу Брэдли, Элайдже Камарене, Тревору Каслу, Исайе Дейли, Адриане Эррере, Чжеён Хвану, Арби Леке, Эндрю Полу, Джозефу Филлипсу, Айубу Шахморади, Кину Джеймсу Вонгу, Цзицзяну Чжану и Чжичэну Чжэну, а также ассистентам Райану Майку и Нейтану Венгеру за конкретные предложения и исправления, которые помогли улучшить текст.

Благодарю также Джеффа Эдмондса и Фредерика Мэннерса за обсуждение выбора тем. Отдельная благодарность Джонатану Аберле, Дэвиду Ауэрбаху, Алексу Блюму, Деннису Хэмилтону и Русанке Лукановой за комментарии, предложения и исправления к черновым версиям этой книги.

На данный момент это всё ещё предварительный черновик. Буду признателен за замечания и предложения по улучшению текста!

Сэм Басс
Ла-Хойя, Калифорния
Август 2023