1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 33
Текст из файла (страница 33)
. , D fk).Из леммD-prodQti3.3.4 и 3.3.3истинно(Q1 /\ ... /\Qп/\ ~Qo)(Dfi, ...получаемI Q(i F (Q1 /\ ··· /\ Qп)(fii, ···, /ki)} Е Dи Z = {i I Qti F Qo(f1i, ... , fki)} 1. D. Очевидно, что Х n У содержитсяв Z. Так как Х n У Е D, то Z Е D - противоречие.б). Пусть f - гомоморфизм Qt на !В. По предложению 3.2.1 б) дляУ=любого термаt{iи интерпретации тFV(t)----,А имеет местоИз этого равенства и определения гомоморфизма получаем, чтоQtF Q[1J ===> !В F Q[1Лдля любой атомарной формулычтоfQсигнатурыI;.
Поэтому в силу того,отображает А на В, из истинности любого тождества Ф вследует его истинность в !В.QtОАксиоматизируемые классы§ 5.2.Теорема5.2.9.159Для \1-аксиоматизируемого класса К сигнатуры:Е следующие условия эквивалентны:1)К-квазимногообразие,2) К замкнут относительно конечных декартовых произведенийи содержит единичную системуДоказательство.l)==;,2)Er,.доказановпредложении 5.2.8,а).Рассмотрим множествоW = {ФIФквазитождество сигнатуры :Е и Ф Е-Th(K)}.Qt - модель W. Покажем, что каждое конечное подмноже<;;; D(Qt) имеет такую модель IВх, что IВх 1 :Е Е К.
ПустьХ = У U Z, где Z состоит из атомных предложений, а У - из отрицаний атомных. Если У = 0, то в качестве 1В х можно взять Er.A. ПустьУ= ГQ1, ... , 'Qп}, Ф - конъюнкция элементов Z, если Z-/=- 0, и Фравно Са ::::! Са для некоторого а Е А, если Z = 0. Пусть Са 1 , ••• , Cak все константы из Сл, входящие в Q1, ... ,Qп,Ф, и Q~, ... ,Q~,Ф'получаются из Q1, ... , Qп, Ф соответственно заменой Са 1 , ••• , Cak наx1, ... ,Xk. Так как квазитождества \lx1 ...
\lxk(Ф _, Qi), q ,(; i ,(; п,ложны в Qt, то они не принадлежат W. Следовательно, существуюттакие системы IВ1, ... , IВп Е К, что IВi F (Ф /\ ·Qi)['Yi], 1 ,(; i ,(; п, длянекоторых 'Yi: { х1, ... , Xk} _, Bi. Рассмотрим декартово произведениеIВ1 х ... х IВп Е К и интерпретацию 'У переменных х1, ... ,Xk в В, длякоторой проекция i('Y) па i-ю координату равна 'Yi· Из леммы 3.3.4получаем, что IВ1 х ... х 1Вn F (Ф /\ 'Q1 /\ ...
/\ 'Qп)["f]. Следовательно,систему IВ1 х ... х IВп можно обогатить до системы IВх сигнатуры:Ел, являющейся моделью Х. Из доказательства теоремы 3.3.6 получаем, что существует ультрапроизведение 1В = D-prod 1В х, являющеесямоделью D(Qt). В силу предложения 5.1.1 О, а) существует такая подсистема IВ1 <;;; 1В 1:Е, что Q( ~ IВ1. Так как 1В 1:Е = D-prod (IВх 1:Е) и1В х 1:Е Е К, то из теорем 5.2.2, 5.2. 7 и из того, что Qt ~ 1В 1, вытекает,что Qt Е К.
Таким образом, получили К= Kr.(W).ОПустьство ХТеорема5.2.10.Для квазимногообразия К сигнатуры :Е следу-ющие условия эквивалентны:1)К-многообразие;2) К замкнут относительно гомоморфных образов.Доказательство.Пусть выполняется2)Z = {Ф I Ф -иl)==;,2) показано вQt - модель множествапредложениитождество сигнатуры :Е и Ф ЕTh(K)}.5.2.86).5.Гл.160Теория моделейРассмотрим множествоD-(!л)=ГФ ЕДля любой формулыЕ, где Ф~q,D(Qt)из1Ф -D-(Qt)атомарная формула}.тождество 1::/у,...
1::/yn Ф 1сигнатуры(Ф1)¼~·i:·.:~;;an, ложно Qt, поэтому оно не принадлежит=Тогда существует S:В,i, Е К и интерпретация 1'Ф: {у,,F ~q, 1 [1'Ф].которых S:В,i,... , Yn}-+ B,i,,Z.дляСледовательно, S:В,i, можно обогатить до системы S:В~ сигнатуры Ел, являющейся моделью {~Ф}. Рассмотрим декартово произведение S:ВIЕимеем S:В~q,Е= D-(Qt)-prod S:В,i,.Е К.
По лемме1а Е А}. По теореме 5.2.76) имеем s:81отображениеh:В, -+ А следующим образом: еслисигнатуры :Е и t'В(v'В(ca 1 ),Корректность определенияF (t1~ t2)(v'В(ca 1 ),=}гдеВ силу предложенияимеет место S:ВF ~q,5.2.8 а)для любогоD-(Qt). Пусть s:81 - подсистема S:В, порожденная в S:В множеством{v'В(са)2'13.3.4Гt, ~t,(x,, ... ,xm)и••• ,•••h1ЕЕ,v'В(cam)) = Ь, то h(Ь) =термt 21 (a,, ... ,am).следует из импликаций:v'В(cam)) =?t2)~~;·:::~,;:,,. tf.
D- (Qt)t2(x,, ... ,xm) -=}2(F (t1Q(x,, ... , Xm)~t2) (а,, ... , ат),любые термы сигнатуры Е. Цепьимпликаций, полученная из предыдущей заменойатомную формулуК. Определимt(x,, ... , Xm) -t1~t2на любуюсигнатуры Е, также имеет место, слеh является гомоморфизмом S:В 1 1Е на Qt. Из 2) получаем,Qt Е К. Таким образом, показано, что К= K~(Z).Одовательно,чтоУпражнения1.Пусть К-аксиоматизируемый класс, содержащий системы какугодно больших конечных мощностей. Показать, что класс К00 ,состоящий из бесконечных систем класса К, является аксиоматизируемым, но не является конечно аксиоматизируемым.2.Показать, что в теореме5.2.2условие замкнутости относительно элементарной эквивалентности можно заменить на замкнутостьотносительно изоморфизмов иэлементарных подсистем.(Указание.
В доказательстве теоремысмотреть3.5.2.2вместоTh(Qt) расD*(Qt).)Показать, что любое квазитождество Ф эквивалентно квазитождеству Ф в приведенной н. ф.4.Утверждение, аналогичное упражнению3,для тождеств не имеетместа. Найти многообразие, которое не имеет системы аксиом,состоящей из предложений вида 1::/х,.. . 1::/xnQ,гдеQ -атомнаяформула.
(Указание. Рассмотреть многообразие с системой аксиом{1::/xP(f(x))}.)§ 5.3.Скулемовские функции161Скулемовские функции§ 5.3.Определение. Множество Т предложений сигнатурыотносительно выводимости (т. е. если Т [> Ф и ФнатурыI:,-I:,замкнутоепредложение сигто Ф Е Т}, называется элементарной теорией или простотеорией сигнатуры Е. Непротиворечивая теория Т сигнатуры Е называется полной, если Ф Е Т или ~Ф Е Т для любого предложенияI:Ф сигнатуры Е. Непротиворечивая теория Т сигнатурымодельнополной,если Qt ~ S:В ==} Qt-<S:Вдляназываетсялюбых моделей Qt,S:В теории Т, имеющих сигнатуру Е.
Формулы Ф и Ф сигнатуры Еназываются эквивалентными относительно теории Т сигнатуры Ет(обозначаем Ф=Ф}, если Т [> (Ф-+ Ф)/\(Ф-+ Ф). Теория Т сигнату-ры Е называется \:/-аксиоматизируемой или универсально аксиоматизируемой (3-аксиоматизируемой, \:/3-аксиоматизируемой},существует такое множество\:/3-предложений), чтоZZесли<;;;; Т \:/-предложений (3-предложений,[> Ф для любого Ф Е Т.
Такое множествоZназывается системой аксиом для теории Т.Изследствия4.5.8вытекает,чтотеорияТсигнатуры"Е\:/-аксиоматизируема (3-аксиоматизируема, \:/3-аксиоматизируема) точнотогда, когда класс К= К~(Т) \;/-аксиоматизируем (3-аксиоматизируем,\:/3-аксиоматизируем}, причем еслиZZ -система аксиом для К~(Т), тоявляется системой аксиом для Т, и наоборот.Теория Т сигнатуры Е называется теорией с элиминацией кванторов, если любая формула Ф сигнатуры Е эквивалентна относительно Тнекоторой бескванторной формуле Ф. Очевидно, что непротиворечиваятеория с элиминацией кванторов модельно полна. С другой стороны,модельно полная теория Т является <<почти» теорией с элиминациейкванторов. А именно, имеет место следующаяТеорема5.3.1. Длятого чтобы непротиворечивая теория Т сигнатуры Е была модельно полной, необходимо и достаточно, чтобылюбая формула Ф сигнатуры Е была эквивалентна относительноТ некоторой \:/-формулеД о к аз ат ель ст в о.5.2.5,Xiи некоторой 3-формуле Х2.Достаточностьследуета).
Необходимость получаем из леммытеорию Т.Конечно, в теореме5.2.6,изпредложениявзяв в качестве ГD5.3.1требование эквивалентности Ф некоторой3-формуле Х2 можно опустить, так как это следует из эквивалентности~Ф некоторой \:/-формуле.Работать с формулами, содержащими кванторы, гораздо трудней,чем с бескванторными.
Поэтому теоремы теории моделей вида: дан-6Ю. Л. Ершов, Е. А. ПалютинГл.1625.Теория моделейная теория Т является теорией с элиминацией кванторов (являетсямодельно полной)-очень важны. Сейчас мы изложим некоторую конструкцию, впервые предложенную Т. Скулемом, позволяющую любуютеорию расширять до \1-аксиоматизируемой модельно полной теории.Определение. Если Е -сигнатура, то сигнатура Е 8 получаетсяиз Е добавлением новых n-местных функциональных символов fФ длякаждой формулы Ф=:3хФ сигнатуры Е, начинающейся с квантора существования и имеющей п свободных переменных.
ЧерезSобозначиммножество предложенийдля всех формул Ф(х 1 , ... , Хп)=:3хФ(х,xi, ... , Хп)сигнатуры Е сосвободными переменными х 1 , ••• , Xn, выписанными в порядке расположения их первых свободных вхождений в формулу Ф. Если Тсигнатуры Е, то через Т 8 обозначим теорию{ Ф I Ф - предложение сигнатуры Е 8 и Т U S[>-теорияФ }.Сигнатура Е 8 (теория Т 8 ) называется скулемизацией сигнатуры Е(теории Т). Модель Qt 8 теории (Th(Qt)) 8 , имеющая сигнатуру Е 8 ,называется скулемизацией системы Q( сигнатуры Е, если Qt 8 1Е = Qt.В отличие от Е 8 и Т 8 скулемизация Qt 8 не определяется по Qtоднозначно, две скулемизацииQtэквивалентными (см. упражнениемогут быть даже неэлементарно1), более того из упражнения 1вытекает, что Т 8 почти всегда не полна.Предложение5.3.2.а). Пусть Тмодель теории Т 8 и Q( ~ S:В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
