СЕРИЯ

Новое в жизни науке технине

математика кибернетика

1968

7

Г. ИВС

К. В. НЬЮСОМ

О математической логике и философии математики

Г. ИВС, К. В. НЬЮСОМ

О МАТЕМАТИЧЕСКОЙ ЛОГИКЕ И ФИЛОСОФИИ МАТЕМАТИКИ

(Начальные сведения об основаниях математики)

Перевод с английского Ф. Л. Варпаховского

ИЗДАТЕЛЬСТВО «ЗНАНИЕ»

Москва 1968

51 И25

СОДЕРЖАНИЕ

Стр.

ПРЕДИСЛОВИЕ . ......... ............. . 3

1. СИМВОЛИЧЕСКАЯ ЛОГИКА.................. 5

2. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ................ . 14

3. ДРУГИЕ ЛОГИКИ......................... 24

4. КРИЗИС ОСНОВ МАТЕМАТИКИ ................ 31

5. ФИЛОСОФИЯ МАТЕМАТИКИ ................... 37

ЗАДАЧИ . ........... . . .................. . . 45

2-2-1

БЗ № 43 1968 г. № 1

Г. ИВС, К. В. НЬЮСОМ

(перевод с английского Ф. Л. Варпаховского)

О МАТЕМАТИЧЕСКОЙ ЛОГИКЕ И ФИЛОСОФИИ МАТЕМАТИКИ

Редактор В. Ю. Иваницкий Художник Л. Г. Ординарцев Худож. редактор Е. Е. Соколов Техн. редактор Е. М. Лопухова Корректор Г. П. Трибунская

Сдано в набор 1/IV 1968 г. Подписано к печати 26/VI 1968 г;

Формат бумаги 60 × 901/16 Бумага типографская № 3 Бум. л. 1,5 Печ. л. 3,0. Уч.-изд. л. 2,63. Зак. 391. Тираж 50 000 экз. Цена 9 коп.

Набрано в тип. ЦИНТИ Госкомзага, Москва, Мукомольный пр., д. 8.

Отпечатано в тип. изд-ва «Знание». Москва, Новая пл., д. 3/4. Зак. 1872,

ПРЕДИСЛОВИЕ

Настоящая брошюра содержит перевод заключительной главы книги известных американских математиков-педагогоз Говарда Ивса и Кэролла Ньюсома «Введение в основания и основные понятия математики»*. Эта книга, пользующаяся в Соединенных Штатах известной популярностью и выдержавшая уже несколько изданий, представляет собой элементарный учебник для студентов — будущих преподавателей математики; от имеющихся в нашей литературе учебников она отличается в первую очередь отказом от ориентации на какой-то один определенный раздел математической науки: в этой книге авторы затрагивают вопросы, относящиеся к арифметике и к алгебре, к геометрии и к математическому анализу. Основной целью, которую преследуют авторы, служит ознакомление неискушенного читателя с тем, что следует назвать «математическим методом», с общим характером построения математических теорий и методами рассуждений.

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

* H. Eves, C. V. Newsom. An Introduction to the Foundations and Fundamental Concepts of Mathematics. N. Y. Holt, Rinehart and Winston.

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

И. М. Яглом

1. СИМВОЛИЧЕСКАЯ ЛОГИКА

Каждая математическая теория (или аксиоматическая теория) «стоит на двух китах» — она базируется на некотором множестве постулатов или аксиом и на логике. В то время как система аксиом образует основу теории, логика дает те правила, согласно которым из аксиом могут быть выведены теоремы. Математическая теория включает в себя всю совокупность утверждений — как постулатов или аксиом, так и теорем.

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

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

Считается, что Лейбниц первым серьезно рассматривал вопрос о необходимости создания символической логики. В одной из своих ранних работ «Искусство комбинаторики» (De arte combinatoria), опубликованной в 1666 г., он говорит о желательности введения универсального научного языка, созданного на основе целесообразно подобранной символики и слу-

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

Идея создания символической логики вновь привлекает внимание ученых в связи с появлением в 1847 г. памфлета Джорджа Буля, озаглавленного «Математический анализ логики или опыт исчисления дедуктивных умозаключений» (The Mathematical Analysis of Logic, Being an Assay towards a Calculus of Deductive Reasoning). Следующая его работа была опубликована в 1848 г., и наконец в 1854 г. Буль излагает свои замечательные идеи в трактате «Исследования законов мышления, на коих основаны математические теория логики и вероятностей» (An Investigation into the Laws of Thought, on Which Are Founded the Mathematical Theories of Logic and Probability).

В 1847 г. современником Буля — Августусом де Морганом (Augustus De Morgan, 1806—1871) был опубликован трактат по формальной логике «Формальная логика или исчисление выводов, необходимых и возможных» (Formal Logic, or the Calculus of Inference, Necessary and Probable); в этом трактате Морган в некоторых отношениях идет значительно дальше Буля. Позднее Морган успешно изучает логику отношений— область, не охваченную исследованиями его предшественников.

В Соединенных Штатах выдающиеся работы по логике принадлежат Чарльзу Пирсу (Charles Sanders Peirce, 1839—1914), сыну известного гарвардского математика Бенджамина Пирса. Им были вновь открыты многие из выдвигавшихся ранее принципов. К сожалению, работы Пирса оказались вне русла нормального научного развития и только сравнительно недавно его идеи были по достоинству оценены.

Наиболее полным образом теория Буля была развита в обширном трактате Эрнста Шредера (Ernest Schöder, 1841—1902) «Лекции по алгебре логики» (Vorlesungen über die Algebra der Logic), опубликованном в период с 1890 по 1895 г. С тех пор направление в логике, идущее от Буля, специалисты называют обычно алгеброй Буля—Шредера*. Алгебра Буля продолжает развиваться, и в современных научных журналах можно найти статьи, посвященные исследованию различных относящихся сюда вопросов.

Опубликованные в 1879—1903 гг. труды немецкого ученого Готлоба Фреге (Gottlob Frege, 1848—1925) и исследования выдающегося итальянского математика Пеано (Peano) кладут начало новым направлениям в математической логике.

* В нашей литературе чаще употребляется более краткий термин: «алгебра Буля».

Пеано считал желательным построить всю математику на базе логического исчисления, а Фреге исходил из необходимости более надежного обоснования математической науки. Работа Фреге «Исчисление понятий» (Begriffsschrift) появилась в 1879 г., а его «Основания арифметики» (Grundgesetze den Arithmetik), имевшие важное историческое значение,— в 1893—1903 гг.; «Математический формуляр» (Formulaire de mathématiques) Пеано и его сотрудников начал выходить в 1894 г. Используя достижения Фреге и Пеано, Уайтхед (Whitehead) и Рассел (Russell) создают в 1910—1913 гг. свои «Принципы математики» (Principia mathematica)—фундаментальный труд, оказавший исключительное влияние на все последующее развитие математической логики. В этой работе математика отождествляется с логикой, поскольку система натуральных чисел, а стало быть, и почти вся математика строится дедуктивным образом на основе некоторого множества постулатов логики. Период с 1934 по 1939 г. ознаменован выходом в свет «Оснований математики» (Grundlagen der Mathematic)—всеобъемлющего трактата Давида Гильберта (David Hilbert) и Поля Бернайса (Paul Bernays), созданного на основе некоторых работ Гильберта и его университетских лекций. Авторы пытаются построить математику с помощью символической логики таким образом, чтобы могла быть решена задача о непротиворечивости математики.

Появление «Принципов математики» дало мощный толчок развитию символической логики, и в настоящее время значительная группа математиков сосредоточила свои усилия в этой области. Работы логиков печатаются в специальном «Журнале символической логики» (Journal of Symbolic Logic), основанном в 1935 г.

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

Любые утверждения, об истинности или ложности которых имеет смысл говорить1, мы будем называть высказываниями; при этом мы можем и не знать, истинно ли данное высказывание или нет. Высказываниями являются, например, следующие утверждения: «весна является временем года», «8 есть простое число», «9000-я цифра в десятичной записи числа π

1 Мы не будем касаться здесь семантического вопроса о значении слов «истинный» и «ложный».

есть 7». Первое из этих утверждений истинно, второе—ложно; истинность или ложность третьего утверждения нам не известна, однако, поскольку и в отношении этого утверждения имеет смысл говорить об истинности или ложности, его также следует считать высказыванием. Высказывания мы будем обозначать строчными буквами латинского алфавита m, n, р, q, r,...; условимся также, что в случае, когда говорится о высказывании р без указания на его истинность или ложность, подразумевается, что р истинно.

Различным образом сочетая высказывания между собой, мы можем получить новые высказывания. Например, из двух высказываний «весна является временем года», «8 есть простое число» можно получить следующие высказывания: «весна является временем года и 8 есть простое число», «весна является временем года или 8 есть простое число», «если весна является временем года, то 8 есть простое число», «весна является временем года тогда и только тогда, когда 8 есть простое число». Наконец, из единственного высказывания «весна является временем года» можно получить новое высказывание «весна не является временем года», то есть высказывание, являющееся отрицанием первого.

Приведенные выше сочетания высказываний образуются при помощи слов «и», «или», «если—то», «тогда и только тогда, когда», «не». В математической логике для обозначения этих основных типов сочетания используются специальные символы, а именно вводятся следующие пять символов:

(1) р∧q (читается «р и q») обозначает высказывание, истинное в том только случае, когда р и q оба истинны. Такое высказывание называют конъюнкцией высказываний р и q.

(2) p∨q (читается «р или q») обозначает высказывание, истинное тогда лишь, когда по крайней мере одно из высказываний р и q истинно (но могут быть истинными и оба высказывания). Такого рода высказывание называют дизъюнкцией высказываний р и q.

(3) р → q (читается «если р, то q») обозначает высказывание, которое ложно в том только случае, когда p истинно, a q ложно, и истинно во всех остальных случаях. Такое высказывание называется импликацией высказываний р и q.

(4) p←→q (читается «р тогда и только тогда, когда q») обозначает высказывание, истинное тогда только, когда р и q оба истинны или оба ложны. Следовательно, утверждение p←→q означает, что р и q имеют одно и то же «значение истинности». Такое высказывание называют эквивалентностью высказываний р и q.

(5) р' (читается «не р») есть противоположность р, то есть р' обозначает высказывание, которое истинно, когда р ложно,

и ложно, когда р истинно. Такое высказывание называют отрицанием высказывания р1.

Заметим, что символы ∧, ∨, →, ←→ обозначают бинарные операции, определенные на множестве всех высказываний, а символ ' выражает определенную на том же множестве унарную операцию*.

Следует также сказать, что слова «и», «или», «если — то», «тогда и только тогда», являющиеся связками в нашем обычном языке, в математической логике получают несколько иной смысл.

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

Он сел в поезд и приехал в Бостон.

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

Весна является временем года и 8 есть простое число.

Аналогично союз или в обычном языке употребляется в двух смыслах — в смысле исключающем от латинского aut («р или q, но не оба») и в смысле неисключающем от латинского vel («р или q или оба»). Именно в этом последнем' смысле используется или в логике. И здесь опять же несущественны смысловая связь или смысловая зависимость соединяемых высказываний.

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

Если будет дождь, то мы останемся дома.

С другой стороны, в логике импликация p→q связывает любые два предложения и, по определению (3), ложность импликации имеет место в том единственном случае, когда р истинно, a q ложно. Любопытно отметить, что для истинности импликации достаточно, чтобы р было ложно или q истинно.

1 Приведенная здесь символика для обозначения конъюнкции, дизъюнкции, импликации, эквивалентности и отрицания не является общепринятой и неодинакова у разных авторов. Так, Уайтхед и Рассел используют символы р — q, р ∨ q, р ) q, р не q, ~ р, а у Гильберта мы находим следующие обозначения: p&q, p∨q, p→q, p~q, p.

* Другими словами, операция A, V, → и «→ алгебры логики сопоставляют новое высказывание двум высказываниям (р и q), а операция ' сопоставляет новое высказывание одному высказыванию (р).

Таким образом, все три приводимые ниже импликации должны считаться истинными:

Если 7— простое число, то 2×2 = 4,

Если 8 — простое число, то 2×2=4,

Если 8 — простое число, то 2×2 = 5.

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

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

7 есть простое число тогда и только тогда, когда 2×2 = 4,

8 есть простое число тогда и только тогда, когда 2×2 = 5 оба являются истинными.

Все, что здесь говорилось о логическом смысле конъюнкции, дизъюнкции, импликации, эквивалентности и отрицания, можно просто и наглядно проиллюстрировать с помощью так называемых таблиц истинности. В этих таблицах буква И означает истинность соответствующего высказывания, буква Л — ложность.

Приведем таблицу истинности для конъюнкции.

Эта таблица построена на основании данного выше определения конъюнкции. Из таблицы следует, что р∧q истинно, если р и q оба истинны, и ложно во всех остальных случаях. В таблице выписываются все возможные комбинации И и Л для составляющих высказываний, а в последней колонке указывается истинность или ложность сложного высказывания для каждой такой комбинации,

Таблица 1 Конъюнкция

1 На выбор подходящего определения импликации влияют противоречивые обстоятельства, и многие исследователи трактуют вопрос по-разному. Импликацию, как мы ее определили, называют материальной (material) импликацией. Льюис (Lewis) ввел понятие строгой (strict) импликации, которое в большой степени соответствует отношению посылки « следствия, когда последнее может быть выведено из первого; пока, однако, никакое определение импликации, апеллирующее к структуре составляющих ее предложений, не является общепринятым. Во всяком случае в любом определении импликации доминирует идея материальной импликация и вне зависимости от принятого определения в конечном счете мы приходим именно к материальной импликации.

Вот так выглядят таблицы истинности для дизъюнкции, импликации, эквивалентности и отрицания.

Таблица 2 Таблица 3

Дизъюнкция Импликация

Таблица 4 Таблица 5

Эквивалентность Отрицание

Составляющие высказывания сами могут иметь более сложную структуру, например,

[p∧(p→q)]→q;

при этом истинность или ложность полученного высказывания для любых комбинаций И и Л первоначальных высказываний может быть определена с помощью таблиц истинности для конъюнкции, дизъюнкции, импликации, эквивалентности и отрицания. Так, для только что полученного высказывания находим:

Таблица 6

Первый, второй и последний столбцы дают нам таблицу истинности для нового высказывания; третий и четвертый столбцы являются вспомогательными. Полученная таблица обладает тем любопытным свойством, что в последнем ее столбце стоят одни только И. Это означает, что рассматри-

ваемое высказывание истинно, каковы бы ни были р и q. Такие высказывания называют тавтологиями или законами логики. Читатель легко может убедиться, что следующие высказывания являются тавтологиями.

Таблица 7

Некоторые законы логики

Название закона

Закон исключенного третьего

Закон противоречия

Закон силлогизма

Закон двойного отрицания

Закон контрапозиции

Если составить таблицы истинности для высказывания p→q и q'→p', то окажется, что они одновременно истинны или одновременно ложны. Два таких высказывания m и n называются логически эквивалентными; как легко видеть, высказывание m ←→ n является тавтологией или законом логики. Следовательно, высказывание (p→q)←→(q'→p') является законом логики в соответствии с тем, что было указано в последней таблице. Понятие логической эквивалентности имеет важное значение, поскольку от всякого высказывания можно перейти к логически эквивалентному высказыванию, сохраняя значение истинности (или ложности) для первоначального высказывания. Так, высказывание q'←p' может быть во всех случаях заменено высказыванием p→q. Точно так же (р')' можно везде заменять на р.

Мы предоставляем читателю доказательство логической эквивалентности следующих пар высказываний:

Таблица 8

Некоторые пары логически эквивалентных высказываний

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

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

Интересно отметить, что дизъюнкция может быть определена с помощью одной лишь импликации, поскольку р ∨q и (p→q)→q логически эквивалентны; однако аналогичное определение для конъюнкции невозможно.

Г. Шеффер (H. M. Sheffer) показал в 1913 г., что для определения всех логических операторов достаточно ввести единственный оператор—так называемый штрих Шеффера. Штрих Шеффера записывается в виде p/q и означает «не р или не q». Читатель легко увидит, что высказывания р/р и р', а также (p/p)/(q/q) и p∨q логически эквивалентны. Поскольку дизъюнкция и отрицание выражаются через штрих Шеффера, то и остальные основные логические операторы также определяются с помощью штриха Шеффера.

2. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ

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

С этой точки зрения важнейшей задачей логики должно,, очевидно, считаться исследование тавтологий, т. е. отыскание всех тех сложных высказываний, которые являются истинными независимо от ложности или истинности составляющих высказываний р, q, r,... Такие высказывания являются законами логики и лежат в основе всякого правильного формального рассуждения. Тавтологичность высказывания мы всегда в состоянии точно обнаружить с помощью таблиц истинности. Однако эти таблицы не дают нам средства для составления сколь-нибудь полного и систематического перечня тавтологий, Успешное достижение поставленной цели осуществляется с помощью метода, изложению которого посвящен настоящий раздел. Мы покажем, что все тавтологии могут быть выведены на основе точно формулированных правил из некоторого специально выбранного множества тавтологий. Более того, указанный метод будет приводить к одним лишь тавтологиям, т. е. не нужно будет тавтологии отделять от нетавтологий, как это пришлось бы делать в случае использования таблиц истинности. Поскольку в новом методе обнаружение тавтологий осуществляется с помощью символических вычислений, соответствующая теория называется исчислением высказываний.

Теорию исчисления высказываний мы будем строить в основном так же, как это делали Уайтхед и Рассел в своих «Принципах математики». Замечательно то обстоятельство, что теория эта является аксиоматической. Несколько тавтологий, выбранных из всего их множества, будут служить в качестве аксиом, и, кроме того, мы укажем некоторые формальные правила, согласно которым остальные тавтологии могут быть выведены из тавтологий-аксиом. Эти правила в теории исчисления высказываний играют такую же роль, какую логические правила вывода играют при построении любой математической теории. Конечно, сами логические правила вывода не могут здесь оказаться полезными, поскольку они именно и составляют объект изучения.

Приведем (с краткими пояснениями) первоначальные понятия, аксиомы и правила вывода теорем для теории исчисления высказываний.

Первоначальные понятия

Первоначальными (или неопределяемыми) понятиями в теории исчисления высказываний будем считать:

(1) множество Р элементов р, q, r,..., называемых высказываниями,

(2) бинарную операцию на Р, обозначаемую символом ∨, и

(3) унарную операцию на Р, обозначаемую символом '. Поскольку, как это было указано в первом разделе, остальные логические операторы ∨, → и ←→ выражаются через эти два, их нет необходимости причислять к первоначальным понятиям. Следует отметить, что если р и q принадлежат р, то p∨q и р' также принадлежат р, т. е. они также являются высказываниями.

Аксиомы или исходные тавтологии

Все тавтологии являются высказываниями, однако не всякое высказывание есть тавтология. Из всего множества тавтологий выбираются четыре в качестве аксиом или исходных тавтологий. Исходные тавтологии мы будем обозначать через A1, A2, A3, A4; приведем их здесь, введя предварительное определение, облегчающее запись тавтологий.

Определение 1. p→q означает p'∨q.

В «Принципах математики» аксиома A1 носит название принципа тавтологии. Нетрудно видеть, что в A1 мы могли бы утверждать и нечто большее, чем просто импликацию, так как (p∨p)←→p также есть тавтология. Однако поскольку тавтологичность высказывания p→(p∨p) легко может быть доказана, то эту часть утверждения об эквивалентности высказываний р и (p∨p) незачем принимать в качестве аксиомы.

Аксиома A2 выражает то обстоятельство, что дизъюнкция истинна, если истинно одно из составляющих ее высказываний. Уайтхед и Рассел называют A2 принципом добавления.

Аксиома A3, называемая принципом перестановки, выражает коммутативность дизъюнкции. Здесь снова имеет место эквивалентность, а не просто импликация, однако постулировать эквивалентность нет необходимости.

Аксиому A4 называют принципом суммирования. В этой аксиоме отражен тот факт, что импликация остается справедливой, если ее предшествующий и последующий члены q и r заменить соответственно на p∨q и p∨r. Для аксиомы A4 существует простой аналог в арифметике натуральных чисел: если а<b, то а+с<b + с.

Правила вывода теорем или отыскания тавтологий

Сформулируем четыре основных правила, позволяющих выводить новые тавтологии из первоначальных.

П 1 (правило подстановки): Из данной тавтологии можно получить новую тавтологию, если высказывание р в данной тавтологии заменить везде высказыванием q.

Например, подставляя в A2 высказывание p∨q вместо высказывания q, получаем новую тавтологию

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

Например, замена q→r на q'∨r в тавтологии A4 дает новую тавтологию.

П 3 (правило отделения или правило импликации). Из двух данных тавтологий m и m→n следует новая тавтология n.

Четвертое правило нам будет удобнее сформулировать, введя предварительно следующее определение: Определение 2: p∧q означает (p'∨q').

Приводим теперь правило П41.

П4 (правило адъюнкции). Из двух данных тавтологий m и n следует новая тавтология m∧n.

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

Теорема 1 :

Доказательство:

(Эта теорема указывает одну из форм транзитивности импликации.)

Теорема 2: p→(p∨p).

Доказательство:

Теорема 3: р→р Доказательство:

(В этой теореме утверждается, что из всякого высказывания следует само это высказывание — свойство рефлексивности импликации.)

Теорема 4: р'∨р

Доказательство: р→р (теорема 3)

Теорема 5: p∨р'. Доказательство:

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

(Мы получим закон исключенного третьего, который можно сформулировать так: «или р истинно или р ложно» либо «или р или не-р истинно»).

Теорема 6:

Доказательство:

(В этой теореме утверждается, что если из некоторого высказывания следует ложность этого высказывания, то само это высказывание ложно. Мы получили—в его наиболее простой форме — принцип приведения к абсурду). Можно доказать этот принцип и в несколько более общей форме, например:

Здесь говорится о том, что если из р следует одновременно и q и q', то высказывание р ложно. Ниже мы сформулируем принцип приведения к абсурду в его наиболее общей форме.

Теорема 7: p→(p')'.

Доказательство:

Теорема 8:

Доказательство:

Теорема 9:

Доказательство:

Теорема 10:

Доказательство:

Определение 3:

Теорема 11 :

Доказательство:

(Это—закон двойного отрицания.)

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

Теорема 12: Теорема 13: Теорема 14:

(Теоремы 12, 13, 14 показывают эквивалентность некоторых высказываний конъюнктивного, дизъюнктивного и импликативного типов. О значении логических эквивалентностей уже говорилось выше.)

Теорема 15: (р'→р)→р.

(Эта теорема устанавливает справедливость следующего рассуждения, часто используемого в доказательствах: если из ложности р следует истинность p, то высказывание р истинно.)

Теорема 16: (p→q)←→(q'→p').

(Это закон контрапозиции, который доказательство высказывания p→q сводит к доказательству высказывания q'→p').

Теорема 17: [(р→q)∧q']→р'.

(В геореме утверждается, что если из р следует q и q ложно, то р ложно.)

Теорема 18: [(р∨q)∧q']→p.

(В теореме утверждается, что в случае истинности р или q и ложности q р истинно.)

Теорема 19: [(р→q)∧(q→r)]→(р→r).

(Это закон силлогизма, дающий иную форму транзитивности импликации.)

Теорема 20: [р∧{[р∧q') →r]∧[(р∧q')→r']}]→q

(Эта теорема, согласно которой если из р и q' следует одновременно r и r' и если р истинно, то q истинно, дает наиболее общую форму принципа приведения к абсурду. В такой форме этот принцип часто используется в математических рассуждениях, причем р есть множество всех аксиом, a q есть доказываемая путем приведения к абсурду теорема: мы предполагаем q' или ложность q; если затем нам удается показать, что из множества аксиом р и ложности q следует пара

противоречивых высказываний r и r', то мы считаем, что q истинно.)

Теорема 21: q→(p→q).

Теорема 22: p'→(p→q).

(Теоремы 21 и 22 выражают два свойства материальной импликации, о которых мы уже говорили выше. Именно, в теореме 21 утверждается, что истинное высказывание q следует из любого высказывания, а в теореме 22—что из ложного высказывания р следует любое высказывание q.)

Теорема 23: (р∧p')'.

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

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

Все люди смертны.

Сократ — человек.

Следовательно, Сократ смертен.

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

В первом издании «Принципов математики» Рассел и Уайтхед строили исчисление высказываний на основе пяти аксиом. Кроме четырех аксиом A1, A2, A3, A4, которые были нами перечислены, они пользовались также аксиомой

Позднее, в 1926 г. Бернайсом1 было показано, что пятая аксиома не является: независимой и может быть выведена с помощью формулированных правил из аксиом A1, A2, A3 и A4. С другой стороны, Бернайс доказал, что эти последние аксиомы являются независимыми.

Следует отметить, что аксиоматическое построение теории можно осуществлять по-разному, в зависимости от выбора первоначальных понятий и аксиом. Построение Россера (J. В. Rosser) и Куайна (W. V. Quine) основывается, например, на выборе в качестве первоначальных операций конъюнкции и отрицания. Соответствующая система аксиом может быть представлена а такой форме:

Определение р→q означает (p∧q)'.

Правила вывода П1, П2, П3, П4 сохраняются без изменения. Еще в 1879 г. Фреге, приняв за исходные операции импликации и отрицания:, предложил иную систему из шести аксиом, сформулированных в терминах этих операций. Лукасевич (J. Lukasiewicz); доказал, что система аксиом Фреге может быть заменена более простой системой, состоящей всего лишь из трех аксиом:

И снова правила вывода П1, П2, П3, П4 остаются в силе. В 1916 г, Никод (J. Nicod)2 показал, что исчисление высказываний может быть построено на основании одного лишь оператора—штриха Шеффера—и единственной аксиомы

Правило отделения заменяется в этой конструкции правилом: Из двух данных тавтологий и и u/(v/w) следует новая тавтология до. Кроме рассмотренных здесь, были предложены также и другие построения исчисления высказываний.

Замечательно то, что исчисление высказываний является по существу интерпретацией алгебры множеств. Чтобы убе-

1 Benays Р. Axiomatische Untersuchung des Aussagen-Kalküls der Principia Mathematica. Mathematische Zeitschrift, 25 (1926), S. 305—320.

2 Nicod J. A reduction in the number of the primitive propositions of logic. (Об уменьшении числа аксиом логики).— Proceedings of the Cambridge Philosophical Society, 19 (1916), p. 32-42.

литься в этом, будем считать, что a, b, с,... в алгебре множеств означают высказывания, объединение U и пересечение П множеств означают ∨ и∧, равенство означает логическую эквивалентность, а универсальное (единичное) множество и пустое множество означают тавтологию U и отрицание тавтологии z соответственно. При такой интерпретации аксиомы булевой алгебры множеств переходят в следующие теоремы исчисления высказываний:

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

Указанное обстоятельство имеет чрезвычайно важное значение. Оно означает, что любая теорема алгебры Буля переходит в соответствующую теорему исчисления высказываний. Например, законы Де Моргана в алгебре Буля

дают следующие теоремы в исчислении высказываний:

Точно так же из принципа двойственности в алгебре Буля вытекает принцип двойственности в исчислении высказываний, формулируемый следующим образом: Любая тавтология в форме m←→n, где m и n выражены с помощью конъюнкции, дизъюнкции и отрицания, не перестает быть тавтологией, если в исходной тавтологии конъюнкцию везде заменить дизъюнкцией и наоборот.

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

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

3. ДРУГИЕ ЛОГИКИ

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

Уже довольно давно математики обнаружили, что первое из этих множеств, т. е. множество аксиом, можно менять сообразно поставленным целям, однако до самого последнего времени второе множество — множество утверждений, образующих логику теории, — считалось всеми учеными неизменным, абсолютным и непреложным. Даже сейчас большинство людей придерживается такой именно точки зрения. Законы логики, открытые Аристотелем в IV в. до н. э., представляются неспециалисту чем-то вечным, чем-то не допускающим альтернативы. По общему убеждению, аристотелевы законы являются как бы частью мироздания и присущи самой природе человеческого мышления. Лишь в 1921 г. с этим заблужде-

нием было покончено, как и со многими другими заблуждениями прошлого. Современную точку зрения чрезвычайно удачно выразил выдающийся американский логик Алонзо Черч (Alonzo Church). Вот что он пишет:

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

Напомним, что новые геометрии появились впервые в связи с отрицанием постулата Эвклида о параллельных, а новые алгебры возникли после того, как был отвергнут закон коммутативности умножения. Аналогично новые, так называемые «многозначные логики» появились впервые в связи с отрицанием аристотелева закона исключенного третьего. В соответствии с этим законом дизъюнктивное высказывание р∨р' есть тавтология, а высказывание р в аристотелевой логике всегда либо истинно, либо ложно. Поскольку здесь всякое высказывание может принимать одно из двух значений истинности,

1 A. Church. A set of postulates for the joundation of logic— Annals of Mathematics, 33 (1932), p. 343—349.

именно истину или ложь, аристотелева логика получила название двузначной логики. В 1921 г. Лукасевич в маленькой двухстраничной статье рассматривает трехзначную логику, т. е. такую логику, в которой всякое высказывание р может принимать одно из трех возможных значений истинности. Вскоре после этого и независимо от Лукасевича Пост (Е. L. Post) анализирует m-значную логику, в которой высказывание р может принимать одно из m возможных значений истинности, причем m—любое целое число, большее 1. В случае, когда m больше 2, логику называют многозначной. В 1930 г. Лукасевич и Тарский (Tarski) предпринимают дальнейшее изучение m-значной логики. В 1932 г. понятие m-значной логики обобщается Рейхенбахом (Н. Reichenbach), рассматривающим бесконечнозначную логику, в которой для высказывания р существует бесконечное множество значений истинности1.

Рассмотренные логики не исчерпывают всех новых логик. Так, например, Гейтинг (A. Heyting) построил двузначную символическую логику, исходя из потребностей интуционистской математической школы; эта логика, в отличие от аристотелевой, не принимает безоговорочно законов исключенного третьего и двойного отрицания. Вследствие этого законы созданной со специальными целями логики Гейтинга, так же как и законы многозначных логик, отличаются от законов Аристотеля. Все такие логики называют неаристотелевыми. Символическая двузначная логика, построенная в «Принципах математики» и рассмотренная нами в предыдущем разделе, принадлежит к числу неаристотелевых логик, отличаясь от аристотелевой логики иной интерпретацией импликации.

Подобно неэвклидовым геометриям, неаристотелевы логики также нашли себе приложения. Бесконечнозначная логика была задумана Рейхенбахом в качестве фундамента математической теории вероятностей. А в 1933 г. Звицкий (T. Zwicky) обнаружил, что многозначные логики могут быть использованы современной квантовой физикой. Многие аспекты такого использования были исследованы Г. Биркгофом (G. Birkhoff), фон Нейманом и Рейхенбахом. Можно с уверенностью сказать, что неаристотелевы логики сыграют свою роль в будущем развитии математики, однако в чем именно это выразится, сказать пока трудно; использование интуиционистами логики Гейтинга свидетельствует о математической ценности

1 Здесь уместно упомянуть об одном интересном историческом обстоятельстве: в 1906 г. Михальский обнаружил, что трехзначная логика была предвосхищена еще в XIV в. средневековым схоластом Уильямом из Окама (William of Occam). Возможность существования трехзначной логики рассматривалась также философом Гегелем и, в 1896 г., Хью Макколом (Hugh MacColl). Однако их идеи почти никакого влияния на последующее развитие логики не оказали и решающего значения не имели.

новых логик. В следующем разделе мы укажем на некоторые возможные приложения этих логик к разрешению современного кризиса основ математики.

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

Мы будем пользоваться методом таблиц истинности и начнем с таблицы истинности для конъюнкции. Воспроизведем прежде всего эту таблицу, придав ей более удобный вид таблицы умножения, как это показано на рисунке. Табл. построена следующим образом. В левом столбце приводятся возможные значения истинности для высказывания р, а и верхней строке — возможные значения истинности для высказывания q. Зная значения истинности для р и для можно найти значение истинности для p∧q в клетке, стоящей на пересечении строчки, соответствующей значению истинности р, и столбца, соответствующего значению истинности q. Поскольку по определению p∧q истинно в том и только в том случае, когда р и q оба истинны, И стоит в левой верхней клетке таблицы и Л—во всех остальных ее клетках. Отметим, что таблица заполняется на основании одного лишь определения p∧q.

Переходим теперь к трехзначной логике и вновь условимся, что p∧q истинно тогда и только тогда, когда р и q оба истинны. Обозначив три возможных значения истинности высказывания через И, ? и Л, приступаем к составлению таблицы истинности (см. табл. 10). По нашему соглашению относительно высказывания р∧q левая верхняя клетка таблицы должна содержать И, и, кроме того, И не может находиться ни в какой другой клетке таблицы. Поскольку остается во-

Таблица 9

Таблица 10

семь клеток, каждая из которых может быть заполнена одним из двух возможных способов (выбирается либо Л либо ?), то получается всего 28=256 способов заполнения таблицы. Отсюда следует, что в трехзначной логике существует 256 различных возможностей определения конъюнкции!

Таблица 11

Таблица 12

В таблицах 11 и 12 приводятся две из числа 256 возможных таблиц истинности для конъюнкции в трехзначной логике. Таблица истинности И была выбрана Лукасевичем, Постом и Россером, она, строится на основании соглашения, по которому ? более ложно, чем И; Л более ложно, чем ?, а значение истинности р∧q совпадает со значением истинности более ложного из составляющих высказываний. Иное определение конъюнкции дает Бочвар (см. табл. 12); по Бочвару символ «?» означает неразрешимость, а конъюнкция p∧q считается неразрешимой в случае неразрешимости хотя бы одного из составляющих высказываний р и q.

Рассмотрим далее таблицу истинности для отрицания. В случае отрицания единственное ограничение заключается в том, что р' не может быть истинным в случае истинности р и р' не может быть ложным в случае ложности р. Указанное ограничение полностью определяет таблицу истинности для отрицания в двузначной логике и допускает 12 возможных способов определения отрицания в трехзначной логике. Ниже приведены две из 12 возможных таблиц. Таблица истинности 13 была выбрана Постом; она построена на основании соглашения, по которому в трехзначной логике [(p)']' и р эквивалентны (по аналогии с эквивалентностью (р)' и р в двузначной логике). Таблица 14 была предложена Бочваром, Лукасевичем и Россером, которые исходили из того, что (р')' должно быть эквивалентно р.

Таблицы истинности для других логических операций могут быть построены далее на основании определения этих свя-

зок с помощью конъюнкции; и отрицания. Поскольку конъюнкция и отрицание независимы, а остальные операции, как мы видели, могут быть через ивх выражены, то существует в общей сложности 256×12 = 3072 различных трехзначных логик. Таким образом, число различных возможных структур многозначной логики чрезвычайно велико.

Таблица 13

Таблтца 14

Иногда при построении многозначных логик каждому высказыванию р ставится в соответствие некоторое действительное число Т(р) отрезка [0,1]; число это называют значением истинности р. Значение истинности р можно понимать, таким образом, как вероятность того, что р истинно, а два высказывания, имеющие одно и то же значение истинности, можно считать логически эквивалентными. Значение истинности 1 означает истинность, а значение истинности 0 означает ложность. Отрицание р' определяется в терминах значений истинности следующим образом: Т(р') = 1—Т(р). В трехзначной логике, например, в качестве значений истинности можно принять числа 0, 1/2 и 1. Если значение истинности р равно 1/2, то значение истинности р' также равно 1/2, и р оказывается логически эквивалентным своему отрицанию. Такое высказывание может быть названо сомнительным, причем отрицание этого высказывания также оказывается сомнительным. Указанный подход свидетельствует о наличии тесной связи между многозначными логиками и теорией вероятностей.

Быть может, приведенные выше фрагментарные сведения дадут читателю некоторое представление о неаристотелевых логиках. Из всего сказанного следует одно замечательное обстоятельство: конструктивное отрицание традиционных убеждений является мощным источником научных открытий и имеет первостепенное значение для развития науки. Когда Эйнштейна спросили, как он пришел к открытию теории относительности, Эйнштейн ответил: «Отвергнув аксиому». Лобачевский и Больяи отвергли эвклидову аксиому о параллель-

ных, Гамильтон и Кэли (Cayley) отвергли аксиому о коммутативности умножения, Лукасевич и Пост отвергли аристотелеву аксиому исключенного третьего. Точно так же обстояло дело и в других науках: Коперник отверг аксиому геоцентричности, Галилей отверг аксиому о более быстром падении более тяжелого тела, Эйнштейн отверг аксиому, согласно которой из двух данных моментов времени один предшествует другому. Конструктивному отрицанию аксиом математика обязана многими своими достижениями, и именно это обстоятельство выражено в знаменитом афоризме Кантора: «Сущность математики заключается в ее свободе».

4. КРИЗИС ОСНОВ МАТЕМАТИКИ

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

Первый кризис основ математики произошел в V в. до н. э. — во всяком случае не раньше, поскольку, как мы знаем, сама математика оформилась в качестве дедуктивной науки в VI в. до н. э., по-видимому, в связи с работами Фалеса, Пифагора и их учеников. Первый кризис был вызван неожиданным открытием — оказалось, что не все однородные геометрические величины соизмеримы друг с другом; было, например, показано, что диагональ квадрата несоизмерима с его стороной. Поскольку учение Пифагора о величинах покоилось на твердой интуитивной уверенности в соизмеримости однородных величин, обнаружение ошибочности этого убеждения нанесло громадный урон всему учению. Так, пифагорова теория пропорций со всеми ее следствиями должна была быть отброшена ввиду своей необоснованности. Первый кризис основ математики преодолевался медленно и нелегко. Конец кризиса относится примерно к 370 г. до н. э. и связан с именем выдающегося математика Евдокса — построенная им теория величин является одним из величайших творений математики за всю ее историю. Замечательное учение Евдокса о несоизмеримостях можно найти в пятой книге «Начал» Эвклида; в основном оно совпадает с современной теорией иррациональных чисел, построенной Рихардом Дедекиндом в 1872 г*. Этот кризис основ математики сыграл выдающуюся роль в становлении математического метода.

Открытия Ньютона и Лейбница, зарождение анализа в конце XVII в. привели ко второму кризису основ математики1. Как мы знаем, последователи Ньютона и Лейбница, увлеченные громадными практическими возможностями и силой нового метода, мало заботились о прочности фундамента, на котором был построен анализ, так что не доказательства га-

* Р. Дедекинд. Непрерывность и иррациональные числа. Одесса, Mathesis, 1923.

1 Предпосылки этого кризиса можно найти уже в знаменитых парадоксах Зенона, относящихся примерно к 450 г. до н. э.

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

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

Первый из опубликованных парадоксов теории множеств был обнаружен в 1897 г. итальянским математиком Бурали-Форти (Burali-Forti)1. Мы не в состоянии воспроизвести этот парадокс в том виде, в каком он был впервые открыт и опубликован, так как для этого потребовалось бы ознакомить читателя с соответствующими теоретико-множественными понятиями и терминологией. Однако двумя годами позже Кантор (Cantor) обнаружил очень похожий парадокс, описание которого не требует привлечения слишком специальной терминологии. При построении теории множеств Кантору удалось доказать, что, каково бы ни было трансфинитное число2, существует большее трансфинитное число и что наибольшего трансфинитного числа не существует — точно так же, как не существует наибольшего натурального числа. Рассмотрим теперь множество, элементами которого являются все возможные множества. Очевидно, что такое множество всех множеств содержит больше элементов, чем любое другое множество. Но если это так, то как может существовать транс-

1 С. Burali-Forti. Una questione sui Humeri transfiniti.—Rendiconti del Circolo Matematico di Palermo, 11 (1897), 154—164.

2 По поводу понятия трансфинитного числа см., например, книгу: П. С. Александров, А. Н. Колмогоров. Введение в теорию множеств и теорию функций. М.-Л., Гостехиздат, 1948 (глава III).

финитное число, большее трансфинитного числа, которое соответствует этому множеству?

В то время как парадоксы Бурали-Форти и Кантора построены на результатах теории множеств, парадокс, открытый в 1902 г. Бертраном Расселом, основан на одном лишь определении множества. Прежде чем перейти к описанию парадокса Рассела, заметим, что множества либо являются элементами самих себя, либо нет. Так, множество всех абстрактных понятий само является абстрактным понятием, а множество всех людей не является человеком. Аналогично множество всех множеств само есть множество, а множество всех звезд звездой не является. Пусть M есть множество всех множеств, являющихся элементами самих себя, а IV — множество всех множеств, не являющихся элементами самих себя. Попытаемся определить, является ли N элементом самого себя. Если N является элементом себя, значит N есть элемент M, а не N. Поэтому N не является элементом самого себя. С другой стороны, если N не является элементом самого себя, тогда N есть элемент N, а не М, и N является элементом самого себя. Таким образом, налицо парадокс, так как всякий раз мы приходим к противоречию.

Парадоксу Рассела можно придать и иную, более компактную и немногословную форму. Пусть X означает любое множество, Тогда по определению N

В случае, когда х совпадает с N, мы приходим к противоречию

Об этом парадоксе Рассел сообщил Фреге, который только что перед этим закончил последний том своего громадного двухтомного трактата по основаниям арифметики. В конце второго тома Фреге в волнующих и чрезвычайно сдержанных выражениях подтверждает получение этого сообщения: «Завершив свой труд, ученый обнаруживает несостоятельность исходных позиций — вряд ли можно придумать что-нибудь более нежелательное. Именно в таком положении оказался я после получения письма от м-ра Бертрана Рассела, когда рукопись была почти готова к набору». Этими словами Фреге заключает свой двенадцатилетний труд.

Популяризация парадокса Рассела осуществлялась во многих формах. Наиболее известна форма, предложенная в 1919 г. самим Расселом: парикмахер некоторой деревни берет на себя обязательство брить всех тех и только тех жителей деревни, которые сами себя не бреют. Парадоксальность получившейся ситуации становится очевидной, стоит лишь за-

дать вопрос: «Бреет ли себя парикмахер?» Если он себя бреет, то он не должен брить себя согласно обязательству, если же он m бреет себя, то он должен брить себя согласно обязательству.

Со времени открытия указанных противоречий в канторовской теории множеств было найдено также много других парадоксов. Современные теоретико-множественные парадоксы родственны некоторым древним логическим парадоксам. Например, Евбулиду, жившему в IV в. до н. э., приписывают следующее замечание: «Утверждение, высказываемое мною, ложно». Если это утверждение истинно, то согласно смыслу этого утверждения оно ложно. С другой стороны, если оно ложно, то оно оказывается истинным. Таким образом, любое из двух предположений приводит нас к противоречию. Повидимому, еще более ранним является неаутентичный парадокс Эпименида. Этому критскому философу VI в. до н. э. приписывают высказывание: «Все критяне лжецы». Нетрудно видеть, что высказывание это внутренне противоречиво.

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

Поскольку дело касается математики, выход из положения кажется простым. Необходимо лишь перестроить теорию множеств, выбрав такую аксиоматику, при которой известные в настоящее время антиномии не могли бы уже возникнуть. Впервые соответствующая система аксиом была предложена Цермело (Zermelo) в 1908 г., дальнейшие усовершенствования были сделаны Френкелем (Fraenkel, 1922, 1925), Сколемом (Skolem, 1922, 1929), фон Нейманом (1925, 1928), Бернайсом (1937—1948) и другими. Указанный метод решения проблемы не является, однако, вполне удовлетворительным: устраняя известные противоречия, он вместе с тем не дает никаких средств к объяснению парадоксов. Более того, от возникновения в будущем других парадоксов мы также не гарантированы.

Существует другой подход, позволяющий одновременно и устранить известные нам парадкосы и объяснить их. Если внимательно проанализировать приведенные выше парадоксы, то легко обнаружить, что в каждом из них фигурирует множество S и элемент m из S, определение которого зависит от S. Определения такого рода называются импредикативными; импредикативные определения являются в известном смысле круговыми. Рассмотрим для примера парадокс Рассела с парикмахером. Обозначим парикмахера через m, а множество всех жителей его деревни — через S. Тогда m оп-

ределяется импредикативно как «такси, представитель S, который бреет всех тех и только тех представителей S, которые сами себя не бреют». Круговой характер этого определения очевиден — в определении парикмахера фигурируют жители деревни, а сам парикмахер также является жителем деревни.

Пуанкаре считал, что антиномии являются следствием импредикативных определений; ту же точку зрения выражает Рассел в своем «Принципе порочного круга»: никакое множество S не может содержать элементов m, определяемых лишь в терминах множества S, а также элементов m, предполагающих в своем определении это множество. Этот принцип суживает понятие множества. Кантор пытался представить понятие множества как значительно более общее: под множеством S мы понимаем любую совокупность, объединяющую в одно целое некоторые определенные различаемые объекты m нашей мысли или интуиции; эти объекты m называются элементами S. Теория множеств, имеющая в основе канторовскую идею множества, приводит, как мы знаем, к противоречиям; ограничение, высказанное в «Принципе порочного круга», позволяет устранить все известные антиномии. Таким образом, в отношении известных парадоксов решение достигается исключением импредикативных определений. Существует, однако, одно серьезное возражение против такого решения — дело в том, что импредикативные определения используются в таких частях математики, отказаться от которых было бы чрезвычайно трудно.

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

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

1 Н. Weyl. Das Kontinuum: Kritische Untersuchungen über die Grundlagen der Analysis, Leipzig. Gruyer, 1918.

раниченной теория множеств заставило призвести всесторонний анализ основ логики. Чрезвычайно интригующим является предположение о том, что трудности, связанные с парадоксами, могут быть преодолены с помощью трехзначной логики. Так, например, когда мы рассматривали парадокс Рассела, мы убедились, что утверждение «N есть элемент самого себя» не может быть ни истинным, ни ложным. На помощь нам приходит третья возможность, и нетрудно спасти положение, приписав утверждению значение истинности «?».

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

5. ФИЛОСОФИЯ МАТЕМАТИКИ

Можно считать, что философия объясняет нам наши знания, пытаясь отыскать некоторый смысл в естественном беспорядке этих знаний. С этой точки зрения можно говорить о философии чего угодно — о философии искусства, жизни, религии, образования, общества, истории, науки, математики и даже самой философии. Философия представляет собой процесс отшлифовывания и упорядочения наших знании и наших оценок; она отыскивает связи между явлениями, которые обычно кажутся совершенно не связанными, и обнаруживает существенные различия в таких вещах, которые в обыденной жизни мы принимаем за одно и то же; философия есть теория, исследующая природу какой-либо области знания. В частности, основная задача философии математики заключается в упорядочении или переосмыслении всей той хаотической массы математических знаний, которая накоплена в течение столетий. Ясно, что философия меняется с течением времени, и вновь приобретенные знания могут либо изменить всякую в отдельности взятую философию, либо сделать ее устаревшей. В этом разделе мы будем интересоваться лишь современной философией математики, которая сформировалась под влиянием текущего кризиса основ и последних достижений математической науки.

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

Ниже мы попытаемся охарактеризовать каждую из трех основных философских школ. Разумеется, ни объем настоящей брошюры, ни самые ее цели не позволяют осветить пред-

мет с надлежащей всесторонностью; мы надеемся, однако, что сумеем дать некоторое представление о современных философских школах, исследующих основания и основные понятия математики.

(1) Логицизм. Согласно основному тезису логистов математика является частью логики. Из инструмента математики логика превращается в первооснову всей математической пауки. Понятия математики должны быть выражены в терминах понятий логики, а теоремы математики должны быть выведены из теоремы логики, и лишь с точки зрения чисто практических удобств имеет смысл отличать математику от логики.

Уже Лейбниц (1666 г.) трактовал логику как науку, которая заключает в себе основные принципы и идеи, лежащие в основе всех прочих наук. Дедекинду (1888 г.) и Фреге (1884—1903 гг.) впервые удалось выразить понятия математики с помощью понятий логики, а Пеано (1889—1908 гг.) обнаруживает, что символический язык логики чрезвычайно удобен для формулировки математических теорем. Названные ученые были прямыми предшественниками логистов, однако по-настоящему логицизм начинается с появлением монументальных «Принципов математики» Уайтхэда и Рассела (1910—1913 гг.) В этой большой и сложной работе авторы пытаются последовательно и строго свести всю математическую пауку к логике. Идеи Уайтхэда и Рассела получили свое дальнейшее развитие в работах Витгенштейна (Wittgenstein, 1922), Хвистека (Chwistek, 1924, 1925), Рамсея (Ramsey, 1926), Лангфорда (Langford, 1927), Карнапа (Carnap, 1931), Куайна (Quine, 1940) и других.

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

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

качестве неких правдоподобных описаний и гипотез, подсказанных нам опытом. Короче говоря, мы переходим здесь от абстрактного к конкретному и в связи с этим не пытаемся доказывать непротиворечивость первоначальных высказываний. Целью авторов было построение математических понятий и теорем на базе первоначальных идей и высказываний; при этом имелось в виду начать с исчисления высказываний, перейти далее к исчислению классов и отношений и перестроить систему натуральных чисел, а вместе с ней и все то, что может быть из нее выведено. Построенная в «Принципах математики» система натуральных чисел обладает в точности теми свойствами, которые мы ей обычно приписываем, а сами натуральные числа вполне однозначно определяются при этом как любые предметы, удовлетворяющие определенной системе аксиом.

Для преодоления противоречий теории множеств в «Принципах математики» строится так называемая «теория типов». Теория эта, грубо говоря, устанавливает определенную иерархию элементов. Некоторым первичным элементам приписывается тип 0, множества элементов типа 0 является элементами типа 1, множества элементов типа 1 являются элементами типа 2 и т. д. Правомерным считается рассматривать лишь такие множества, все элементы которых принадлежат одному типу. Следование этому правилу исключает возможность импредикативных определений и тем самым позволяет избежать противоречий. Поскольку в «Принципах математики» речь шла также об иерархиях внутри иерархий, оказалось необходимым разработать так называемую «разветвленную» теорию типов.

Не имея возможности построить анализ, не пользуясь импредикативными определениями, авторы вынуждены были ввести специальную аксиому — «аксиому сводимости». Однако произвольный и непримитивный характер этой аксиомы вызвал серьезную критику оппонентов; в дальнейшем логисты сосредоточили свои усилия в основном на построении такого аппарата, который сделал бы ненужным пользование аксиомой сводимости.

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

(2) Интуиционизм. Согласно тезису интуиционистов математика должна быть построена с помощью одних лишь финитных конструктивных средств на основе системы натураль-

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

Интуиционистская школа была основана в 1908 г. голландским математиком Л. Е. Дж. Брауером (Brauwer), впрочем основные идеи интуиционистов выдвигались и ранее, например Кронекером (в 80-х годах прошлого века) и Пуанкаре (в 1902—1906 гг.). С течением времени интуиционистская школа окрепла и разрослась, к ней примкнули многие выдающиеся современные математики, и следует признать, что интуиционизм оказал громадное влияние на весь строй мысли, связанный с вопросами оснований математики.

В некоторых своих частях интуиционизм является почтя революционным. Так, интуиционистские требования в отношении конструктивного построения объектов приводят к определенному пониманию существования математических объектов — пониманию, которое не разделяется большинством действующих математиков. Для интуициониста доказательство существования объекта заключается в конструктивном построении объекта в конечное число шагов; если же из факта несуществования объекта следует противоречие, то это с интуиционистской точки зрения не считается еще достаточным доказательством. А отсюда следует, что неприемлемыми оказываются многие доказательства современной математики.

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

Замечательно также и то, что требование конструктивных доказательств приводит к отказу от общепринятого закона исключенного третьего! Пусть, например, число х определено

следующим образом: если 1 есть k-я десятичная цифра в десятичной записи числа я и вслед за нею идут цифры 2 3 4 5 6 7 8 9 в этой именно их последовательности, причем левее k-го знака такой последовательности цифр нет, то х = (—1)k в противном случае х = 0. И хотя число х определено теперь вполне корректно, интуиционистские ограничения не позволяют нам утверждать, что высказывание «х = 0» является либо истинным, либо ложным. Про это высказывание можно сказать, что оно истинно лишь после того, как будет указано соответствующее доказательство, состоящее из конечного числа шагов. Аналогичным образом исчерпывается вопрос о ложности данного высказывания. Пока же никакое из двух доказательств не указано, высказывание не является ни истинным, ни ложным и закон исключенного третьего оказывается неприменимым. Однако если наложить дополнительное ограничение, потребовав, скажем, чтобы k было меньше 5000, то тогда уже с полным правом можно утверждать, что наше высказывание либо истинно, либо ложно, поскольку при k<5000 истинность или ложность высказывания может быть установлена в конечное число шагов.

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

В «Принципах математики» закон исключенного третьего равносилен закону противоречия. У интуиционистов дело обстоит не так — в связи с этим представлялось интересным построить логику, основанную на интуиционистских идеях. Эта задача была выполнена Гейтингом, который в 1930 г. завершает построение интуиционистской символической логики. Таким образом, интуиционистская математика привела к созданию логики нового типа, и можно поэтому говорить о том, что сама математическая логика является разделом математики.

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

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

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

Формалистская школа была основана Давидом Гильбертом в связи с завершением последним аксиоматического изучения геометрии. В своих «Основаниях геометрии» Гильберт переходит от материальной аксиоматики Эвклида к современной формальной аксиоматике. Формалистские идеи, развитые позднее Гильбертом, были выдвинуты им в качестве средства преодоления кризиса основ, вызванного теоретико-множественными парадоксами, и в ответ на выступление интуиционистов, бросивших вызов классической математике. Формалистская концепция возникла у Гильберта еще к 1904 г., но лишь начиная с 1920 г. Гильберт и его сотрудники Бернайс, Аккерман (Ackermann) и фон Нейман приступают к серьезной разработке формалистской программы.

Спасение классической математики на пути, указанном Гильбертом, зависит от решения проблемы непротиворечиво-

* С интуиционистской школой читатель может познакомиться по книге: А. Гейтинг. Интуиционизм. М., «Мир», 1965. На русском языке существует также сборник статей одного из основоположников этого направления—Г. Вейля (см. Г. Вейль. О философии математики. М.—Л., Гостехтеориздат, 1934). Следует отметить, что дальнейшее развитие интуционистских идей привело к появлению так называемой конструктивной школы в основаниях математики, имеющей горячих приверженцев и в нашей стране.

ста. Именно доказательство непротиворечивости гарантирует нас от возможности возникновения противоречий, однако до Гильберта такие доказательства базировались на отыскании содержательной интерпретации, и тем самым доказательств) непротиворечивости какой-либо области математики упиралось в доказательство непротиворечивости какой-либо другой ее области. Таким образом, доказательства методом интерпретаций имели лишь относительную ценность. Гильберт предложил новый, прямой путь. Наподобие того, как в игре правила игры позволяют доказать невозможность возникновения какой-либо игровой ситуации, точно так же соответствующим образом подобранные правила вывода формул позволяют (по Гильберту) доказать невозможность возникновения противоречивой формулы. В обозначениях логики, которые знакомы нам по предыдущим разделам этой главы, противоречивая формула записывается в виде F∧F', где F — любая формула системы. Доказательство непротиворечивости сводится к доказательству невыводимости противоречивой формулы.

Развивая свою концепцию непосредственного доказательства непротиворечивости, Гильберт приходит к теории, названной им «теорией доказательств». Гильберт и Бернайс приступают к подробному изложению этой теории и на основе ее пытаются построить доказательство непротиворечивости всей классической математики — так возникают знаменитые «Основания математики», явившиеся как бы своего рода «Принципами математики» формалистской школы. Первый том «Оснований математики» был опубликован в 1934, а второй — в 1939 г., однако по мере написания трактата возникали все новые непредвиденные трудности, и завершить теорию доказательств оказалось невозможным. Были получены доказательства непротиворечивости для некоторых простейших систем — тем самым Гильберт показал, каковы те доказательства непротиворечивости, которые он хотел бы распространить на всю математику, однако для формальной системы в целом проблема непротиворечивости оставалась нерешенной.

В действительности план Гильберта, по крайней мере в той форме, в какой первоначально представлял его себе сам Гильберт, оказался обреченным на неудачу; это обстоятельство было обнаружено Куртом Гёделем (Kurt Gödel) в 1931 г., т. е. еще до опубликования «Оснований математики». Пользуясь безукоризненно строгими методами, одинаково приемлемыми для представителей, всех основных философских направлений, Гёдель доказал, что в случае такой широкой формализованной дедуктивной системы, какой является гильбертова система, охватывающая всю классическую математику, доказательство непротиворечивости невозможно провести средствами одной лишь этой системы. Этот замечательный результат, является следствием еще более общего утверждения: Гёдель

доказал неполноту гильбертовой системы, т. е. обнаружил внутри системы ряд «неразрешимых» проблем — одной из них как раз и оказалась проблема непротиворечивости. Указанные теоремы Гёделя в техническом отношении чрезвычайно сложны, и мы не имеем возможности их здесь рассматривать. Результаты Гёделя, принадлежащие безусловно к числу наиболее выдающихся достижений современной математики, устанавливают непредвиденную ограниченность формалистских методоз. Из теорем Гёделя следует, «что финитными методами, формализованными внутри формальной системы, адэкватном в определенном смысле современной математической науке, невозможно провести доказательство непротиворечивости, а системы, позволяющие осуществить такое доказательство, не удовлетворяют свойству адэкватности»1.

1 F. De Sua. Consistency and completeness—a résumé (Ф. Де Cya, Непротиворечивость и полнота — резюме) — American Math. Monthly, 63 (1956, p. 295—305. Автор приводит также следующий любопытный пример: «Допустим, что религией в широком смысле слова мы условимся называть всякую дисциплину, основания которой базируются на вере, вне зависимости от того, чем именно эта вера вызвана. Квантовую механику, например, мы вынуждены будем считать религией. Математика также окажется религией, однако она занимала бы особое место среди прочих религий: право называться религией нуждается в обосновании, и только математика располагала бы внутренними средствами, достаточными для проведения соответствующего доказательства».

ЗАДАЧИ

1.1. С помощью таблиц истинности доказать законы логики, приведенные в таблице 7 § 1.

1.2. С помощью таблиц истинности определить, какие из приведенных ниже высказываний являются тавтологиями, а какие нет:

1.3. Пусть Р означает сложное высказывание, составленное из n элементарных высказываний. Показать, что таблица истинности для Р содержит 2n строк.

1.4. Доказать логическую эквивалентность пар высказываний, приведенных в таблице 8 § 1.

1.5. Записать следующие высказывания с помощью только дизъюнкции и отрицания:

1.6. Пусть или в разделительном смысле обозначается символом ∨, так что «p∨q» означает «p или q, но не оба». Показать, что высказывание р∨q можно записать как

1.7. С помощью таблиц истинности проверить логическую эквиваленность следующих пар высказываний:

1.8. Отрицания следующих высказываний привести к виду, в котором знак отрицания относится только непосредственно к высказываниям р, q, r:

1.9. В связи с высказыванием р → q рассматриваются следующие три высказывания: 1) q→р (обратное), 2) p'→q' (противоположное), 3) q' → р' (противоположное обратному). Показать, что

а) обратное истинному высказыванию не всегда истинно,

б) противоположное истинному высказыванию не всегда истинно,

в) противоположное обратному истинного высказывания всегда истинно,

г) высказывание, противоположное обратному, совпадает с высказыванием, обратным противоположному,

д) если высказывание и обратное ему истинны, то и противоположное также истинно,

е) если высказывание и противоположное ему истинны, то и обратное также истинно.

1.10. Написать обратное, противоположное и противоположное обратному для следующих высказываний:

1.11. В математике теоремы обычно формулируют следующим образом: 1) «для того чтобы р было истинно, необходимо, чтобы q было истинно», 2) «для того чтобы р было истинно, достаточно, чтобы q было истинно», 3) «для того, чтобы р было истинно, необходимо и достаточно, чтобы q было истинно». По определению эти три формы означают соответственна:

а) Показать, что 3 эквивалентно p←→q.

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

1.12. Если последний столбец таблицы истинности некоторого сложного высказывания состоит только из Л, то такое высказывание называется тождественно ложным. Если в последнем столбце содержится как И, так и Л, то высказывание называется выполнимым.

а) Показать, что высказывание р∧р' тождественно ложно.

б) Показать, что высказывание [(p∧q)→q]' тождественно ложно.

в) Показать, что отрицание тождественно ложного высказывания является тавтологией.

г) Показать, что высказывание р'∧q'∧r' выполнимо.

д) Показать, что высказывание р∨q∨r выполнимо.

е) Показать, что отрицание выполнимого высказывания выполнимо.

1.13. Показать, что отрицание нельзя выразить с помощью∧, ∨, →.

1.14. Пусть p/q означает p'∨q'.

а) Показать, что р/р логически эквивалентно р'.

б) Показать, что (p/p)/(q/q) логически эквивалентно p∨q.

в) Выразить V с помощью только /.

г) Выразить с помощью только /.

д) Выразить ←→ с помощью только /.

2.1. Установить следующие вспомогательные полезные правила получения тавтологий из данных тавтологий в исчислении высказываний.

а) П5: Если m∨m — тавтология, то m — тавтология.

б) П6: Если m — тавтология, ар — любое высказывание, то p∨m— тавтология.

в) П7: Если m∨n— тавтология, то n∨m — тавтология.

г) П8: Если m→п — тавтология, а р — любое высказывание, то (p∨m)→(p∨n) — тавтология.

д) П9: Если p→q, q→r— тавтология, то р→r — тавтология.

2.2. (а) Показать, пользуясь таблицей истинности для импликации, что «если р и р→q истинны, то q истинно».

б) В силу (а) аксиома L1 утверждает, что «если р или р истинно, то р истинно». Дать аналогичную интерпретацию аксиом L2, L3, L4 и теорем 1, 2 и 3.

2.3 Показать, что если по определению р означает q, то p→q — тавтология.

2.4. Можно доказать следующее правило П10: Если p←→q — тавтология, то при замене в произвольной тавтологии любого вхождения р на q мы снова получим тавтологию. Пользуясь этим правилом, доказать

а) Теорему 15.

б) Теорему 23.

2.5. (а) Показать, что высказывание (p→q')→(q→p') является тавтологией.

б) Доказать теорему 16.

в) Если m←→n — тавтология, то m'←→n— тавтология.

2.6. (а) Доказать теорему 21.

б) Показать, что высказывание р → (p∨q)— тавтология,

в) Доказать теорему 22.

2.7. Проверить, что аксиомы булевой алгебры переходят в тавтологии при интерпретации, приведенной в конце § 2.

2.8. В какие тавтологии переходят следующие соотношения булевой алгебры:

2.9. (а) Что соответствует импликации а→b в булевой алгебре?

б) Что соответствует отношению включения aczb в исчислении высказываний?

2.10. Получить новые тавтологии из данных по принципу двойственности:

3.1. Построить таблицы истинности для дизъюнкции в трехзначной логике, выражая p∨q как (p'∧q')' и используя:

а) Таблицы 11 и 13;

б) Таблицы 11 и 14;

в) Таблицы 12 и 13;

г) Таблицы 12 и 14.

3.2. Построить таблицы истинности для импликации в трехзначной логике, выражая p→q как (p∧q')' и используя:

а) Таблицы 11 и 13;

б) Таблицы 11 и 14;

в) Таблицы 12 и 13;

г) Таблицы 12 и 14.

3.3. Проверить, что для отрицания можно построить в точности 12 различных таблиц истинности в трехзначной логике.

3.4 (а) Показать, что для таблицы истинности 13 [(р')']' принимает всегда то же значение, что и р.

б) Показать, что для таблицы истинности 14 (р')' принимает всегда то же значение, что и р.

3.5. Аналогично тому, как было подсчитано в § 3 общее число всевозможных различных трехзначных логик (3072), подсчитать общее число всевозможных различных m-значных логик.

3.6. Предположим, что при определении импликации р→q требуется, чтобы из одновременной истинности р и р→q вытекала истинность q. Сколько тогда имеется способов определения импликации (а) в двузначной логике? (в) в трехзначной логике?

4.1. Рассмотреть парадокс Рассела в следующих его популярных формах:

а) Каждый муниципалитет некоторого государства имеет своего мэра, и у разных муниципалитетов разные мэры. Некоторые мэры не проживают в своих муниципалитетах. Выпущен закон, по которому все такие мэры обязаны проживать в некотором специальном районе A, и никто другой не должен там проживать. В А оказалось так много мэров, что А был провозглашен муниципалитетом. Где должен проживать мэр муниципалитета А?

б) Прилагательные русского языка подразделяются на самоприменимые, т. е. применимые к самим себе, и на несамоприменимые, т. е. все прочие. Так, прилагательные «русский», «многосложный» являются самоприменимыми, а прилагательные «французский», «односложный» являются несамоприменимыми. Спрашивается, в какой из двух классов попадает прилагательное «несамоприменимый»?

в) Может ли библиотекарь составить для своей библиотеки библиографию в точности тех библиографий библиотеки, которые не перечисляют самих себя?

4.2. Рассмотреть следующий парадокс: Каждое натуральное число можно выразить в обычном русском языке без помощи нумерических символов. Так, для выражения числа 5 можно использовать такие словосочетания, как «пять», «половина десяти», «второе по порядку нечетное простое число», «арифметический квадратный корень из двадцати пяти» л так далее. Введем теперь словосочетание «наименьшее натуральное число, которое не может быть выражено менее чем тринадцатью словами». Это словосочетание из двенадцати слов выражает натуральное число, которое не может быть выражено менее чем тринадцатью словами.

4.3. Рассмотреть следующие логические дилеммы:

а) Крокодил обещает вернуть похищенного им ребенка отцу, если тот угадает, вернет крокодил ребенка или нет? Что делать крокодилу, если отец заявит, что крокодил не вернет ребенка?

б) Путешественник был схвачен людоедами, которые предоставили ему возможность произнести какое-нибудь высказывание, с условием, что если это высказывание окажется истинным, то его сварят, а если — ложным, то зажарят. Что делать людоедам, если путешественник заявит «Вы меня зажарите»?

4.4. Показать, что утверждение «Каждое общее правило имеет исключения» внутренне противоречиво.

4.5. Рассмотреть такие вопросы:

а) Сокрушит ли всесокрушающая сила несокрушимое препятствие?

б) Если Зевс всемогущ, то может ли он сотворить камень, который он не в состоянии поднять?

9 коп.

Индекс 70096

ТЕМ, КОГО ИНТЕРЕСУЕТ ФИЗИКА И АСТРОНОМИЯ

ИЗДАТЕЛЬСТВО «ЗНАНИЕ» ПРЕДЛАГАЕТ СЕРИЮ НАУЧНО ПОПУЛЯРНЫХ БРОШЮР «ФИЗИКА, АСТРОНОМИЯ»

Эти книжки в популярной форме познакомят вас с новейшими успехами ядерной физики, достижениями в области физики твердого тела, астрофизики, космологии.

ГИНЗБУРГ В. Л., акад. КАК УСТРОЕНА ВСЕЛЕННАЯ И КАК ОНА ИЗМЕНЯЕТСЯ ВО ВРЕМЕНИ.

СЕДОВ Л. И., акад. НАУКА, КОСМОНАВТИКА И ОБЩЕСТВО.

ЩЕЛКИН К. И., член-корр. АН СССР. ДЕТОНАЦИЯ.

ФРИШ С. Э., член-корр. АН СССР. СОВРЕМЕННАЯ ОПТИКА.

ГУРЕВИЧ Л. Э., профессор. ТЕОРИЯ ОТНОСИТЕЛЬНОСТИ В КАРТИНЕ МИРА.

Вот те работы, которые получат подписчики серии «Физика, астрономия» во втором полугодии 1968 года.

Всего в год выходит 12 брошюр.

Подписка на эту серию производится как на газеты или журналы в любом отделении «Союзпечати».

В каталоге вы найдете серию «Физика, астрономия» в разделе «Научно-популярные журналы» под рубрикой «Брошюры издательства «Знание».

Стоимость подписки на квартал-27 коп.

ПОДПИСЫВАЙТЕСЬ НА СЕРИЮ «ФИЗИКА, АСТРОНОМИЯ»!

ИЗДАТЕЛЬСТВО «ЗНАНИЕ»