Свойства аксиоматических теорий

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

Непротиворечивость аксиоматических теорий

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

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

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

Доказательство. В самом деле, ввиду противоречивости теории существует предложение теории, такое, что и — ее теоремы. Рассмотрим следующую последовательность высказываний данной теории:

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

Ясно, что обратное утверждение также справедливо: если любое предложение аксиоматической теории является ее теоремой, то теория противоречива.

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

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

Во многих случаях этот вопрос удается решить с помощью понятия модели. Развивая аксиоматическую теорию на базе той или иной системы аксиом , мы не вкладываем в ее основные понятия и отношения между ними никакого содержания сверх того, что сказано о них в аксиомах; в них содержатся все сведения об этих понятиях, необходимые для построения теории путем чисто логических умозаключений. Изменим теперь нашу точку зрения на первоначальные понятия: будем понимать под ними некоторые вполне определенные объекты и соотношения между ними из какой-нибудь области математики (другой аксиоматической теории), которую мы считаем уже установленной и обоснованной (непротиворечивой). Это придание каждому первоначальному понятию и отношениям между ними конкретного содержания посредством каких-то конкретных предметов и конкретных отношений между ними, как мы говорили в предыдущем параграфе, называется интерпретированием данной системы аксиом . Совокупность этих конкретных предметов и отношений между ними называется интерпретацией данной системы аксиом. В результате каждая аксиома из превращается во вполне определенное предложение из той уже обоснованной области математики (непротиворечивой аксиоматической теории), которая используется для интерпретации. Каждое из этих предложений может быть как истинным (теоремой), так и ложным в непротиворечивой аксиоматической теории, использованной для интерпретации. Если все аксиомы из превращаются в истинные утверждения, то построенная интерпретация называется моделью данной системы аксиом . (Если же хотя бы одна аксиома превратилась в ложное утверждение, то можно считать, что интерпретирование не удалось: ведь цель интерпретирования — построить модель системы аксиом!)

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

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

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

К непротиворечивости арифметики аналогичным образом сводится непротиворечивость обширных областей классической математики. Тем не менее "абсолютная" непротиворечивость ни геометрии Лобачевского, ни евклидовой геометрии, ни арифметики натуральных чисел не установлена. Уверенность в непротиворечивости этих теорий, в их истинности есть своего рода акт веры.

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

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

Категоричность аксиоматических теорий

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

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

Определение 27.2. Аксиоматическая теория называется категоричной, если любые две ее модели изоморфны.

Примерами категоричных теорий служат аксиоматические теории евклидовой геометрии, различных систем чисел: натуральных, целых, рациональных, действительных, комплексных. Категоричность евклидовой геометрии доказывается в курсе геометрии. Категоричность теорий систем чисел устанавливается в курсе "Числовые системы".

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

Независимость системы аксиом

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

Определение 27.3. Аксиома из системы аксиом называется независящей от остальных аксиом этой системы, если ее нельзя вывести (доказать) из множества всех остальных аксиом системы .

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

Определения 27.3, 27.4 равносильны.

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

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

Интересно отметить, что проблема независимости систем аксиом является, по существу, самой первой проблемой в основаниях математики. Уже ближайшим последователям Евклида было известно, что если воспользоваться понятием движения, то его IV постулат, утверждающий, что все прямые углы равны между собой, может быть доказан как логическое следствие остальных аксиом и постулатов. Также было известно, что аксиомы "Если удвоим равные, то получим равные" и "Половины равных равны между собой" являются логическими следствиями остальных. С размышления над проблемой независимости менее тривиального V постулата Евклида, собственно, и началась наука об обосновании геометрии. Проблема непротиворечивости тогда не возникала, да и не могла возникнуть вплоть до XIX в., пока Лобачевский не указал метод доказательства независимости аксиом — метод построения моделей.

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

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

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

Система аксиом называется независимой, если каждая ее аксиома не зависит от остальных. Отсюда ясно, насколько кропотливо исследование системы аксиом на независимость. Если для доказательства непротиворечивости данной системы аксиом достаточно построить одну ее модель, то для доказательства ее независимости придется построить столько моделей, сколько аксиом содержит система, причем каждая модель должна реализовывать все аксиомы, кроме одной — исследуемой на независимость.

Полнота аксиоматических теорий

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

Выделяют понятие внутренней полноты. Здесь различают две его модификации: абсолютная полнота и полнота в узком смысле.

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

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

Всякая абсолютно полная теория будет полна и в узком смысле.

Доказательство. В самом деле, допустим, что некоторая абсолютно полная теория не полна в узком смысле. Значит, найдется такое утверждение этой теории, недоказуемое в ней, что новая теория, построенная на основе прежних аксиом и утверждения в качестве новой аксиомы, непротиворечива. Ясно, что принадлежит новой теории. Кроме того, ввиду абсолютной полноты исходной теории и недоказуемости в ней утверждения заключаем, что в ней доказуемо . Но все аксиомы, из которых выведено , вошли в состав системы аксиом новой теории. Поэтому принадлежит и новой теории. Получаем противоречие с тем, что новая теория непротиворечива.

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

Классическим примером неполной системы аксиом является система аксиом и постулатов "Начал" Евклида. Уже при доказательстве первых теорем Евклид вынужден молчаливо прибегать к наглядности и очевидности. Так, для обоснования наличия точки пересечения у двух прямых, у двух окружностей, у прямой и окружности требуется аксиома непрерывности, что было осознано математиками лишь в XIX в. Понятие равенства фигур Евклид определяет через движение: "И совмещающиеся равны между собой". Но свойства движения, которые Евклид, несомненно, почерпнул из эмпирических представлений о механическом движении твердых тел и которыми он широко пользуется при доказательстве теорем, никак не выражены в его аксиомах. Нет среди евклидовых аксиом и аксиом порядка или расположения (поэтому тот факт, что прямая делит плоскость на две части, очевиден для Евклида), как и аксиом, связанных с измерением длин, площадей и объемов. (Последнюю задачу блестяще решил великий геометр, механик и инженер древности Архимед, живший непосредственно после Евклида (287–212 гг. до н.э.), который в своем сочинении "О сфере и цилиндре" развил теорию измерения площадей и объемов, получив, в частности, формулы площади поверхности и объема шара, ввел аксиому, носящую и поныне его имя).

Другим примером неполной системы аксиом может служить система аксиом абсолютной геометрии (аксиомы I–IV групп системы аксиом Гильберта). В этой системе не может быть ни доказано, ни опровергнуто ни одно предложение, опирающееся на аксиому параллельности Евклида (V.1) или аксиому параллельности Лобачевского (а также, конечно, и сами эти аксиомы).

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

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

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

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

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

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