517 Н73 УДК 164 Петр Сергеевич. Новиков Конструктивная математическая логика с точки зрения классической (Серия: «Математическая логика и основания математики») М„ 1977 г., 328 стр. с илл. Редакторы Ф. Л. Кабаков, Б. А. Кушнер, В. В. Донченко Техн. редактор И. Ш. Аксельрод Корректор Г. С. Плетнева Сдано в набор 30.07.76. Подписано к печати 9.03.77, Бумага 84Х108'/а, тип. № 1. Физ. печ. л. 10,25+1 вкл. Условн. печ. л. 17,32. Уч.-изд. л. 17,19. Тираж 14000 экз. Т-03635. Цена книги 1 р. 43 к. Заказ № 265 Издательство «Наука» Главная редакция физико-математической литературы 117071, Москва, В-71, Ленинский проспект, 15 Ордена Трудового Красного Знамени Ленинградская типография № 2 имени Евгении Соколовой Союзполиграфпрома при Государственном комитете Совета Министров СССР по делам издательств, полиграфии и книжной торговли. 198052, Ленинград, Л-52, Измайловский проспект, 29. н 20203—052 053(02)-77 69-76 © Главная редакция физико-математической литературы издательства «Наука», 1977 ОГЛАВЛЕНИЕ Предисловие ....... .. ."..Т .."... . ...... 7 Глава I Классическая логика высказываний .............. 9 § 1. Алгебра высказываний ................ 9 § 2. Исчисление высказываний ............... 19 Глава II Конструктивная (интуиционистская) логика высказываний ... 48 § 1. Основные принципы .................. 48 § 2. Конструктивное (интуиционистское) исчисление высказы- ваний ......................... 53 § 3. Сравнение классического и конструктивного исчисления высказываний ..................... 69 § 4. Невыводимость законов исключенного третьего и снятия двойного отрицания .................. 73 § 5. Модели исчислений высказываний ........... 77 § 6. Теорема Гливенко .................. 83 Глава III Д-исчисление Гёделя ..................... 92 § 1. Основные определения ................ 9.2 § 2. Дедуктивные свойства Д-исчисления .......... 93 § 3. Интерпретация конструктивного исчисления высказываний в D-нсчислении .................... 108 § 4. Арифметическая модель Д-исчисления ......... 117 § 5. Элиминируемость 0-оператора в арифметических моделях D-нсчисления ..................... 130 § 6. Топологические модели Л-исчислепия ......... 136 § 7. Теорема Тарского о топологической полноте конструктив- ного исчисления' высказываний ............. 147 § 8. Бэровское пространство как точная модель конструктив- ного исчисления высказываний ............. 155 § 9. Топологическая полнота D-исчисления ......... 165 6 ОГЛАВЛЕНИЕ Глава IV Исчисление предикатов .................... 170 § 1. Основные определения ................ 170 § 2. Элементы дедукции в предикатных исчислениях . . . .185 § 3. Классическое D-исчисление предикатов как модель кон- структивного исчисления предикатов .......... 197 § 4. Топологические модели предикатного Д-исчисления . . . 204 Глава V Формализованная арифметика ................. 213 § t. Классическая формальная арифметика с fl-оператором . 213 § 2. Классическая формальная арифметика с (-i-оператором . 227 § 3. Вычислимые формулы в классической арифметике . . . 239 § 4. Конструктивная формальная арифметика ....... 252 § 5. Частично рекурсивные функции ............ 258 § 6. Метод арифметизацин. Теорема Геделя о неполноте фор- мальной арифметики .................. 272 § 7. Реализуемость по Кляни ............... 278 Литература .......................... 318 Список аксиом ........................ 321 Указатель имен ........................ 323 Предметный указатель .................... 324 ^Г^Г06 читает лекции п0 ———РУ-вной матема- логике на механико-математическом факультете МГУ (фото Б. Я. Фалевича, 1955 г.), ПРЕДИСЛОВИЕ Автор этой книги, выдающийся советский математик академик Петр Сергеевич Новиков, родился в августе lulfl года. Свою научную деятельность П. С. Новиков начал в двадцатые годы в области дескриптивной теории мно- жеств. Петру Сергеевичу принадлежат глубокие науч- ные результаты в области теории множеств матема- тической логики, теории алгоритмов и теории групп Искючительная роль П. С. Новикова в развитии этих областей математики в СССР определяется также его многолетней педагогической деятельностью в МГПИ им. В, И. Ленина и в МГУ им. М. В. Ломоносов? 11. L. Новиков создал большую научную школу в сб ча- сти ".агематической логики и теории алгоритмов ' Его книга элементы математической логики» являющаяся первым отечественным курсом математической логики пользуется большой популярностью как в нашей стране' так и за рубежом. Она переведена на английский, фраи^ цузскии, итальянский и японский языки В 1973 ГОЛУ вышло в свет второе русское издание этой книги Настоящая книга написана на основе лекций читав- шихся П. С_ Новиковым во второй половине пятидеся- тых годов. В ней излагаются вопросы математической логики, не рассмотренные в первой книге В этом смысле она как бы дополняет предыдущую книгу В.го же время книга написана так, что ее можнГ читать и-^^^ь-^ьК ^уТеГ- ———-Р06"0 щийся к классическим л^ч^иУ0^3^'^^' ^^^'"H^'B интерпретации инструктивных фор6 н^е^едсткласс^"4601"" ^Р"""^ и с использова- ^^^о^струк^^^ математики. Вопросы семан- тики конструктивной логики изложены в ней в оригиналь- 8 ПРЕДИСЛОВИЕ ной и доступной для читателя форме. Доказательства основных утверждений приводятся во всех деталях. Только в последней главе опущены доказательства неко- торых утверждений, относящихся к теории рекурсивных функций и теореме Гёделя о неполноте формальной арифметики. Несмотря на то, что со времени чтения соответствую- щих курсов Петра Сергеевича прошло около 20 лет, затронутые в них вопросы не потеряли своей актуаль- ности. Наоборот, интерес к вопросам, связанным с раз- личными интерпретациями конструктивной (интуиционист- ской) логики, в последнее время даже возрос. Редакторы книги Ф. А. Кабаков и Б. А, Кушнер провели большую работу по переработке записей лекций. В своей работе они использовали записи лекций, сделанные А. В. Куз- нецовым, Б. Ю. Пильчак, В. А. Успенским и А. А. Фрид- маном. Ряд полезных замечаний к первоначальному тексту рукописи книги сделал рецензент В. Е. Плиско. Не пре- тендуя на полноту, редакторы добавили в примечаниях, а иногда и в тексте книги без доказательств опублико- ванные в последнее время результаты, относящиеся к по- нятию реализуемости. Работа редакторов усложнялась тем, что тяжелая болезнь и смерть Петра Сергеевича в январе 1975 года помешали ему принять участие в окончательной подготовке к-печати рукописи книги. Я хочу выразить благодарность Ф. А. Кабакову и Б. А. Кушнеру, большой и кропотливый труд которых обеспечил читателям возможность ознакомиться с насто- ящей книгой. В книге проводится четкое различие между класси- ческими и конструктивными логическими операциями. С этой целью для одноименных операций используются различные обозначения в классическом и конструктив- ном случаях. Книга доступна широкому кругу читате- лей. Для ее чтения не требуется специальной подготовки. В то же время, насыщенность разнообразными техничес- кими деталями делает ее полезной для лиц, занимаю- щихся исследованием математических аспектов конструк- тивной логики. Книга может также служить основой для спецкурсов. С. И. Адян 25 февраля 1976 г. ГЛАВА I КЛАССИЧЕСКАЯ ЛОГИКА ВЫСКАЗЫВАНИИ § 1. Алгебра высказываний 1. Под высказыванием (суждением) мы понимаем всякое предложение, о котором имеет смысл говорить, что оно (его содержание) истинно или ложно. Именно это свойство высказываний — быть истинными или лож- ными — будет нас интересовать, в то время как от струк- туры и содержания высказываний мы отвлекаемся. Пример 1. Рассмотрим высказывания «Рим—сто- лица Италии» и «собаки имеют шесть ног». Первое из этих высказываний естественно считать истинным, а вто- рое — ложным. При изучении высказываний мы будем предполагать, что 1) каждое рассматриваемое высказывание либо истинно, либо ложно (здесь, очевидно, применяется закон исклю- ченного третьего традиционной (аристотелевой) логики); 2) никакое высказывание не является одновременно истинным и ложным. Объем понятия «высказывание» мы сейчас не уточ- няем, вместе с тем сказанное выше можно выразить на математическом языке таким образом, что на сово- купности высказываний, какой бы она ни была, мы счи- таем определенной некоторую функцию со значениями из двухэлементного множества {«истина», «ложь»}. Нам будет удобно обозначать элементы этого множества символами 1 («истина») и 0 («ложь»). Основной задачей логики высказываний является исследование операций над высказываниями (логических операций), позволяющих получать некоторые новые вы- сказывания из произвольных исходных высказываний. При этом в соответствии с нашей трактовкой высказы- ваний естественно ограничиться такими логическими операциями, при которых истинностное значение резуль. ЛИТЕРАТУРА Александров П. С. [1] Введение в общую теорию множеств и функций, Гостехиздат, М.—Л., 1948. Варпаховский Ф.Л. [1] О нереализуемости дизъюнкции нереализуемых формул, ДАН СССР 161, 6 (1965). [2] Об одном классе реализуемых формул логики высказываний, Записки научных семинаров Ленинградского отделения МИАН им. В. А. Стеклова 20 (1971), 8—23. Г е и т и н г (Н е у t i n g A.) [1] Die formalen Regein der intuitionistischen Logik, Sitzungsber. Preuss. Akad. Wis„ phys.-math. Kl., 1930, 42—56. [2] Intuitionism, an Introduction, Studies in Logic and Foundations oi Mathematics, Amsterdam, 1956. [Русский перевод: А. Г е й- т и н г, Интуиционизм, «Мир», М., 1965.] Ген не н (G en t z е n G.) [1] Untersuchungen (iber das logische Schliessen, Math. Z, 39 (1934—1935), 176—210, 405—431. [Русский перевод: Г. Ген- цен, Исследования логических выводов, сб. «Математическая теория логического вывода», «Наука», М., 1967, 9—74.] Гёдель (Godel К.) [1] Ober formal unentscheidbare Satze der Principia Mathematica und verwandter Systeme 1, Monatsh. Math. Phys. 38 (1931), 173—198. [2] Zum intuitionistischen Aussagenkalkdl, Akad. Wiss. Wien, math.- naturw. Kl., Anzeiger 69 (1932), 65—66. [3] Eine Interpretation des intuitionistischen Aussagenkalkiils, Er- gebn. math. Koll. 4 (1931—1932, опубл. 1933), 39—40. Г л и в е н к о В. И. [1] Sur quelques points de la logique de M. Brouwer, Acad. Roy. Beig, Bull. cl. csi„ ser. 5, 15 (1929), 183—188. Кабаков Ф. А. [1] Выводимость некоторых реализуемых формул исчисления вы- сказываний, Z. math. Logik Grundl. Math. 9 (1963), 97—104. Карри (Curry Н. В.) [1] Foundations of mathematical logic, McGraw-Hill, N. Y., 1963. [Русский перевод: X. Б. Карри, Основания математической логики, «Мир», М., 1969.] К и п н и с М. М. [1] О реализациях пропозициональных формул, Записки научных семинаров Ленинградского отделения МИАН им. В. А. Стекло- ва 20 (1971), 40—48. ЛИТЕРАТУРА 319 [2] Об одном свойстве пропозициональных формул, ДАН СССР 174, № 2 (1967). К л и н и (К 1 eene S. С.) [1] On the interpretation of intuitionistic number theory, J. Symbolic Logic 10 (1945), 109—124. [2] Introduction to metamathematics, N. Y.—Toronto, 1952. [Рус- ский перевод: С. К. К л и н и, Введение в метаматематику, ИЛ, М., 1957.] [3] Logical calculus and realizability, Acta Philosophica Fennica 18 (1965), 71—80. [4] Mathematical logic, N. Y. — London — Sydney, 1967. [Русский пе- ревод: С. К. К л и н и, Математическая логика, «Мир», М., 1973.] К л и н и (К 1 е е n е S. С.) и В е с л и (V е s 1 е у R. Е.) [1] The foundations of intuitionistic mathematics, Amsterdam, North- Holland Publ. Co., 1965. Колмогоров А. Н. [1] О принципе tertium поп datur, Матем. сб. 32, № 4 (1925), 646—, 667. [2] Zur Deutung der intuitionistischen Logik, Math. Z. 35 (1932), 58—65. К р и n к е (К г i p k e S. А.) [1] The undecidability of monadic modal quantification theory, Z. math. Logik Grundl. 8 (1962), 113—116. [Русский перевод: С. А. К р и п к е, Неразрешимость одноместного модального ис- числения предикатов, в кн. Ф е и с [I], 247—253.] К у р а т о в с к и и (К ч г а t о w s k i К.) [1] Topologie, vol. I, Academic Press, N. Y.—London, Panstwowe Wydawnictwo Naukowe, Warszawa, 1966. [Русский перевод: К. К у р а т о в с к и и. Топология, т. I, «Мир», М., 1966.] К У ш н е р Б. А. [1] Лекции по конструктивному математическому анализу, «Нау- ка», М., 1973. Мальцев А. И. [1] Алгоритмы и рекурсивные функции, «Наука», М., 1965. Марков А.А. [1] О конструктивной математике. Труды Матем. ин-та АН СССР им. В. А. Стеклова 67 (1962), 8—14. Медведев Ю. Т. ]1] Финитные задачи, ДАН СССР 142, № 5 (1962). [2] Интерпретация логических формул посредством финитных за- дач и связь ее с теорией реализуемости, ДАН СССР 148, № 4 (1963). Мендельсон (MendelsonE.) [1] Introduction to mathematical logic, D. Van Nostrand Co., 1963. [Русский перевод: Э. Мендельсон, Введение в математиче- скую логику, «Наука», М., 1976.] Нагорный Н. М. [1] О реализуемых и восполнимых логико-арифметических форму- лах, ДАН СССР 157, № 3 (Г964). Нельсон (Nelson D.) [1] Recursive functions and intuitionistic number theory, Trans. Amer. Math. Soc. 61 (1947), 307—368. Новиков П. С. [1] Элементы математической логики, 2-е изд., «Наука», М., 1973. П л и с к о В. Е. [1] О реализуемых предикатных формулах, ДАН СССР, т. 212, № 3, (1973). [2] Некоторые варианты понятия реализуемости для предикатных формул, ДАН СССР, т. 226, № 1 (1976). Расёва и Сикорский (Rasiowa H., Sikorski R.) [1] The mathematics of metamathematics, Warszawa, 1963. [Русский перевод: Е. Расёва, Р. Сикорский, Математика метамате- матики, «Наука», М., 1972.] Роджерс (Rogers H., Jr.) [1] Theory of recursive functions and effective computability, McGraw-Hill 1967. [Русский перевод: X. Роджерс, Теория рекурсивных функций и эффективная вычислимость, «Мир», М., 1972.] Роуз (Rose G. F.) [1] Propositional calculus and realizability, Trans. Amer. Math. Soc. 75 (1953), 1—19. Тарский (Tarski A.) [1] Der Aussagenkalkul und die Topologie, Fundam. Math. 31 (1938), 103—134. Успенский В. А. [1] Лекции о вычислимых функциях, Физматгиз, М., 1958. Фене (F е у s R.) [1] Modal logics, Paris, 1965. [Русский перевод: Р. Ф е и с, Модаль- ная логика, «Наука», М., 1974.] Френкель и Бар-Хиллел (Fraenkel A. A., Bar-Hil- 1 е 1 Y.) [1] Foundations of set theory, Studies in Logic and Foundations of Mathematics, Amsterdam, 1958. [Русский перевод: А. А. Френ- кель, И. Бар-Хиллел, Основания теории множеств, «Мир», М„ 1966.] Чёрч (Church А.) [1] An unsolvable problem of elementary number theory, Amer. J. Math. 58 (1936), 345—363. Шанин H. А. [1] Конструктивные вещественные числа и конструктивные функ- циональные пространства, Труды Матем. ин-та АН СССР им. В. А. Стеклова 67 (1962), 15—294. Шенфилд (ShoenfieldJ.R.) [1] Mathematical logic, Addison-Wesley Publ. Cow., 1967. [Русский перевод: Дж. Шенфилд, Математическая логика, «Наука», М., 1975.] Я н к о в В. А. [1] О реализуемых формулах логики высказываний, ДАН СССР. 151, № 5 (1963). -• - •