Чёрч А. Введение в математическую логику.
Пер. с англ. Изд. 2

Оглавление

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

I

В течение долгого времени математическая логика оставалась глубинной областью математики и логики, обслуживавшей внутренние потребности этих наук. Эхо больших естественно-научных приложений математики докатывалось до этой области лишь через проблематику оснований математики. Что же касается логики, то она не имела и, казалось, не могла иметь никаких конкретных приложений; только в самые последние годы стало осознаваться ее прикладное значение.

Разумеется, и роль "внутренней науки" является почтенной и необходимой. К тому же именно в этой роли математическая логика добилась выдающихся успехов (по крайней мере один из ее результатов достоин того, чтобы быть известным каждому, кого интересуют возможности человеческого мышления: это так называемая теорема Гёделя о неполноте, утверждающая невозможность полной формализации процесса логического вывода).

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

1. Одну из новых областей приложения математики составляют вопросы анализа и синтеза конечных автоматов. Важными представителями конечных автоматов являются релейно-контактные и электронные схемы, идеализированные "нервные сети" и т.п. При анализе и синтезе этих схем, сетей и т.п. с успехом используется разработанный в математической логике для ее собственных нужд формальный аппарат.

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

3. Происходящий сейчас "кибернетический переворот" ставит машины на места, которые ранее в системе обмена информацией занимали люди и их объединения (подобно тому как промышленный переворот поставил машины на места, которые занимали ранее люди и их объединения в системе промышленного производства). Общепризнано, что замена людей машинами, способными воспринимать, перерабатывать, хранить и выдавать информацию, будет происходить во все возрастающих масштабах. Чтобы успешно возложить на машины функции, долгое время считавшиеся исключительной привилегией человеческого интеллекта, необходим, очевидно, формально-логический анализ этих функций. Очевидно также, что при передаче машинам все более и более сложных функций потребуется создание специального языка, или языков, машин, на котором информация будет храниться в машинах и передаваться от машины к машине. Целесообразно, по-видимому, чтобы этот язык был лишен неправильностей естественных языков и следовал бы логической форме, т.е. был бы "формализованным языком" в том смысле, как он описан на стр.16–17 настоящей книги. Создание такого языка и тем более логический анализ возлагаемых на машины функций не есть, конечно, задача только математической логики, но математическая логика – понимаемая автором книги как "предмет формальной логики, изучаемый посредством построения формализованных языков", – может оказать тут существенную помощь.

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

II

Выдающийся математик и логик, профессор математики Принстонского университета (США) Алонзо Чёрч известен своим вкладом в математическую логику и теорию алгоритмов. Следующие два результата Чёрча оказали особенно сильное влияние на развитие этих дисциплин.

1. Построение в 1935 г. (опубликовано в 1936 г.) первого примера неразрешимой массовой проблемы".

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

Алонзо Чёрч известен также как крупный знаток мировой литературы по математической логике. Им составлена знаменитая "Библиография математической логики", ставящая себе целью дать свод всей литературы по математической логике от времени зарождения этой науки до 1935 г. включительно.

Естественно, что появление монографии столь авторитетного автора было встречено с большим интересом. Изданный в качестве 17-го выпуска известной серии "Princeton Mathematical Series" первый том "Введения в математическую логику'5 быстро завоевал широкое признание и стал необходимой книгой для всякого, кто желает серьезно изучить предмет. Том содержит описание метода математической логики и ее первичных понятий (категорий математической логики, таких, как "имя", "переменная", "форма" и т.п.) и изложение пропозиционального исчисления (в другой терминологии – исчисления высказываний) и функциональных исчислений двух первых порядков (в другой терминологии – исчислений предикатов двух первых ступеней). Он может быть использован как в качестве систематического курса, причем не требующего никаких специальных знаний, хотя и предполагающего довольно высокую математическую культуру, так и в качестве справочника, причем наиболее полного и удобного из существующих.

III

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

Книга Чёрча посвящена именно математической логике, а не основаниям математики, что отличает ее от Principia Mathematica Уайтхеда и Рассела, от Grundlagen der Mathematik Гильберта и Бернайса и от Introduction to Metamathematics Клини; последняя книга вышла сравнительно недавно в русском переводе (С.К.Клини, Введение в метаматематику, 1957). Из имеющихся на русском языке книг к 1-му тому "Введения в математическую логику" ближе всего примыкают Основы теоретической логики Д.Гильберта и В.Аккермана (перевод с немецкого, 1947). Однако "Введение в математическую логику" значительно превосходит "Основы теоретической логики" как современностью и полнотой изложения, так и внимательностью к чисто логическим вопросам и четкостью в употреблении основных понятий (не говоря уже о том, что во втором томе будут изложены такие совершенно не затронутые в книге Гильберта и Аккермана темы, как конструктивная логика, аксиоматическая арифметика и аксиоматическая теория множеств).

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

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

Чтобы не перегружать основной текст, автор относит значительную часть фактов в упражнения, разбитые на 30 циклов. Существенную часть содержания книги составляют 550 нумерованных (1–372, 400–486, 500–590) примечаний, служащих для примеров, сравнений, ссылок, дополнений, терминологических и исторических справок и т.д. (исторические вопросы освещаются также в двух специальных параграфах). В английском оригинале эти примечания были подстрочными, в русском издании они перенесены в конец книги. Возможны различные способы использования этих примечаний – от чтения их параллельно основному тексту до полного их игнорирования при первом чтении. При намерении серьезно проработать книгу лучше всего, пожалуй, читать каждый параграф по два раза – сперва один основной текст без примечаний, затем и основной текст, и примечания.

Наиболее замечательным разделом 1-го тома является Введение, содержащее систематическое описание основных первичных понятий математической логики и ее метода. Ясность и последовательность, с которыми дается это описание, вызывают восхищение. Выглядит, в частности, очень естественным, что первым рассматривается понятие имени (ведь дальнейшее изложение, каково бы оно ни было, неизбежно будет употреблять имена упоминаемых объектов; значит, надо прежде всего объяснить, что такое имя).

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

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

IV

Русская математико-логическая терминология, к сожалению, еще не устоялась, поэтому при выборе русских переводов английских терминов встречались иногда трудности. Английские прообразы для русских терминов, входящих в предметный указатель (стр.461–477), могут быть восстановлены по этому указателю. В необходимых случаях английский термин, взятый в угловые скобки, следует за своим русским переводом непосредственно в тексте. Тем не менее представляется уместным обратить уже сейчас внимание читателя на употребление и перевод отдельных терминов.

1. В заключительной части § 07 термины "символическая логика", "математическая логика" и "логистика" объявляются синонимами (не смешивать логистику с логицизмом – направлением в философии математики!).

2. В самом начале § 08 проводится различие между синтаксисом в узком смысле (или просто синтаксисом) и синтаксисом в широком смысле (или логическим синтаксисом) и между элементарным синтаксисом и теоретическим синтаксисом.

3. Английский термин "sentence", понимаемый сперва как единица выражения в естественных языках и затем распространенный на формализованные языки, переводится русским термином "предложение" (употребляемом согласно с принятым в грамматике значением "слово или сочетание слов, выражающее законченную мысль"; см. Толковый словарь русского языка под ред. проф. Д.Н.Ушакова, т.III, M., 1939, стр.715).

4. Английский термин "proposition", означающий в этой книге то, что может быть смыслом предложения, являющегося истинным или ложным, переводится русским термином "суждение". При этом, очевидно, принимается расширительное истолкование термина "суждение" по сравнению с истолкованием этого термина в отечественных руководствах по логике, где, как правило, рассматриваются лишь суждения, имеющие субъектно-предикатную структуру. Новое истолкование лишь расширяет старое, но не противоречит ему, поскольку всякое суждение в старом понимании является суждением в новом понимании. Совместное употребление терминов "суждение" и "предложение" – так, как это получилось в русском издании книги Чёрча в результате принятого перевода терминов "proposition" и "sentence", – согласуется, по-видимому (с учетом указанной расширительности истолкования), с употреблением этих терминов в отечественной литературе.

5. Термин "высказывание" имелось в виду оставить для того неопределенного случая, когда не уточняется, идет ли речь о предложении или о суждении (в разъясненном только что понимании этих терминов). Именно с такой Ситуацией сталкивается читатель книги Гильберта и Аккермана (с этой точки зрения употребление в русском переводе этой книги термина "высказывание" следует признать удачным).

6. Английский термин "decision problem" переводится русским термином "проблема разрешения", что является терминологическим новшеством. Раньше (см., например, русское издание книги Клини) это же понятие по навязчивой традиции неудачно обозначалось термином "проблема разрешимости". Представляется целесообразным отказаться, наконец, от этой традиции и проблему поиска разрешающей процедуры назвать проблемой разрешения. Проблемой разрешимости (данной проблемы А) естественно называть следующую проблему: "узнать, разрешима ли проблема А".

Предисловие

Предлагаемая книга является исправленным и значительно расширенным изданием Введения в математическую логику, часть I (Introduction to Mathematical Logic, Part I >, которое было опубликовано в 1944 г. в серии Annals of Mathematics Studies. Несмотря на обширные добавления, она остается введением, а не всеобъемлющим исследованием. Эта книга задумана в качестве учебника для студентов-математиков, а также, в известных пределах, и в качестве справочника. В качестве учебника она содержит начальный курс математической логики, но предполагает у читателя существенную математическую подготовку.

Отличительной чертой нового издания является наличие большого числа упражнений для студентов. Некоторые из этих упражнений имеют элементарный характер и являются просто иллюстрациями; другие представляют собой по существу краткие наброски сложных проблем, изложению которых можно было бы посвятить целые параграфы основного текста; наконец, имеются упражнения, занимающие различные промежуточные положения. Мы не пытались систематически классифицировать упражнения по их трудности. Однако начинающему в качестве основы для выбора мы рекомендуем следующий примерный список: 12.3–12.9, 14.0–14.8, 15.0–15.3, 15.9, 15.10, 18.0–18.3, 19.0–19.7, 19.9, 19.10,23.1–23.6, 24.0–24.5, 30.0–30.4 (если потребуется – с посторонней помощью), 34.0, 34.3–34.6, 35.1, 35.2, 38.0–38.5, 39.0, 41.0, 43.0, 43.1, 43.4, 45.0, 45.1, 48.0–48.11, 52.0, 52.1, 54.2–54.6, 55.1, 55.2, 55.22, 56.0–56.2, 57.0–57.2.

Для того чтобы опубликовать том I, книга была довольно случайным образом разделена на две части, так что во многих случаях пришлось сделать ссылки на различные места еще не написанного тома II. Чтобы читатель мог себе хотя бы в общих чертах представить, о чем в соответствующих местах идет речь, в конце оглавления настоящего, первого тома добавлено предполагаемое содержание тома II, в свете чего и следует понимать эти ссылки.

Том I автор писал в течение ряда лет, начиная с 1947 г., и по мере того, как завершались отдельные части работы, они становились доступными в форме рукописи в библиотеке Принстонского университета. Работа выполнялась в течение отпуска в Принстонском университете с сентября 1947 г. по 1 февраля 1948 г., а затем по соглашению между Принстонским университетом и Управлением военно-морских исследований США с 1 февраля по 30 июня 1948 г. За этот период были написаны введение и главы I и II, хотя в этот материал в дальнейшем и были внесены некоторые незначительные изменения; в частности, были добавлены упражнения 15,4, 18.3, 19.12, 24.10, 26.3(2), 26.3(3), 26.8, 29.2, 29.3, 29.4, 29.5, а также исправлены ошибки и приняты во внимание новейшие публикации. Остальная часть работы была выполнена в течение 1948–1951 гг. по субсидии от Фонда научных исследований Принстонского университета и фонда треста Юджина Хиггинса; именно эти два фонда сделали возможным написание второй половины настоящего тома.

Что касается персональной помощи, то я по-прежнему благодарен лицам, перечисленным в предисловии к изданию 1944 г., за оказанное ими содействие, и в особенности С.А.Трусделу, чьи замечания относительно лекций 1943 г. сохранили большое значение и были полезными как при написании тома I, так и в предварительной работе, проделанной над материалом тома II, несмотря на значительные отклонения от содержания и построения первоначальных лекций. Я также благодарен всем тем, кто прочел новую рукопись или ее части и сделал ценные замечания или исправления, и среди них особенно Е.Адлеру, А.Ф.Баушу, У.У.Буну, Леону Хенкину, Дж.Кемени, Морису Л'Аббэ, Е.А.Мейеру, Паулю Майеру, И.Л.Новаку и Ралону Уэллсу.

(Добавлено 28 ноября 1955 г.) Я, далее, благодарен за указания, которые могли быть учтены только в корректурах, А.Н.Прайору, Т, Т.Робинсону, Хартли Роджерсу младшему, Дж.Шепердсону, Ф.О.Уайзу и Г.Зубиетта Русси и за помощь в чтении самих корректур Майклу Рэбину и Зубиетта; за ценное участие в составлении указателей я особенно благодарен Робинсону и Зубиетта.

Об авторе

Выдающийся американский математик и логик. Родился в Вашингтоне. В 1924 г. получил степень бакалавра в Принстонском университете, в 1927 г. защитил диссертацию под руководством известного математика О. Веблена. С 1929 г. преподавал математику в Принстоне. С 1936 г. редактор журнала "The Journal of Symbolic Logic". Профессор Принстонского университета (1947-1967). С 1967 г. профессор математики и философии Калифорнийского университета (Лос-Анджелес).

Работы А. Чёрча оказали сильное влияние на развитие математической логики и теории алгоритмов. В 1935 г. он построил первый пример неразрешимой массовой проблемы, а позже дал доказательство неразрешимости проблемы для узкого исчисления предикатов. В 1936 г. выдвинул основную гипотезу теории вычислимых функций (так называемый тезис Чёрча). Он внес существенный вклад в развитие комбинаторной логики: ему принадлежат исследования в области логической семантики и модальной логики. Разработанная им система лямбда-исчислений легла в основу функциональных языков программирования, в частности, семейства Лисп.