Игошин Математическая логика и теория алгоритмов (1019110), страница 59

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 59)

Например, двухэлементное множество (е, а) вместе с определенной на нем по следующим правилам операцией: е е= а. а = е, е. а= а е= а является, как нетрудно убедиться, моделью теории групп. Поэтому с полной уверенностью можно утверждать, что аксиоматическая теория групп непротиворечива. Категоричность. Это свойство в значительной мере характеризует происхождение аксиоматической теории (см. ~ 26, п.«Как возникают аксиоматические теории»). В большинстве категоричные теории возникали на первом пути.

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

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

Примерами категоричных теорий служат аксиоматические теории евклидовой геометрии, различных систем чисел: натуральных, целых, рациональных, действительных, комплексных. Категоричность евклидовой геометрии доказывается в курсе геометрии. Категоричность теорий систем чисел устанавливается в курсе «Числовые системы», Некатегоричная аксиоматическая теория имеет существенно различные (т.е. неизоморфные) модели.

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

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

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

Определения 27.3, 27.4 равносильны. Доказательство. В самом деле, из первого определения вытекает второе, так как если утверждение А нельзя вывести из мно- 241 жества Е'~(А), то его не будет среди теорем теории 77г(Е~(А)) и оно будет среди теорем теории 7л(Е), т.е. ТЬ(Е (А)) ~ ТЬ(Е). Обратно, если Тл(Е~,(А)) ~ 7Ъ(Е), то А нельзя вывести из Е'~(А), ибо в противном случае, каждая теорема, выводимая из Е, могла бы быть выведена и из Е~(А), т.е. каждая теорема из ТЬ(Е) принадлежала бы теории ТЬ(Е~,(А)), т.е. ТЬ(Е) ~ ТЬ(Е'~(А)), что противоречило бы условию.

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

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

Также было известно, что аксиомы «Если удвоим равные, то получим равные» и «Половины равных равны между собой» являются логическими следствиями остальных. С размышления над проблемой независимости менее тривиального Ч постулата Евклида, собственно, и началась наука об обосновании геометрии. Проблема непротиворечивости тогда не возникала, да и не могла воз- 242 пикнуть вплоть до Х1Х в., пока Лобачевский не указал метод доказательства независимости аксиом — метод построения моделей.

В чем же состоит метод доказательства независимости аксиомы А от остальных аксиом непротиворечивой системы аксиом з.? Рассмотрим систему аксиом (У.'х(А)) 0 ( А), получающуюся из Е заменой аксиомы А ее отрицанием ~А. Если окажется, что полученная система аксиом, так же как и з., непротиворечива, то отсюда будет следовать независимость аксиомы А от аксиом из ьЯА).

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

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

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

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

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

Характеристики

Список файлов книги