Колмогоров, Драгалин - Введение в математическую логику (947386), страница 21
Текст из файла (страница 21)
3 $1. С) Таким образом, если формула В выводится в теории Т, . то В истинна во всякой модели теории Т. Из теоремы Геде- ля о полноте исчисления предикатов вытекает и обратное: ' если формула В истинна во всякой модели теории Т, то В выводится в теории Т. Наш, казалось бы, чисто формальный аппарат выводимости оказывается адекватным инструмен- том установления истинности фактов в теории. 3. Приведем некоторые примеры формальных теорий. Элементарная арифметика Аг есть формальная аксиома- тическая теория в языке Аг (см. п. ! $4, гл. П). Нелогичес- кие аксиомы Аг суть формулы следующих видов. Аксиомы равенства: !) х=х; 2) х=уДх=я~у=а. Аксиомы Пеано-; 3) 5хчн0; 4) (5х=5у) = — х=у; б) А (О) Д)У х (А (х) =эА (5х7 ):эухА (х) (принцип полной математической индукции; здесь А(х) произвольная формула Аг, так что б) определяет бесконеч- ную серию аксиом, схему аксиом индукции).
Определяющиа аксиомы для сложения и умножения: 6) х+О=х; 7) х+5у=5(х+у); 8) х 0=0; 9) х.5у=х.у+х, Определение теории Аг закончено. Легко видеть, что мо- дель ы языка Аг является моделью и формальной теории Аг. У п р а жн е и и е. Докажите, что аксиома !) выводится из 2) и 6) и, таким образом, является излишней. (Тем не ме- нее мы приводим ее в целях единообразного введения акси- ом равенства в различных теориях, И в дальнейшем мы да- леко не всегда будем приводить минимальный список ак- сиом.) С помощью аксиом 1) и 2) докажите, что Аг 1 — х=у:эу=х. Аксиомы !) — 9) выбраны таким образом, чтобы все обычные факты, верные в ы и формулируемые на языке Аг, выводились бы в Аг.
В этом отношении успех аксиоматики Аг впечатляет: привести пример истинного в ы, но не выво- димого в Аг утверждения очень непросто. Впервые некото- рый искусственныи пример такого рода привел Гедель 109 в 1931 году, примеры же математически содержательных теорем, невыводимых в Аг, появились совсем недавно. Если М вЂ” модель языка 11, то через Тп,(М) обозначим множество всех предложений языка (г, истинных в М. Множество ТЬ~(М) называется теорией модели М.
С другой стороны, если Т теория в языке й; то через Щ обозначим множество всех предложений, выводимых в Т (так называемое логическое замыкание теории Т). Теория Т называется полной по отношению к модели М, если Щ=ТЬа(М). Теория Т называется просто полкой, если для всякого предложения А в языке й имеем Ть-А или Т 1 — ~ А.' Упражнение. Докажите следующие утверждения, 1) Если теория Т полна по отношению к некоторой модели М, то Т является полной теорией. 2) Если Т вЂ” полная теория, то Т является полной по отношению ко всякой модели теории Т.
Как мы отметили выше, [Аг)ыТплг(в), но (Аг)ФТЬл (е), так что элементарная арифметика — неполная теория. Далее, теория Т называется разрешимой, если множество (Т) рекурсивно. Иными словами, Т разрешима, если существует алгорифм, позволяющий по любому предложению А выяснить, верно ли Т ~- А или нет. Известно, что множество [Аг1 рекурсивро-перечислимо„ но не разрешимо, так что элементарная арифметика — неразрешимая теория. Что касается множества Тп„,(в), то оно даже не рекурсивно перечислимо.
Еще один замечательный факт, открытый Сколемом в 20-х годах, состоит в том, что существуют модели элементарной арифметики (и даже'модели Тйл,(м)), существенно неизоморфные модели Гэ. Они называются нестандартными моделями арифметики. И хотя'в такой модели выполняются все аксиомы арифметики 1) — 9), в том числе и аксиомы Пеано, все же, например, существуют подмножества множества объектов модели, не имеющие первого элемента в смысле порядка, определимого естественной формулой арифметики! Как же быть тогда с утверждением, что аксиомы Пеано однозначно определяют' натуральный ряд (категоричность натурального рядаг) Следует ясно понимать, что здесь различаются постановки:вопроса.
Категоричность натурального ряда означает, что в рамках некоторой. теоретико-множественной системы„ например, системы Цермело — Френкеля (так сказать, внутри системы) можно доказать единственность натурального ряда (с точностью до изоморфизма), существенно пользуясь законами теории множеств. Модель же элементарной арифметики совсем не обязана быть;натуральным рядом, это должна быть просто интерпретация языка Аг, удовлетворяющая аксиомам 1) — 9). Принцип индукции (схема аксиом 5) 110 должен -выполняться не для. всех теоретико-множественно понимаемых свойств А(х), а только для свойств, выразимых в языке Аг.
Такая структура, может быть, и не изоморфна обыкновенному ряду, Так, подмножество без первого элемента в нестандартной модели существует,.но это подмножество невыразимо в языке Аг. Кстати, если теория Цермело — Френкеля непротнворечива, то у нее тоже существуют неизоморфные модели.
В каждой такой модели ввиду категоричности существует только один натуральный ряд, хотя натуральные ряды из разных моделей могут быть и неизоморфны1 Доказательство всех этих классических результатов читатель найдет в более подробных руководствах по математической логике (см. список литературы в конце книги). 4. Рассмотрим теперь элементарную теорию действительных чисел й. Эта теория, так же как и Аг, — в языке Аг, Нелогические аксиомы К суть формулы следующих видов.
Аксиомы равенства: 1) х=х; 2) х=уЛх=я~у=я; 3) х=у~5х=5у; 4) х=у:эх+я=у+а; 5) х=у=зх г=у х. Эта группа аксиом подобрана таким образом, чтобы выводились следующие схемы, определяющие схемы равенства: а) х=у~. 1(х) =1(у); Ь) х=у=з, Л(х) — Л(у); с) х=х. Здесь 1 — произвольный терм, а Л вЂ” произвольная формула языка. Иногда в теории определяющие' схемы равенства а) — с) сразу принимают в качестве аксиом, причеьг относят их к разряду. логических аксиом.
В таких случаях говорят, что теория рассматривается в исчислении прединатов с равенством. Мы все же в наших примерах будем явно описывать аксиомы, относящиеся к равенству, и считать их нелогическими аксиомами. Но при этом, конечно, схемы а)— с) будут выводиться.
Аксиомы поля: 6) 0~50; -7) х+О=х1 3) х+у=у+х; 9) (х+у) +г=х+'(у+я); 10) ~у(х+у=О); 11) х 50=х; ' 12) х-у=у х; 13) х (у г) = (х у) гй 14) х~О:з йу(х у=50); 15) х (у+я) =х у+х г. Аксиомы порядка: 18) ~г(г'=х'+уз) !7) х+у=О~ ~г(х=гз~/у=г~). Здесь, конечно, х"= х х. Если ввести естественное сокращение: х<у -~ г(х+г'=у), то написанные выше аксиомы порядка позволят вывести все обычные свойства порядка в области действительных чисел. Читателю в качестве упражнения рекомендуется убедиться в том, что из аксиом !) — 17) вытекают следующие свойства порядка: с() х<х; е) х<уЛу<г~х<г; 1) =у= (х<уЛйх); у) х<у~/у<х; и) 0 <х= ~ у(х=уз); !) х<уэх+г<у+г; 1) 0<хЛу<г~х у<х г; й) 0<50.
Определим, далее, х<у= (х<у)Лхчьу. Пусть !(х)— произвольный терм' языка Аг. Следующая формула называется аксиомой вещественной замкнутости; 18) х<уЛ!(х) <ОЛО<!(у) ~ 3 г(х<гЛг<уЛ!(г) =0). ' Суть аксиомы состоит в том, что если многочлен с вещественными коэффициентами принимает на концах некоторого отрезка значения разных знаков, то внутри отрезка он обращается в нуль в некоторой точке. Формулировка теории К.закончена. Сразу видно, что множество действительных чисел К является моделью теории К.
В отличие от Аг теория К является полной и разрешимой. Этот замечательный факт был обнаружен Тарскнм. Модели теории К называются в алгебре вещественно замкнутыми упорядоченными полями. Хорошо известны модели теории К, неизоморфные множеству всех действительных чисел. Так, счетное множество алгебраических чисел составляет модель К.
Известны и более экзотические модели, являющиеся неархимедовыми полями. 5. Рассмотрим теперь теорию 1.!и в языке Е!п. Нелогические аксиомы 1!п суть следующие. Аксиомы равенства: 1) х=х; 2) х=уЛх=гну=а; 3) х~уЛх<г~у<г; 4) х=уЛг<х~г<у. Аксиомы порядка: 5) 1х<х 6) х<уЛу<г~х<г; 7) х<у:» 3г(х<гЛг<у); 8) 3г(г<х); 9) Дг(х<г). Формулировка теории Е)п закончена. Множество Я рациональных чисел и множество ц действительных чисел с естественным порядком являются, очевидно, моделями 1.!п. Вообще модели 1.!и называются плотными лннейнымн упорядочениями без первого и последнего элементов. Теория 11п полна и разрешима. Примечательная особенность 11п состоит в том, что все счетные модели Е!п изоморфны и, следовательно, изоморфны Я.
Как говорят, теория 1.!п категорична в счетной мощности. Заметим, что теория ц выглядит более мощной по своим выразительным возможностям, чем теория Е)п, В самом деле, в ц можно определить некоторые, уже, быть может, и не атомарные формулы х=у, х<у, относительно которых все аксиомы 1!п могут быть'выведены в В.
Мы говорим, что теория 1.1п интерпретируется (или относительно интерпретируется) в теории К. Обшее определение важного понятия относительной интерпретации одной теории в другой довольно громоздко, и мы не будем его давать. Коротко говоря, теория Т, относительно интерпретируется в теории Т„если все атомарные понятия теории Т, могут быть выражены в виде формул и терман Тэ таким образом, что все нелогические аксиомы Т, оказываются выводимыми в Ть по крайней мере если объекты Т, изображаются некоторой частью объектов Ть Эта часть определяется формулой Тт. Если формула выводима в Ть то ее интерпретация выводима в Т,. В частности, если в Т, выводимо противоречие АЛ 1 А, то после интерпретации окажется, что в Т, также выводимо некоторое противоречие. А отсюда следует, что из непротиворечивости Т, следует непротиворечивость Т,. Таким образом, можно устанавливать непротиворечивость теорий, не обращаясь к моделям.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
