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

Исторический очерк

Идея построения универсального языка для всей математики и формализации на базе такого языка математических доказательств выдвигалась в 17 в. Г. В. Лейбницем. В середине 19 в. появились первые работы по алгебраизации аристотелевой логики (Дж. Буль, 1847, и О. де Морган, 1858). После того как Г. Фреге (1879) и Ч. Пирс (1885) ввели в язык алгебры логики предикаты, предметные переменные и кванторы, возникла реальная возможность применить этот язык к вопросам, связанным с основаниями математики.

Создание неевклидовых геометрий сильно поколебало уверенность математиков в абсолютной надёжности геометрических построений, на которых была основана евклидова геометрия. Помимо этого, в результате развития исчисления бесконечно малых были обнаружены неожиданные примеры всюду непрерывных, но не дифференцируемых функций. Появилась потребность отделить понятие действительного числа от неясного понятия «величины», которое было основано на геометрических представлениях. Эта задача была решена (с помощью различных подходов) в работах К. Вейерштрасса, Р. Дедекинда и Г. Кантора. Они показали возможность «арифметизации» анализа и теории функций, в результате чего в качестве фундамента всей классической математики стала рассматриваться арифметика целых чисел. Затем была предпринята аксиоматизация арифметики (Р. Дедекинд, 1888, Дж. Пеано, 1891). При этом Пеано создал удобную символику для логического языка. Позднее этот язык был усовершенствован в работе Б. Рассела и А. Уайтхеда «Основания математики» (т. 1–3, 1910–1913), где была предпринята попытка сведения всей математики к логике. Эта попытка не увенчалась успехом, т. к. оказалось невозможным вывести из чисто логических аксиом существование бесконечных множеств. Хотя логическая программа Фреге – Рассела в основаниях математики не достигла своей главной цели – сведения математики к логике, в их работах был создан богатый логический аппарат, без которого становление математической логики как полноценной математической дисциплины было бы невозможно.

На рубеже 19–20 вв. были обнаружены антиномии, связанные с основными понятиями теории множеств. Наиболее сильное впечатление на современников произвела антиномия Рассела (1901), которая состоит в следующем. Пусть $M$ есть множество всех таких множеств, каждое из которых не является своим собственным элементом. Можно убедиться, что множество $M$ является своим элементом тогда и только тогда, когда $M$ не является своим элементом. Выйти из создавшегося противоречия можно попытаться, сделав заключение, что такого множества $M$ не существует. Однако если не может существовать множество, состоящее в точности из всех элементов, удовлетворяющих чётко определённому условию, приведённому выше в определении множества $M$, то нет гарантий того, что не придётся столкнуться с множествами, которые также не существуют. Возникает вопрос, каким должно быть определение множества для того, чтобы это множество существовало? Парадокс Рассела показал, что нужно как-то ограничить канторовскую теорию множеств.

Л. Брауэр выступил (1908) против применения правил классической логики к бесконечным множествам. В выдвинутой им интуиционистской программе предлагалось отказаться от рассмотрения абстракции актуальной бесконечности, т. е. рассмотрения бесконечных множеств как завершённых совокупностей. Допуская существование сколь угодно больших натуральных чисел, интуиционисты выступают против рассмотрения натурального ряда как завершённого множества. Они считают, что в математике всякое доказательство существования того или иного объекта должно быть конструктивным, т. е. должно сопровождаться построением этого объекта. Если предположение о том, что искомый объект не существует, привело к противоречию, то это, по мнению интуиционистов, не может рассматриваться как доказательство его существования. Особой критике со стороны интуиционистов подвергается т. н. закон исключённого третьего. Ввиду того что этот закон первоначально рассматривался применительно к конечным множествам, а многие свойства конечных множеств несправедливы для бесконечных множеств (например, что всякая собственная часть меньше целого), интуиционисты считают неправомерным применение этого закона к бесконечным множествам. Так, например, чтобы утверждать, что Великая теорема Ферма справедлива или нет, интуиционист должен указать соответствующее доказательство, т. е. пока теорема Ферма не доказана, не допускается утверждать, что эта теорема либо верна, либо нет. Такое требование интуиционистов может создать затруднение и для задач, связанных с конечными множествами. Пусть из урны, содержащей три чёрных и три белых шара, некто, закрыв глаза, достаёт один шар и тут же кладёт его обратно. Если никто не видел этот шар, то мы не имеем возможности узнать, какого он был цвета. Однако вряд ли можно всерьёз оспаривать достоверность утверждения, что этот шар был либо чёрного, либо белого цвета.

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

Д. Гильберт наметил другой путь преодоления трудностей, возникших в основаниях математики на рубеже 19–20 вв. Этот путь, базировавшийся на применении аксиоматического метода рассмотрения формальных моделей содержательной математики и на исследовании вопросов непротиворечивости таких моделей надёжными финитными (конечными) средствами, получил в математике название финитизма Гильберта. Признавая ненадёжность геометрической интуиции, Гильберт прежде всего тщательно переработал евклидову геометрию, освобождая её от обращения к интуиции. Результатом такой переработки явились его «Основания геометрии» (1899).

Вопросы непротиворечивости различных теорий по существу рассматривались и до Д. Гильберта. Так, построенная Ф. Клейном (1871) проективная модель геометрии Лобачевского сводит вопрос о непротиворечивости геометрии Лобачевского к непротиворечивости евклидовой геометрии. Аналогично непротиворечивость евклидовой геометрии можно свести к непротиворечивости математического анализа, т. е. к непротиворечивости теории действительных чисел. Однако вопрос о том, какими средствами можно строить модели анализа и арифметики для доказательства их непротиворечивости, оставался открытым. Заслуга Д. Гильберта состоит в том, что он указал прямой путь для исследования этого вопроса. Непротиворечивость данной теории означает, что в ней не может быть получено противоречие, т. е. не может быть доказано некоторое утверждение $A$ и его отрицание $¬A$. Гильберт предложил представлять рассматриваемую теорию в виде формальной аксиоматической системы, в которой будут выводимы все те и только те утверждения, которые являются теоремами этой теории. Тогда для доказательства непротиворечивости достаточно установить невыводимость в рассматриваемой теории некоторых определённых утверждений. Т. о., математическая теория, непротиворечивость которой мы хотим доказать, становится предметом изучения математической науки, которую Гильберт назвал метаматематикой (см. Метатеория), или теорией доказательств.

Д. Гильберт считал, что парадоксы теории множеств вызваны не законом исключённого третьего, а «скорее тем, что математики пользуются недопустимыми и бессмысленными образованиями понятий, которые в моей теории доказательств исключаются сами собой… Отнять у математиков закон исключённого третьего – это то же, что забрать у астрономов телескоп или запретить боксёрам использовать кулаки». Гильберт предлагал различать «действительные» и «идеальные» предложения классической математики. Первые имеют содержательный смысл, а вторые не обязаны его иметь. Предложения, соответствующие употреблению актуальной бесконечности, идеальны. Идеальные предложения присоединяются к действительным для того, чтобы простые правила логики были применимы и к рассуждениям о бесконечных множествах. Это существенно упрощает структуру всей теории, подобно тому как при рассмотрении проективной геометрии на плоскости добавляется бесконечно удалённая прямая, пересекающая любые две параллельные прямые в некоторой точке.

Выдвинутая Д. Гильбертом программа обоснования математики вдохновила современников на разработку аксиоматического метода. Именно с предпринятой в начале 20 в. Гильбертом и его последователями разработкой теории доказательств на базе развитого в работах Г. Фреге, Дж. Пеано и Б. Рассела логического языка связывают становление математической логики как самостоятельной математической дисциплины.

Первыми работами по математической логике в России были работы П. С. Порецкого (1884–1904). Вопросам оснований математики и математической логики большое внимание уделяли Н. Н. Лузин и его ученики А. Н. Колмогоров и П. С. Новиков. Колмогоров сформулировал (1925) аксиомы для логики высказываний, приемлемые с точки зрения философии интуиционизма Л. Брауэра, и предложил (1932) естественную интерпретацию интуиционистской логики Брауэра как логики задач. А. И. Мальцев доказал (1936) теорему о компактности, состоящую в том, что произвольная система формул в языке логики предикатов непротиворечива, если непротиворечиво любое её конечное подмножество. Этот результат стал средством доказательства локальных теорем для различных алгебраических систем. Новиков разработал (1941) метод доказательства непротиворечивости классических формальных систем, основанный на введённом им понятии регулярной формулы и сводящий этот вопрос к вопросу о непротиворечивости интуиционистской математики. Продолжая исследования К. Гёделя о непротиворечивости континуум-гипотезы, Новиков установил (1951) непротиворечивость ряда других важных предложений теории множеств, доказательства которых представляли большие трудности.

Появление в математической логике точного определения понятия алгоритма позволило устанавливать разрешимость и неразрешимость алгоритмических проблем в математике. Первые результаты в этом направлении были получены в теории алгоритмов и в математической логике (например, результаты, связанные с проблемой остановки работы машины Тьюринга и теоремой Чёрча о неразрешимости логики предикатов). В связи с этими результатами возник вопрос: не являются ли неразрешимые алгоритмические проблемы специфическими для теории алгоритмов и математической логики? Оказалось, что это не так, и существенный вклад в исследование разрешимости алгоритмических проблем традиционной математики внесли российские учёные. А. А. Марков и американский математик Э. Пост независимо и одновременно (1947) доказали, что не существует алгоритма распознавания проблемы равенства слов в полугруппах, задаваемых конечным числом определяющих соотношений. Эта проблема возникла задолго до уточнения понятия алгоритма. П. С. Новиков доказал (1955) неразрешимость проблемы тождества слов для конечно определённых групп. На основе этого результата С. И. Адян доказал (1955) алгоритмическую неразрешимость частной проблемы изоморфизма для любой фиксированной группы, а также алгоритмическую нераспознаваемость почти всех инвариантных групповых свойств (например, единичности, конечности, коммутативности). Марков, используя результат Адяна, доказал (1958) алгоритмическую неразрешимость важной алгоритмической проблемы в топологии – проблемы распознавания гомеоморфизма многообразий размерности, большей трёх. Ю. В. Матиясевич доказал (1970) алгоритмическую нераспознаваемость существования решений у диофантовых уравнений, решив тем самым (отрицательно) 10-ю проблему Гильберта. Эта работа Матиясевича явилась завершением работ, проводившихся группой американских учёных в начале 1960-х гг. (Б. Дэвис, Дж. Робинсон, Р. Робинсон, Х. Путнем).

В 1957 г. по рекомендации 3-го Всесоюзного съезда математиков в Математическом институте имени В. А. Стеклова АН СССР был образован отдел математической логики, который возглавил П. С. Новиков; в 1959 г. на механико-математическом факультете МГУ образована кафедра математической логики, которую возглавил А. А. Марков, создатель теории алгорифмов и основатель школы конструктивной математики в России. Представителями школы Маркова получены результаты по конструктивной логике и математике, сложности алгоритмов, поиску логического вывода, логике доказуемости, модальным логикам. А. Н. Колмогоров заложил (1968) основы алгоритмической теории информации, предложив понятие сложности описания конечного объекта (сложность по Колмогорову). В отделе математической логики Математического института велись исследования по теории доказательств, алгоритмическим проблемам алгебры и логики и теории сложности вычислений. В частности, была доказана распознаваемость существования решений уравнений в свободных полугруппах и в свободных группах (Г. С. Маканин, 1977, 1982), доказана разрешимость универсальной и позитивной теорий свободной группы (Маканин, 1984). Были получены сверхполиномиальные нижние оценки сложности реализации монотонных булевых функций схемами в базисе без отрицания (А. А. Разборов, 1985) и полная классификация пропозициональных логик доказуемости (Л. Д. Беклемишев, 1989). Большую известность в математической логике и алгебре приобрела проблема Бёрнсайда о периодических группах (сформулирована в 1902), в которой ставился вопрос о том, будет ли любая конечно порождённая группа, для элементов которой справедливо тождество $x^n=1$, конечной. В серии совместных работ П. С. Новиков и С. И. Адян доказали (1968, 1975), что нециклическая группа $B(m,n)$, заданная $m$ порождающими и тождественным соотношением $x^n= 1$, бесконечна при показателях $n$, кратных любому нечётному $k>665$. Эти исследования были продолжены Адяном (1975). С. В. Иванов и И. Г. Лысёнок доказали, что нециклические группы $B(m,n)$ бесконечны при всех $n$, начиная с 2⁴⁸ (Иванов, 1994), 8000 (Лысёнок, 1996).

А. И. Мальцевым была основана сибирская школа алгебры и логики (1960). Он и его ученики внесли существенный вклад в изучение неклассических логик и проблем разрешимости элементарных теорий различных алгебраических систем. Ю. Л. Ершов доказал (1965, одновременно с американскими учёными Дж. Аксом и С. Коченом) разрешимость элементарной теории поля $p$-адических чисел. Им также получены результаты по теории нумераций, теории конструктивных моделей и теоретико-рекурсивным иерархиям. Его учеником С. С. Гончаровым развита теория т. н. алгоритмической размерности, он внёс вклад в изучение конструктивных моделей, в особенности конструктивных булевых алгебр.

Предмет и основные разделы математической логики, связь с другими областями математики

К математической логике относятся исследования логических и логико-математических исчислений, из которых основным является классическое исчисление предикатов. В 1930 г. К. Гёдель доказал теорему о полноте исчисления предикатов, согласно которой множество всех чисто логических утверждений математики совпадает с множеством всех формул, выводимых в исчислении предикатов. Эта теорема показала, что исчисление предикатов является той логической системой, на базе которой можно формализовать математику. На базе исчисления предикатов строятся различные логико-математические теории, представляющие собой формализацию содержательных математических теорий – арифметики, математического анализа, теории множеств, теории групп и прочего. Наряду с элементарными теориями рассматриваются также теории высших порядков, в которых допускаются также кванторы по предикатам, предикаты от предикатов и т. д. Традиционными вопросами, которые исследуются для тех или иных формальных логических систем, являются исследования структуры выводов в этих системах, выводимость тех или иных формул, вопросы непротиворечивости и полноты рассматриваемых систем.

Доказанная в 1931 г. теорема Гёделя о неполноте арифметики поколебала оптимистические надежды Д. Гильберта на полное решение вопросов оснований математики на указанном им пути. Эта теорема утверждает, что в любой теории, содержащей элементарную арифметику (с операциями сложения и умножения), можно сформулировать такое утверждение, что ни оно само, ни его отрицание не доказуемо. В частности, таковым является утверждение о непротиворечивости самой рассматриваемой теории. Это означает, что с вопросами оснований математики дело обстоит не так просто, как хотелось или казалось Гильберту вначале. Однако Гёдель заметил, что непротиворечивость арифметики можно доказывать, пользуясь достаточно надёжными конструктивными средствами, хотя и выходящими за рамки средств, формализуемых в арифметике. Аналогичные доказательства непротиворечивости арифметики были получены немецким математиком Г. Генценом (1936) и П. С. Новиковым (1942).

В результате анализа канторовской теории множеств и связанных с ней парадоксов были построены различные системы аксиоматической теории множеств, в которых принимается то или иное ограничение на образование множеств, чтобы исключить возникновение известных антиномий. В этих аксиоматических системах могут быть развиты довольно обширные разделы математики. Вопрос о непротиворечивости достаточно богатых аксиоматических систем теории множеств остаётся открытым. Среди наиболее значительных результатов, полученных в аксиоматической теории множеств, – результат К. Гёделя (1939) о непротиворечивости континуум-гипотезы и аксиомы выбора в системе Бернайса – Гёделя $Σ$ и результат П. Коэна (1963) о независимости этих аксиом от аксиом системы Цермело – Френкеля $ZF$. Системы аксиом $Σ$ и $ZF$ равнонепротиворечивы. Для доказательства своих результатов Гёдель ввёл понятие конструктивного множества и показал существование модели системы $Σ$, состоящей из таких множеств. Метод Гёделя был использован П. С. Новиковым для доказательства непротиворечивости некоторых утверждений дескриптивной теории множеств (1951). Для построения моделей теории множеств $ZF$, в которых выполняются отрицания континуум-гипотезы или аксиомы выбора, Коэн ввёл т. н. метод вынуждения, который впоследствии был усовершенствован и стал основным методом построения моделей теории множеств, удовлетворяющих тем или иным свойствам.

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

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

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

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

Важное место в теории моделей занимает исследование т. н. нестандартных моделей арифметики и математического анализа. В начале развития дифференциального исчисления в работах Г. В. Лейбница и И. Ньютона бесконечно малые и бесконечно большие величины рассматривались как числа. Позднее появилось понятие переменной величины, и в математике отказались от употребления бесконечно малых чисел, модуль которых отличен от нуля и меньше любого положительного действительного числа, т. к. их употребление требует отказа от аксиомы Архимеда. Через три столетия в результате развития методов математической логики удалось установить, что нестандартный анализ с бесконечно малыми и бесконечно большими числами непротиворечив относительно обычного (стандартного) анализа.

Аксиоматический метод оказал влияние и на интуиционистскую математику. Нидерландский учёный А. Гейтинг в 1930 г. ввёл в рассмотрение формальные системы интуиционистской логики высказываний и предикатов (конструктивные исчисления высказываний и предикатов). Позднее были введены формальные системы интуиционистского анализа. Было введено понятие т. н. реализуемости формул по Клини, связанное с одной из попыток интерпретировать понятие интуиционистской истинности с точки зрения классической математики. Однако оказалось, что не всякая реализуемая формула исчисления высказываний выводима в интуиционистском (конструктивном) исчислении высказываний.

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

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