ББК 22.12 Е80 УДК 510.6 (075.8) Ершов Ю. Л., Палютин Е, А. Математическая логика: Учеб. пособие для вузов.— 2-е изд., нспр. и доп.— М.; Наука. Гл. ред. физ.-мат. лит., 1987.— 336 с. В книге изложены основные классические исчисления мате- матической логики: исчисление высказываний и исчисление пре- дикатов; имеется.. краткое изложение основных понятий теории множеств и теории алгоритмов. Ряд разделов книги — теория мо- делей и теория доказательств — изложены более подробно, чем это предусмотрено программой. Для студентов математических специальностей вузов. Может служить пособием для спецкурсов. Рецензент член-корреспондент АН СССР О. Б. Лупанов Юрий Леонидович Ершов Евгений Андреевич Палюгин МАТЕМАТИЧЕСКАЯ ЛОГИКА Редактор В, В. Донченко Художественный редактор Г. II. Колъчеико Технический редактор В, Н. Кондакова Корректоры Г. В, Подвольская, М, Л. Медеедская ИВ М 12972 Сдано в набор 21,05.86. Подписано к печати 16.02.87. Формат 84х108/32. Бумага тип. Ж.!. Гарнитура обыкновенная новая. Печать высокая. Усл. печ. л. 17,64, Уел, кр.-отт. 17,64. Уч.-изд. л. 19,38. Тираж 30 000 эка, Заказ .N1 218. Цена 95 коп, Ордена Трудового Красного Знамени издательство «Наука» Главная редакция физико-математической литературы 117071 Москва В-71, Ленинский проспект, 15 4-я типография издательства «Натка» 630077 г, Новосибирск 77, Станиславского, 25 g 1702020000—069 go n, 053(02)-87 ©Издательство «Наука». Главная редакция физико-математической литературы, 1879; с изменениями и дополнениями, 1981 ОГЛАВЛЕНИЕ Предисловие ко второму изданию ....... Предисловие 'к первому изданию ....... Введение , i ,. . ••.•••••• Глава 1. Исчисление высказываний ..... § 1. Множества и слова ........ § 2. Язык исчисления высказываний ..... § 3. Система аксиом и правил вывода .... § 4. Эквивалентность формул ....... § 5. Нормальные формы ........ § 6. Семантика исчисления высказываний § 7. Характеризация доказуемых формул § 8. Исчисление высказываний гильбертовского типа § 9. Консервативные расширения исчислений , Глава 2. Теория множеств ........ § 10. Предикаты и отображения ...... § 11. Частично упорядоченные множества § 12. Фильтры булевой алгебры ...... § 13. Мощность множества ........ § 14. Аксиома выбора ......... Глава 3. Истинность на алгебраических системах § 15. Алгебраические системы . . .... § 16. Формулы сигнатуры S ....... § 17. Теорема компактности . . ..... Глава 4. Исчисление предикатов , ..... § 18. Аксиомы и правила вывода ...... § 19. Эквивалентность формул . . .... § 20. Нормальные формы ........ § 21. Теорема о существовании модели .... § 22. Исчисление предикатов гильбертовского типа § 23. Чистое исчисление предикатов , . , . . Глава 5. Теория моделей . . ...... § 24. Элементарная эквивалентность ..... § 25. Аксиоматизируемые классы ...... § 20. Скулемовские функции ....... § 27. Механизм совместности ....... § 28. Счетная однородность и универсальность § 29, Категоричность ,...,...< Г 4 ОГЛАВЛЕНИЕ Глава 6. Теория доказательств § 30. Генценовская система G § 31. Обратимость правил .... § 32. Сравнение исчислений ИТР и G § 33. Теорема Эрбрапа ..... § 34. Исчисления резольвент , Глава 7. Алгоритмы и рекурсивные функции . , , , § 35. Нормальные алгорифмы и машины Тьюринга , § 36. Рекурсивные функции ........ § 37. Рекурсивно перечислимые предиката .... § 38. Неразрешимость исчисления предикатов и теорема Гёделя о неполноте ......... § 39. Разрешимые теории ......,., § 40. Неразрешимые теории ,.....,. Предметный указатель ........... 204 204 209 214 222 233 241 241 251 2G8 281 296 318 335 ПРЕДИСЛОВИЕ КО ВТОРОМУ ИЗДАНИЮ При подготовке нового издания значительной перера- ботке подверглась глава 6, имевшая ранее серьезные по- грешности. К главе 7 добавлены два новых параграфа (§ 39. Разрешимые теории и § 40. Неразрешимые тео- рии). Незначительные изменения сделаны и по осталь- ному тексту: исправлены замеченные опечатки и мелкие погрешности, сделаны небольшие добавления. Авторы благодарны коллегам, конструктивная крити- ка которых способствовала улучшению книги. ПРЕДИСЛОВИЕ К ПЕРВОМУ ИЗДАНИЮ Настоящая книга представляет собой систематическое пзложегше ряда разделов современной математической логики и теории алгоритмов. Написана она с целью ис- пользования ее в преподавании как в качестве учебника по математической логике для университетов, так и в качестве учебного пособия при чтении спецкурсов. Разделы, соответствующие обязательной программе (§ 1—9 в главе 1 (без мелкого шрифта), § 10—11 п главе 2, § 15-16 в главе 3, § 18-20, 22-23 в главе 4 и § 35 в главе 7), написаны более тщательно и подроб- но, чем разделы, относящиеся к более специальным во- просам. Изложение исчисления высказываний и исчисления предикатов не является традиционным и начинается с изучения секвенциальных вариантов исчислений нату- рального вывода (хотя традиционные исчисления также появляются здесь под названием гильбертовских). Осно- ванием к этому являются: 1) возможность хорошего объяснения смысла всех правил вывода; 2) возможность более быстрого приобретения навыка формальных доказательств; 3) практическая возможность проделать все необхо- димые в курсе формальные доказательства в таких ис- числениях. Многолетний опыт чтения старшим из авторов курса математической логики на математическом факультете НГУ, на основе которого написаны главы 1—4, показы- вает, что указанные выше возможности вполне реализу- ются. Это оправдывает использование такого способа из- ложения наряду с традиционными. Более подробные сведения о содержании книги мож- но получить из ее оглавления. Ввиду учебного характера книги, несмотря на назва- ния «Теория множеств», «Теория моделей», «Теория до- казательств» и «Алгоритмы и рекурсивные функции», ПРЕДИСЛОВИЕ 7 соответствующие главы, конечно, содержат лишь малую часть содержания этих больших разделов современной математической логики. Как и принято в учебниках, большинство результатов приведено в даннои книге без указания авторов. В тексте имеется небольшое число упражнений почти после каждого параграфа книги. Однако этих упражне- ний явно недостаточно для учебных целей. Мы рекомен- дуем использовать в качестве задачника для данного курса следующий: Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов.— М.: Наука, 1984. Для облегчения пользования книгой укажем схему зависимости глав: 4 Сделаем несколько замечаний технического порядка. Нумерация теорем сквозная по главам, нумерация пред- ложений и лемм своя в каждом параграфе. Выражение «предложение 12.2» («теорема 12.2», ...) означает «пред- ложение 2 (теорема 2, ...) из § 12». При ссылке на предложения и леммы внутри одного параграфа и часто при ссылке на теоремы внутри одной главы параграф не указывается. Символ е> является сокращением для вы- ражения «из... следует ...», символ •ф!> является сокра- щением для выражения «... равносильно ...», Символ D указывает на окончание доказательства. Создание этой книги не было бы возможно без кол- лектива кафедры алгебры и математической логики Но- восибирского государственного университета. Основатель этой кафедры — выдающийся советский математик ака- демик А. И. Мальцев, (1909—1967)—оказал решающее влияние на формирование научных интересов и педаго- гических взглядов авторов. На разных этапах подготовки настоящей книги большую помощь и поддержку мы по- лучали от М. И. Каргаполова, Н. В. Белякина, И. А. Лав- рова, Л. Л. Максимовой и многих других. Этим коллегам и товарищам мы выражаем свою искреннюю признатель- ность и благодарность. При работе над данной книгой были использованы ваписи курсов лекций А. И. Мальцева и Ю. Л. Ершова, 8 ПРЕДИСЛОВИЕ книги: Ершов Ю. Л, Палютин Е. А., Тайц- лин М. А. Математическая логика.—Новосибирск; Иэд-во НГУ, 1973; Куратовский К., Мостов- скии А. Теория множеств.—М.: Мир, 1970; Маль- цев А. И. Алгебраические системы.—М.: Наука, 1970; Марков А. А. Теория алгорифмов.—М.: Изд-во АН СССР, 1954; Шенфилд Дж. Математическая логика.— М.: Наука, 1975, а также другие монографии и научные статьи. Нииисибирск . Академгородок Ю. Л. Ершов Е, А, Палютин ВВЕДЕНИЕ Математическая логика как самостоятельный раздел современной математики сформировалась сравнительно недавно — на рубеже девятнадцатого — двадцатого веков. Возникновение и быстрое развитие математической логи- ки в начале нашего века было связано с так называемым кризисом в основаниях математики. Поговорим об этом чуть подробнее. При любой попытке систематического изложения ма- тематики (как, впрочем, и любой другой науки) возни- кает проблема выбора начальных (исходных) понятий и принципов, которые будут положены в основу всего из- ложения. Проблема выбора и обоснование этого выбора исходных данных лежит, как правило, вне самой науч- ной дисциплины и относится к философии и методологии научного познания. Систематизация математики в конце девятнадцатого века выявила, что весьма перспективным является использование понятия множества в качестве единственного исходного понятия для всей математики. Работами Б. Больцано, Р. Дедекинда и Г. Кантора была создана новая область математики — теория множеств, которая красотой и силой своих построений и перспек- тивами использования ее в основаниях математики при- влекла внимание многих ведущих математиков того времени. Была проделана большая работа по теоретико- множественному осмыслению математических и даже логических понятий. В этой связи большой интерес пред- ставляют исследования Г. Фреге и Б. Рассела. Однако высокая степень абстрактности и «универсальность» по- нятия множества не могли не привести в конце концов .к трудностям, хорошо и давно известным в философии при работе с «универсалиями». Проявилось это в появ- лении так называемых теоретико-множественных пара- доксов. Приведем один из наиболее типичных теоретико-мно- жественных парадоксов — парадокс Рассела. Для произ- вольного множества является вполне осмысленным вс- 10 ВВЕДЕНИЕ прос, «будет ли это множество своим собственным эле- ментом». Примером множества, которое содержит само себя в качестве элемента, могло бы служить, например, множество всех множеств. Рассмотрим множество М» всех множеств, для которых ответ на этот вопрос отри- цателен. Спросим теперь, является ли это множество своим элементом? К своему (наивному) удивлению обна- ругким, что если ответ положительный, то имеем My ф Л7„, т. е. ответ должен (бы) быть отрицательным. Если же ответ отрицателен, то в силу определения множества Мц ответ должен быть положительным. Этот парадокс пока- зывает, что если мы не хотим приходить к противоре- чиям, то необходимо {в частности) отказаться от прият- ной мысли, что любое осмысленное условие на элементы определяет некоторое множество. К счастью, такого рода парадоксы можно получить лишь с «большими» или «неестественными» множествами, без которых в матема- тике можно вполне обойтись*). Появление таких парадоксов в теории множеств было воспринято многими математиками очень болезненно и поэтому привлекло к вопросам оснований математики пристальное внимание практически всех ведущих мате- матиков того времени (назовем к примеру имена Д. Гиль- берта, А. Пуанкаре, Г. Вейля). Было предложено не- сколько программ «спасения» математики от «ужаса» парадоксов, входить в детали которых мы не будем. Ука- жем вкратце только две наиболее действенные програм- мы, различные модификации которых обсуждаются и в настоящее время. Отметим, что многообразие подходов к основаниям математики остается и поныне. Однако прошедшие годы и безусловные достижения математи- ческой логики, речь о которых еще впереди, сняли остро- ту этой проблемы настолько, что большинство математи- ков, работающих в других разделах математики, не уде- ляют особого внимания тем дискуссиям, которые ведут ныне специалисты по основаниям математики. Одной из наиболее разработанных программ по осно- ваниям математики является предложенная Д. Гильбер- том программа финитарного обоснования математики. Суть этой программы состоит в попытке построения та- •) Упоминаемые ниже формализации теории множеств — ак- сиоматические теории множеств,— сохраняя все полезное, не до- пускают проведения всех известных «парадоксальных» рассуж- дении. ВВЕДЕНИЕ 11 кой формализации математики, что средствами этой системы можно доказать свою собственную непротиворе- чивость. Другим принципиальным требованием к такой формализации является условие, чтобы все простейшие, проверяемые непосредственно утверждения о натураль- ных числах были истинными в этой формализации. Ра- бота над этой программой как самого Гильберта, так и его учеников и последователей оказалась весьма плодо- творной для математической логики, в частности, в раз- работке современного аксиоматического метода. Хотя программа «финитизма» в своей исходной постановке оказалась невыполнимой, как показал в своих знаменитых работах К. Гёдель, однако возможные модификации этой программы подвергаются полезному обсуждению и до на- стоящего времени. Другой подход к основаниям математики был связан с критикой ряда положений, которые использовались в математике без должного обоснования. Это относится, в частности, к неограниченному использованию закона исключенного третьего и аксиомы выбора. Программа построения математики при жестких ограничениях на использование этих принципов получила название ин- туиционизма; ее создание и развитие связано в первую очередь с именем Л. Э. Я. Брауэра. Развитый в Со- ветском Союзе А. А. Марковым и его последователями конструктивистский подход к основаниям математики также связан с критическим подходом к допустимым ло- гическим средствам в математике и систематически ис- пользует понятие алгоритма при конструктивистском вос- произведении математических результатов. Хотя основания математики традиционно относятся к математической логике, в настоящем учебнике не место вдаваться в большие подробности этого раздела, находя- щегося на стыке математики и философии. Поэтому огра- ничим обсуждение оснований математики приведенными выше замечаниями, не претендующими на полноту и исчерпывающую точность, служащими скорее иллюстра- тивным целям. Основным итогом деятельности в области оснований математики можно считать становление математической логики как самостоятельного раздела математики, а прин- ципиальным достижением математической логики — раз- работку современного аксиоматического метода, который может быть охарактеризован следующими тремя чертами: 12 ВВЕДЕНИЕ 1. Явная формулировка исходных положений (акси- ом) тон или иной теории. 2. Явная формулировка логических средств (правил вывода), которые допускаются для последовательного по- строения (развертывания) этой теории. 3. Использование искусственно построенных формаль- ных языков для изложения всех положений (теорем) рассматриваемой теории. Первая черта характеризует классический аксиома- тический метод. Две следующие являются дальнейшими шагами в достижении максимальной точности и ясности в изложении теорий. Введение и использование подходя- щих обозначений было на протяжении всей истории ма- тематики весьма важной и продуктивной процедурой. Но математические символы были только элементами формальных языков. В математической же логике впер- вые в истории были созданы такие богатые формальные языки, которые позволяют формулировать практически все основные положения современной математики. Бога- тые формальные языки математической логики и успеш- ный опыт работы с ними создали одну из объективных предпосылок для создания универсальных вычислитель- ных машин, пользующихся в настоящее время весьма разнообразным спектром формальных языков програм- мирования. Основным объектом изучения в математической логи- ке являются различные исчисления. В понятие исчисле- ния входят такие основные компоненты, как: а) язык (формальный) исчисления; б) аксиомы исчисления; в) правила вывода. Понятие исчисления позволяет дать строгое математическое определение понятия доказатель- ства и получить точные утверждения о невозможности доказательства тех или иных предложений теории. Еще одним замечательным достижением математической ло- гики является нахождение математического определения понятия алгоритма, т. е. эффективной процедуры для решения задач из того или иного (бесконечного) класса задач. Интуитивно понятие алгоритма использовалось очень давно. Выдающийся мыслитель XVII—XVIII вв. Г. Лейбниц даже мечтал о нахождении универсального алгоритма для решения всех математических проблем. Точное определение понятия алгоритма позволило доволь- но быстро разрушить эту красивую утопию: А. Чёрч в 1936 г, показал, что невозможен алгоритм, который по ВВЕДЕНИЕ 13 произвольному утверждению, записанному на формаль- ном языке элементарной арифметики, отвечал бы на во- прос: будет ли это утверждение истинно на натуральных числах? Далее оказалось, что даже в системе, описыва- ющей «чистую логику» (исчисление предикатов), про- блема доказуемости алгоритмически неразрешима. В по- следующие годы было обнаружено большое многообра- зие алгоритмически неразрешимых проблем в многих разделах математики. Большой вклад в разработку тео- рии алгоритмов и решение алгоритмических проблем внесли Э. Пост, А. Тьюринг, С. Клини и советские ма- тематики А. И. Мальцев, П. С. Новиков и А. А. Марков. Изучение исчислений составляет синтаксическую часть математической логики. Наиболее глубокое изуче- ние (синтаксического) понятия доказательства в тех или иных исчислениях составляет самостоятельный раздел математической логики, который носит название теории доказательств. Наряду с синтаксическим изучением исчислений проводится также семантическое изучение формальных языков математической логики. Основным понятием семантики является понятие истинности для выражений (формул, секвенций и т. п.) формального языка. Семантические понятия также получили точные математические определения, что дало возможность си- стематического и строгого изучения различных понятий истинности. Классическая семантика языка исчисления предикатов составила весьма богатый раздел математи- ческой логики — теорию моделей, которая активно раз" вивается, а ее методы и результаты успешно применя- ются и в других областях математики (алгебре, анализе). Основателями теории моделей являются А. Тарский и А. И. Мальцев. Исчисления позволяют формализовать многие разделы математики и других наук. Исчисление высказываний и упоминавшееся выше исчисление предикатов являются формализациями логики, древнейшей науки о законах правильного мышления. Создание н изучение этих фор- мализации явилось важным этапом в развитии логики как науки. Первые попытки формализации логики свя- заны с именами Аристотеля и Дж. Буля, но действитель- ная (и действенная) формализация логики была осу- ществлена только с созданием математической логики. Итальянский математик Пеано много сделал для разра- ботки ц популяризации формальных языков логики, 14 ВВЕДЕНИЕ Для математики особенно важной оказалась возмож- ность формализации теории множеств. Исчисления, фор- мализующие основные конструкции «наивной» теории множеств, оказались столь богатыми, что любое теорети- ко-множественное рассуждение, встречающееся в реальной математической практике, можно формально воспроизве- сти в этих исчислениях. Естественной «расплатой» за это богатство было обнаружение К. Гёделем эффектов непол- ноты и даже непополнимости таких исчислений. На пути построения семантики естественных или фор- мальных языков нас поджидают также большие трудно- сти. Так, простодушное убеждение, что каждой повество- вательной фразе русского языка можно правдоподобным (или, по крайней мере, непротиворечивым) образом при- писать значение истинности, опровергается так называе- мым «парадоксом лжеца». Некто говорит: «Фраза, кото- рую я сейчас произношу, ложна». Попробуем выяснить, правду сказал этот человек или солгал. Если предполо- жить, что он сказал правду, то из смысла фразы полу- чается, что он солгал. Если он солгал, то из того, что фраза ложна, получаем, что он сказал правду. Этот па- радокс лежит в основе ряда замечательных теорем ма- тематической логики (теорем о неполноте и о неопреде- лимости истинности в системе). История создания и развития математической логики является самостоятельным предметом и ей не будет уделено внимания в этой книге, за исключением приве- денных выше заведомо не полных указаний некоторых имен и обстоятельств. В заключение настоящего введения нужно отметить, что современная математическая логика представляет собой обширный и разветвленный раздел математики, ис- точником проблем для которого наряду с внутренними ее проблемами служат как философские проблемы осно- ваний математики и логики, так и проблемы, возникаю- щие в других разделах математики (алгебра, анализ, ма- тематическая кибернетика, программирование и др.). 15 Глава 1 ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ § 1. Множества и слова Под буквой мы понимаем знак, который рассматри- вается как целый, т. е. знак, части которого нас не ин- тересуют. Букву будем называть также символом*}. Про две данные (например, написанные) буквы мы можем говорить, что они одинаковы пли что они различны. На- пример, все строчные буквы «а». в данной книге считаем одинаковыми. Одинаковыми мы считаем также все строч- ные буквы «а» в некотором рукописном тексте, хотя оди- наковость двух букв в этом случае установить трудней, чем в предыдущем. Будет предполагаться, что для рас- сматриваемых/двух конкретных букв мы всегда можем установить их одинаковость или различие. Если буквы ai и а,, одинаковы, то будем писать di == flz. Абстракция отождествления одинаковых букв даст нам понятие абстрактной буквы. В дальнейшем о двух одинаковых конкретных буквах Oi и йг мы будем гово- рить как об одной п. той же (абстрактной) букве а. При этом каждая из этих двух конкретных букв будет назы- ваться представителем абстрактной буквы а**). Совокупность Х некоторых объектов, которые будут называться элементами X, назовем множеством***}. Если а — элемент множества X, то пишем а е X. Если любой .элемент множества Х является элементом множе- ства Y, то множество Х называется подмножеством мно- *) Иногда слово «буква» будет иметь и обычный смысл, на- пример, «латинская буква», «строчная буква». **) Следует при этом различать абстрактную букву, обозна- чаемую символом а, и сам символ я, который есть обозначений или имя упомянутой абстрактной буквы. ***) Как отмечалось во введении, такое определение, вообще говоря, может привести к противоречию. Однако это не должно пу- гать читателя, так как существование всех рассматриваемых в этой книге множеств можно вывести в рамках формальной системы, описанной в § 11, в которой невозможно провести ни одно извест- ное опарадоксйльное» рассуждение о множествах. 16 ГЛ. 1. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ жества У и обозначается это так: Х s У. Если для мно- жеств Х и У имеем Х s У и У s X, то будем считать множества Х и У равными и писать Х = У. Таким обра- зом, множество полностью определено своими элемента- ми. В частности, существует только одно множество, не содержащее ни одного элемента. Такое множество будем называть пустым и обозначать символом 0. Если для множества Х не имеет место а е X, то будем писать а Ф X. Буквами i, ], k, I, m, п, р, г, s, возможно с индексами, будем обозначать натуральные числа. Множество всех натуральных чисел будем обозначать буквой ю. Если QiSX, ..., я„еХ, то будем писать fli, ..., а„еХ. Если. Х — множество, Oi, ..., а„ <= Х и любой элемент Х равен одному из Oi, ..., а„, то Х называем конечным множе- ством и пишем X={ai, ..., On)*). Если (р(п)—некоторое условие на объект а, а Х — множество, то через {аеХ1ф(а)} или {а1ср(а), я е X} обозначаем множество, содержащее в качестве элементов те и только те элемен- ты а<=Х, которые удовлетворяют условию ср(д). Напри- мер, {n&Q\n=2k для некоторого k <=• со} 'является мно- жеством всех четных натуральных чисел. Множество абстрактных букв называется алфавитом. Букву, являющуюся элементом алфавита А, будем назы- вать буквой алфавита. А. Конечный ряд написанный друг за другом конкрет- ных букв называется конкретным словом. В частности, каждая конкретная буква является конкретным словом. Если каждая из букв конкретного слова к является пред- ставителем некоторой буквы алфавита А, то будем гово- рить, что к является словом в алфавите А. Мы допуска- ем также случай, когда слово к не содержит ни одной конкретной буквы. Такое слово будем называть пустым. и обозначать через Л. Будем говорить, что два конкрет- ных слова at...a„ и bi... b,, алфавита А равны, и писать fli.. -On = &i... Ьц, если п = k и Qi = fti, ..., я„ = 6„. Все пустые слова считаем равными. Если ai...o„—конкрет- ное слово, состоящее из п букв ai, ..., a„ алфавита А, то число п называется длиной этого слова. Длиной пустого слова будет число 0. •) Отметим, что при этом попарное различие элементов л;, .>» ..., an не предполагается. В частности, {0} = {0, 0, 0}. § \. МНОЖЕСТВА II СЛОВА 17 Применяя абстракцию отождествления, будем гово- рить о двух равных конкретных словах tti, «2 как об од- ном и том же (абстрактном) слове а. При этом эти два конкретных слова будем называть представителями сло- ва а. Из определения равенства конкретных слов полу- чаем, что абстрактное слово a можно определить как конечный ряд абстрактных букв такой, что каждый пред- ставитель слова та есть ряд представителей соответству- ющих абстрактных букв. Количество абстрактных букв в этом ряду будем называть длиной абстрактного слова к. Пустое абстрактное слово будем обозначать той же буквой Л, что и конкретные пустые слова. Для .абстрактных слов ст и ^ определяем абстрактное слово оф как такое абстрактное слово, все представители которого получаются приписыванием к некоторому пред- ставителю слова к некоторого представителя слова ^. Абстрактное слово сф будем называть соединением абст- рактных слов «, Р; абстрактное слово к будем называть началом слова к?. Аналогично определяется соединение та»... о.п абстрактных слов cii, ,.., сс,г В дальнейшем под словом мы понимаем абстрактное слово. Очевидно, что для любых слов и, ^ имеем Ли == •= кЛ = а и кЛр = сф, Слово ^ алфавита А называется подсловом слова к алфавита 4, если к == '^б для некоторых слов f, б. В частности, любое начало сюва <х будет подсловом а. Д1ожет оказаться, что а == ^б = ^i?6i и 'y^'Yi. В этом случае говорим о различных вхождениях подслова ^ в к. Таким образом, вхождением подслова ? в слово <х назы- вается слово Р вместе с местом его расположения в сло- ве ос. Вхождение подслова ^ в слово ос, можно изображать так; ^ * р * б, где * — символ, не принадлежащий алфа- виту А. В частности, если к = "^б == ^ftp6i и "f^'fi, то мы имеем два различных влоэддения f * ^ * 6 и 'Yi * ? * 61 подслова ^ в слово к. Если для вхождения 'is * Р * бо подслова ? в а слово 'Уо (слово бо) имеет наименьшую длину среди всех слов f (слов б), для которых к="(рб, то •Yo» р * бо называется первым (последним} вхожде- нием рвк. Вхождением буквы а в слово а называется вхожде- нием в к слова, состоящего из одной буквы а. Если су- ществует вхождение буквы д в слово к, то говорим, что буква а входит в к. Пусть f » р * б — вхождение слова ^ в «. Если а == ^'Ь для некоторого слова У, то будем 2ю. Л. Ершов, Е. А. Палютин 18 ГЛ. 1. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ говорить, что слово а' получается из os заменой вхож- дения f » р * б подслова р на слово ^'. Ряд Xi, ..., Хп некоторых объектов Х„ i^{l, ..., п), будем называть последовательностью пли кортежем, а число га — длиной этой последовательности. Объекты X», г'е^{1^ ,..^ /г}^ будут называться членами или элементами последовательности Xi, ..., Х„. Мы предполагаем, что по записи последовательности ее члены и их порядок вос- станавливаются однозначно. Для этого нам необходимо разделять члены последовательности, например, с по- мощью запятой. Если п == 0, то ряд Xi, ..., Хп будем считать пустой последовательностью и обозначать его тем же символом 0, что и пустое множество. Иногда последовательность Xi, .... Хп будем обозначать через . Если Xi, ..., Хп—множества, то множе- ство всех кортежей , где ai е Xi, .... я„ е= Хг„ будем обозначать через Xi Х ... Х Хп, Если X, == Ха == ... ... == Х„, то множество Xi Х Хг Х ... Х Хп будем обозна- чать также через Х.п. Последовательность из двух (трех п т. д.) членов будем называть парой (тройкой и т. д.). Последовательность из п элементов будем называть п-кой. Отображением } множества Х в множество Y назы- вается соответствие, сопоставляющее каждому элементу аёХ элемент /(я) е У^ называемый значением отобра- жения / на элементе а. Ясно, что отображение / множе- ства Х в множество Y однозначно определяется множе- ством {<я, /(д)> е XX 7|а е X}. Это множество (называе- мое иногда графиком /) мы будем отождествлять с ото- бражением /. Если / — отображение Х в У, то пишем /: Х ->- Y. Если Х—множество, то всякое отображение /: X" -> Х будем называть п-местной операцией на X, а п—местностью операции /. Если /: У--Х и VsX", то / будет называться частичной п-местной операцией на Х с областью определения Y. Пусть Х — множество, Хо s X' и /i, ..., /,, — операции на X, местности которых равны га,, ..., п^ соответствен- но. Определим множество WsX следующим образом: a s W тогда и только тогда, когда существует последова- тельность До, ..., Ят элементов множества X, обладающая следующим свойством: am °= а и для любого i^m либо :Хо, либо а, =» /j (^, .) для некоторого /' s{l, ..., k} и некоторых ii, ...,^<г. В этом случае § 1. МНОЖЕСТВА И СЛОВА 19 будем говорить, что множество W определено по индук- ции с помощью следующего определения: 1) если деХо, то a<=W; 2) если i'^{l, ..., k} и а^, ..., я„. е W, то /,(ai, ...,a^)e=F7. Будем говорить, что задано исчисление I, если зада- ны следующие четыре множества: а) алфавит А (1}; б) множество Е (/) слов алфавита А(1}, называемое множеством выражений исчисления I; в) множество Ах(/) выражений исчисления I, назы- ваемое множеством аксиом исчисления I; г) множество {/i, ..., /rJ частичных операций на множестве Е(1), называемых правилами вывода исчис- ления I. Выражения рассматриваемых в этой книге исчислений будут называться секвенциями и формулами, а правила вывода /: Y -г Е (/) записываться так: Ф Ф п' • • •' П f{^---^n) ' При этом указывается область определения /, если она не совпадает с (Е (/))". Выражения Фо, ..., Фп в пре- дыдущей записи будут называться посылками, а выраже- ние /(Фо, ..., Фп)—заключением правила f. га-местное правило / исчисления / будем называть также п-посы- лочным правилом. Пару <Л(7), Е(1)~>, состоящую пз алфавита А(1} и множества выражений Е(1} исчисле- ния /, будем называть языком исчисления / и обозна- чать через L{1}. Пусть даны два исчисления /i и 1г. Если A{li)sA(Ii} a E(It)sE(It), то будем говорить, что язык L(Is) исчисления 1г является расширением языка ?(/i) исчисления /i, и обозначать это так: L(Iz}'= L(I,)*). Если дано исчисление /, то множество Т(1}^Е(1} доказуемых выражений или теорем исчисления I опреде- ляется с помощью следующего индуктивного определения: 1) если S—аксиома /, то S—теорема /; 2) если iS'i, ..., 6'„—теоремы /, /—п-посылотаое пра- вило исчисления / и кортеж <5i, ..., Sn> принадлежит области определения /, то f(Si, ..., Sn)—теорема I. *} Это обозначение не совсем согласуется с уя;е введенным обозначением включения для множеств, однако оно удобно п пу- таницы не вызывает. 2* 334 ГЛ. 7. АЛГОРИТМЫ II РЕКУРСИВНЫЕ ФУНКЦИИ ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Аксиома выбора 75 —.исчисления 19 — регулярности 80 — экстенсиональности 65 Алгебраическая система 97 — — насыщенная 189 — — однородная 187 — — универсальная 189 Алгебраические системы изоморф- ные 98 — — элементарно эквивалентные. 152 Алгоритм 12, 241 Булева алгебра 73 — — атомная 316 Вполне упорядоченное множество 74 Вывод в IIBi 53 — — ПП2 143 Гомоморфизм 98 График 18 — частично рекурсивной функции 270 Декартово произведение G6 — — алгебраических систем 113 Диаграмма алгебраической систе- мы 159 — — — полная 159 Дизъюнктивная нормальная форма (д. и. ф.) 40, 132 Дизъюнкция 22 — элементарная 39 Доказательство 12 — в ИВ в виде дерева 28 — — — линейное 27 — — ЦП ^в виде дерева 121 — — — линейное 121 Изоморфизм алгебраических си- стем 98 — — — частичный 152 — — — — конечный 152 Импликация 22 Истинность формулы на алгебраи- ческой системе при интерпрета- ции 107 Исчисление 19 — высказывании (ИВ) 22 — — гильбертовского типа (HBi) 52 — независимое 50 — непротиворечивое 43 — — по отношению к семантике 50 — предикатов сигнатуры 2 (ITO'") 119 — — — — гильбертовского типа (1Ш f) 142 — разрешимое 50, 281 — резольвент 236 Кардинал 86 Квазивывод секвенции в ИВ 31 _ — — ИП2 )21 Квазимногообразче 1G6 Квазптождество 1в6 Квантор всеобщности 105 Квантор существования 105 Класс 114 — алгебраических систем аксиома- тизируемый 1В1 — — — категоричный в мощности 194 Консервативное расширение ис- числения 56 Конъюнктивная нормальная форма (к. н. ф.) 40 Конъюнкция 33 — элементарная 40 Кортеж 18, 66 Линейно упорядоченное множест- во 70 Линейный порядок 70 Машина Тьюринга 242, 248 Машинное слово 248 Многообразие 166. Множества подобные 76 — равномощные 83 Множество 15 — бесконечное 87 — конечное 16, 87 — натуральных чисел 65 — рекурсивно перечпслимов 274 — рекурсивное 274 — счетное 87 — транзитипное 84 — формул выполнимое 117 — —локально выполнимое 117 — — непротиворечивое 135 — центрированное 79 Множество-степень 20 Мощность алгебраической системы 97 — множества 87 — сигнатуры 97 Натуральное число 65 Нормальный алгорифм 242. 244 — —, вычисляющий функцию 247 Носитель алгебраической системы 97 Нумерация гёделевская 281 Обеднение алгебраической системы 100 Область действия вхождения кван- тора 106 — значений функции 68 — определения операции 18 — — функции 68 Обогащение алгебраической систе- мы 99 Оператор минимизации 253 — примитивной рекурсии 253 — регулярной суперпозиции 252 Ординал S'i Отношение 66 — антисимметричное 67 — обратное 67 — рефлексивное 67 — симметричное 67 — транзитивное 67 Отображение 18, 68 — в 68 — на 68 — разнозначное 68 Пара 18 336 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Парадокс лжеца 14 — Рассела 9 Переменная 103 — пропозициональная 22 Подсистема алгебраической систе- мы 98 — — —, порожденная множеством 99 — — — элементарная 158 Порядок плотный 1П1 Посылка правила 19 Правило вывода 12, 19 — —, допустимое в ИВ 30 — — независимое v исчислении 50 Предикат 66 — рекурсивно пере.чпслпмый 269 — рекурсивный 259 — универсальный 278 Предложение 108 — я-общезначимое 109 Првненсная нормальная форма 132 Приведенная нормальная форма 134 Принцип максимума 75 — нормализации 246 — полного упорядочения 75 — трансфинптной индукции 74 Проолема разрешимости исчисле- ния 50 Произведение отношений 67 Расширение исчисления консерва- тивное 56 Рекурсия кусочно возвратная 285 Решетка 7t Свободная переменная формулы 10В Связка логическая 22 Секвенция 19 — ИПЧ 147 — ПП^ 119 —"исчисления G 204 — — Go 60 Сигнатура 9в Система акгпом для теории 169 — — Цсрмсло — Френкеля 92 Скулсмизация алгебраической си- стемы 171 — теории 171 Слово абстрактное 17 — машинное 248 Совершенная д. н. ф. 41 — к. н. ф. 41 Тезис Тьюринга 251 — Чёрча 254 Теорема 12 — Геделя о неполноте 293 — — — полноте 139 — интерполяционная Крейга —« .Чиндона 179 — Кантора 83 — Кантора — Бернштейна 83 — компактности 117, 142 — Лося 116 — о графике 270 — — дедукции 54, 144 — — замене 35, 130 — — подстановке 33 — — полноте ИВ 49 — — редукции 277 —•. — существовании модели 136 Теорема о функциональной полно- те IIB 47 — об опускании типов 178 — — устранении сечения 214 — Рыль-Нардзевского 194 — Эрбрана 232 Теория 169 — аксиоматизируемая 292 — алгебраической системы 152 — категоричная в мощности 194 — класса алгебраических систем 152 — модельно полная 169 — наследственно неразрешимая 318 — полная 169 — с элиминацией кванторов 170. 297 — универсально аксиоматизируе- мая 169 — элементарная 169 Терм 103 — базисный 173 — рекурсивный 267 Тождество 166 Ультрафильтр булевой алгебры 80 Упорядоченный набор В6 Условие несмешанности перемен- ных 204 Фильтр булевой алгебры 79 — главный 81 — на множестве 79 — Фреше 79 Формула 19, 22, 105, 119 — атомарная 22, 105 — атомная 105 —, выполнимая в алгебраической системе 109 — замкнутая 108 — ИВ 22 — —, тождественно истинная 45 — — элементарная 22 — ИПЧ 147 — ИП^ 119 — исчисления резольвент 237 — — G 204 — общезначимая 108 — позитивно примитивная 303 — положительная 183 — рекурсивная 267 —— рекурсивно перечнслпмая 269 — тождественно истинная 108 — условии фильтрующаяся 115 — фильтрующаяся 115 Формулы конгруэнтные 131 — пропозиционально эквивалент- ные 129 — эквивалентные 34, 129, 144 Функция 68 — базисная 253 — рекурсивная 253 — спектрально представимая 326 — универсальная 279 — характеристическая 259 — частичная 246 — — вычислимая 246 — — — по Тьюрингу 249 —, — нормально вычислимая 247 — частично рекурсивная 253 Частично упорядоченное множест- во 70 — — — фундированное 73 Частичный порядок 7U Опечатка в выпускных данных Стоимость книги 1 р. 10 к.