книги из ГПНТБ / Новиков П.С. Элементы математической логики

ЭЛЕМЕНТЫ

МАТЕМАТИЧЕСКОЙ

ЛОГИКИ

П. С. НОВИКОВ

И З Д А Н И Е В Т О Р О Е , И С П Р А В Л Е Н Н О Е

М О С К В А 1 9 7 3

ОГЛАВЛЕНИЕ

§1. Предикаты (123). § 2. Кванторы (128). § 3. Теоретико-

нечные и бесконечные области (168). § 13. Разрешающие функ­

§ 1. Формулы исчисления предикатов (183). § 2. Замена пере­ менных в формулах (190). § 3. Аксиомы исчисления предика­ тов (192). § 4. Правила образования выводимых формул (193).

\

ПРЕДИСЛОВИЕ КО ВТОРОМУ ИЗДАНИЮ

Интенсивное развитие математической логики в послед­ нее время сопровождается увеличением ее роли в мате­ матике.

Одной из основных задач математической логики ос­ тается анализ оснований математики. Но в настоящее время она уже вышла из рамок этой задачи и оказала существенное влияние на развитие самой математики. Из ее идей возникло точное определение понятия алго­ ритма, что позволило решить многие вопросы, которые без этого оставались бы в принципе неразрешимыми. Возникший в математической логике аппарат нашел при­ ложение в вопросах конструкций вычислительных машин и автоматических устройств.

Со времени выхода в свет первого издания настоя­ щей книги прошло 14 лет. За это время задача ознаком­ ления широкого круга математиков с основами матема­ тической логики стала еще более актуальной. В настоя­ щей книге была сделана попытка дать по возможности доступное изложение основ математической логики. Этой задаче посвящены первые пять глав книги, составляю­ щие ее основное содержание. Последняя, шестая, глава носит более специальный характер и уже не является столь элементарной. В ней рассматриваются методы тео­ рии доказательства, посредством которых решаются не­ которые вопросы математической логики, возникающие в основном тексте книги.

8 П Р Е Д И С Л О В И Е КО В Т О Р О М У И З Д А Н И Ю

Настоящее издание по содержанию не отличается от первого издания. В нем исправлены опечатки и заменены устаревшие термины. В частности, удален термин «ис­ тинная в данном исчислении формула», который в пер­ вом издании использовался как синоним термина «вы­ водимая в данном исчислении формула». Таким обра­ зом, исключена возможность смешения этого понятия с содержательной истинностью формул.

Книга не претендует на полноту освещения всех раз­ вивающихся в настоящее время важных направлений в математической логике. Некоторые из этих направлений не затронуты вовсе. С разделами математической логики, которые не отражены в настоящей книге, читатель смо­

ин-та АН СССР им. В. А. Стеклова, Изд-во АН СССР,

1954.

Э. М е н д е л ь с о н , Введение в математическую ло­ гику, «Наука», 1971.

П. С. Новиков

ВВЕДЕНИЕ

В современной математике большое распространение получил так называемый аксиоматический метод. Источ­ ником его следует считать открытие Лобачевским неев­ клидовой геометрии. К настоящему времени аксиомати­ ческий метод прошел большую эволюцию, придя в со­ прикосновение с другими идеями, и породил не только новые методы, но и новые принципы математического мышления. Развитие аксиоматического метода можно разбить на два этапа. Первый продолжается от Лоба­ чевского до работ Гильберта по основаниям матема­ тики*), второй — от этих работ Гильберта до наших дней. Этот второй этап представляет собой соединение идей, идущих из геометрии, с развивавшимся параллель­ но учением, известным под названием «символической» или «математической» логики. В результате возникла новая дисциплина, сохранившая название математиче­ ской логики.

Прежде чем говорить о самой математической ло­ гике, мы рассмотрим вкратце предшествующее ей состояние аксиоматического метода и постараемся уяс­ нить, хотя "бы в самых общих чертах, причины возникно­ вения этого метода и стоящие перед ним задачи. Сущ­ ность аксиоматического метода состоит в своеобразном способе определить математические объекты и отношения между ними. Предположим, что, изучая систему ка­ ких-то объектов, мы употребляем определенные термины," выражающие свойства этих объектов и отношения между ними. При этом мы не определяем ни сами объ­ екты, ни эти свойства и отношения, а высказываем ряд

10 В В Е Д Е Н И Е

определенных утверждений, которые должны для них вы­ полняться. Очевидно, эти утверждения выделяют из все­ возможных систем объектов, их свойств и отношений меж­ ду ними такие системы, для которых они выполнены.

Таким образом, сделанные утверждения можно рас­ сматривать как определения системы объектов опреде­ ленного класса, их свойств и отношений между ними.

Рассмотрим простой пример, с которым нам и в дальнейшем часто придется встречаться. Пусть дана си­ стема каких-то объектов, которые мы будем обозначать буквами латинского алфавита, и между ними установ­ лено отношение, выражаемое термином «предшествует».

с таким отношением между ними, что если под терми­

Или объектами являются действительные числа, а от­ ношение «х предшествует у» представляет собой «х мень­ ше у». Здесь утверждения 1 и 2, очевидно, также вы­ полнены.

Системы объектов с одним отношением, для которых положения 1 и 2 выполнены, образуют определенный класс, а положения 1 и 2 мы можем рассматривать как определение систем этого класса. Утверждения, посред­ ством которых мы таким образом выделяем совокуп­ ность объектов, носят названием аксиом. Если для какойлибо совокупности объектов, их свойств и отношений некоторые аксиомы истинны, то говорят, что данная со­ вокупность объектов удовлетворяет системе этих аксиом, или является интерпретацией данной системы аксиом.

Делая логические выводы из аксиом, мы будем полу­ чать утверждения, истинные для любой системы объек­ тов, удовлетворяющей данным аксиомам.