Клини С.К. Введение в метаматематику:
Математическая логика и рекурсивные функции. Пер. с англ. Изд. 2, испр.

Оглавление

От переводчика

Хотя математическая логика существует как наука по крайней мере с середины прошлого столетия, круг специалистов в этой области невелик и результаты ее известны недостаточно широко. Однако за последние десятилетия-и в особенности начиная с 1930 г.-в ней были сделаны важнейшие открытия и развитие ее приняло настолько бурный характер, что теперь трудно уже охватить все полученные результаты одной монографией, во всяком случае, такая монография до сих пор никем не написана. Имеются всё же две монографии, которые играют ведущую роль в мировой литературе по математической логике, это книга Гильберта и Бернайса "Grundlagen der Mathematik" (т.I–1934 г., т.II–1939 г.) и предлагаемая вниманию читателя более современная книга Клини "Введение в метаматематику" (1952 г.).

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

От читателя не требуется никаких предварительных познаний в логике или математике. Однако подробное проведение всех опущенных автором деталей доказательств требует некоторой тренировки (которую, впрочем, можно приобрести в процессе тщательного изучения этой книги). Таким образом, книгу можно рекомендовать и начинающему-при условии, что он не боится трудностей. Читателю, уже знакомому с излагаемым материалом, книга будет полезна не только благодаря оригинальности изложения и обилию тонких замечаний, но и потому, что она может служить удобным библиографическим источником.

Часть III этой монографии может в основном читаться независимо от остальных частей и служить руководством для изучения теории рекурсивных функций, более сжатым и потому более трудным, чем выпущенная недавно Издательством иностранной литературы книга Р.Петер "Рекурсивные функции", (1951 г.; третья часть книги Клини содержит более полное изложение теории обще-рекурсивных функций и вовсе отсутствующую у Петер теорию частично-рекурсивных функций, но зато монография Петер богаче материалом, связанным с примитивными рекурсиями).

В нескольких местах автор счел возможным отослать читателя за доказательствами к упомянутой книге Гильберта и Бернайса. Мы в специальных добавлениях восполнили эти отсутствующие звенья в изложении автора.

Если принять во внимание сделанные нами добавления и ряд подстрочных примечаний, то по сравнению с материалом, изложенным у Гильберта и Бернайса, в настоящей книге отсутствует теория одноместных предикатов, а также изложенные в последних двух дополнениях к книге Гильберта и Бернайса теория положительных форм (относящаяся к исчислению высказываний) и формальное построение анализа на основе арифметики с переменными функциями (для которого, впрочем, до сих пор не известно никакого доказательства непротиворечивости).

Зато налицо подробное рассмотрение интуиционистских систем, общая теория как обще-, так и частично-рекурсивных функций, исчисление Генцена, реализуемость, т.е. вещи, более современные и заведомо перевешивающие упомянутый не вошедший сюда материал книги Гильберта и Бернайса.

Мы глубоко благодарны автору за присланный им перечень опечаток и отдельных мелких погрешностей, имевшихся в английском издании. В русском издании соответствующие места исправлены.

Выражаем благодарность также А.А.Курмитису (Рига), указавшему на одну неточность, допущенную автором (в замечании 1 § 27).

Ряд мелких исправлений внесен нами без специальных оговорок.

В оригинале при переносе формул последний знак, стоящий перед переносом, не повторяется. Следуя установившейся у нас традиции, мы, как правило, повторяем этот последний знак, если он не является знаком отрицания или запятой.

Обращаем особое внимание читателя на различие между двумя шрифтами – курсив и плантин, которое начинает появляться в IV главе, и особенно начиная с § 40 гл.VIII.

Курсив: а, b, с, d, e, f, g, h, i,..., l, m, n, p, r, s,..., x, у, z

Плантин: a, b, c, d, e, f, g, h, i... l, m, n, p, r, s,..., x, y, z.

(Плантин употребляется для обозначения формальных переменных, а курсив-для содержательных.)

Предисловие

Две последовательные эры исследований по основаниям математики в девятнадцатом столетии, достигшие своего наивысшего развития в теории множеств и арифметизации анализа, сменились около 1900 г. новым кризисом и новой эрой, отмеченной господством программ Рассела и Уайтхэда, Гильберта и Брауэра.

Появление в 1931 г. двух теорем Гёделя о неполноте, в 1933 г. работы Тарского о понятии истины в формализованных языках, в 1934 г. эрбран-гёделевского понятия "обще-рекурсивной функции" и в 1936 г. связанного с ним тезиса Чёрча возвещает уже новейшую эру, в которой математические средства применяются как для оценки прежних программ, так и в новых, не предвиденных прежде направлениях.

Цель этой книги – дать связное введение в область математической логики и теории рекурсивных функций и в новейшие исследования по основаниям математики вообще.

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

Книга написана с таким расчетом, чтобы она могла служить учебником для аспирантов-математиков первого года обучения (и старше) и для других лиц, достигших этого уровня владения математикой, независимо от их познаний в том или ином разделе математики.

При использовании книги в качестве учебника рекомендуется быстро (в течение двух или трех недель при аудиторных занятиях по три раза в неделю) пройти часть I (главы I–III), которая содержит необходимый подготовительный материал. Интенсивное изучение должно начаться с части II (глава IV), где существенно, чтобы изучающий сосредоточился на приобретении прочного навыка в обращении с метаматематическим методом.

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

Обе знаменитые теоремы Гёделя о неполноте изложены в главе VIII, причем доказательство одной леммы отложено до главы X. Автору удавалось закончить эти десять глав (а иногда даже несколько больше) в течение семестрового курса, который он неоднократно читал в Висконсинском университете.

Остальные пять глав можно использовать для расширения такого курса до годичного или при параллельном чтении, сопровождающем семинар.

Семестровый курс по рекурсивным функциям при наличии у студентов некоторого предварительного знакомства с математической логикой или под руководством осведомленного преподавателя можно начать с части III (глава IX). Имеются и другие возможности выбора материала; например, тем, кто интересуется преимущественно математической логикой, многое из части IV можно читать непосредственно за частью II или даже за главой VII.

Автор благодарен Сондерсу Маклэйну, склонившему его к написанию этой книги и сделавшему ценные критические замечания в связи с первыми черновиками некоторых глав. Джон Аддисон полностью прочитал гранки с большой тщательностью и независимо от автора. Среди многих других, оказавших помощь, были Эверт Бет, Роберт Бройш, Аренд Рейтинг, Нэнси Клини, Леонард Линский, Дэвид Нельсон, Джеймс Ренно и Джин Роуз. Научные заимствования отмечены ссылками на библиографию; особенно много использована книга Гильберта и Бернайса "Grundlagen der Mathematik" в двух томах, 1934 и 1939 гг.