1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 40
Текст из файла (страница 40)
Пусть 21, !В -две К+-сиих базисы. Из определения базисаследует, что любое разнозначное отображениеединственным образом до изоморфизма21f:Х --+ У продолжаетсяна !В(!(Х)). Поэтому в силуIXI = IYI. Если х): w, тоIXI = IYI = х. Если х < w и IXI ::;; IYI,!131 ~ !В. Так как IB11 = IAI = IBI, тоDсвойства 1) базиса достаточно заметить, чтоиз леммы 5.6.5, б) получаемто 21 изоморфна подсистеме!131 = !В.Упражнения1.Показать, что теория То плотных линейных порядков без первого и последнего элемента не категорична ни в какой бесконечной несчетной мощности. (Указание.То мощности х>Пусть21 -модельw и Qto -счетная модель То, для котороймодель 211 с носителем А 2 и отношениемАо n А= 0, рассмотрим(а,Ь) ::;; 211 (c,d) ~ (а< 21 с или (а= с и Ь ::;; 21 d)) и модель 212с носителем А U Ао и отношениема ::,; 212 Ь ~ ((а Е А и Ь Е Ао) или (а, Ь Е А и а::,;2!Ь) или(а, Ь Е Аои а ::,;2to Ь));тогда2.211и212неизоморфны.)Показать, что многообразие булевых алгебр категорично во всехконечных мощностях и некатегорично во всех бесконечных.3.
Доказать, что многообразие М с аксиомами (кванторы всеобщности опущены)1) f(g1(x),g2(x)) ~ х,2) J(x,y) ~ f(g1(x),g2(y)),3) g1(f(g1(x),g1(y))) ~g1(x),4) g2(!(91(x),g1(y))) ~ g1(y),5) 9i(9k(x)) ~gk(x), i,k Е {1,2},RQ-формулы и 'Е-формулы§ 5. 7.категоричнововсехv'21(f) для любоймощностях.191(Указание.Показать,что(gF[A]) 2 на Аи любое разнозначное отображение h: gF[A]-+ g?3[B] для Qt, 23 ЕЕ М продолжается до изоморфизма системы Qt на 23(h(gF[A])),переводящего а в J'E(hgF(a), hgr(a)).)4.Qt Е М разнозначно отображаетПостроить пример, показывающий, что в теоремеутверждать, что К категорично также в мощности5.Обобщить предложение5.6.35.6.41.нельзяна теории, категоричные в бесконечной мощности х, и получить тем самым теорему Линдстремав полном объеме.
(Указание.с заменой5.6.3Применить метод предложенияна х и показать, что если формула Ф не сохраwняется при переходе к подмоделям теории Т, то Ф не сохраняетсяпри переходе к подмоделям мощности х.)§ 5.7.Пусть аRQ-формулы и :Е-формулы= (~ 2, ••• )-произвольная сигнатура с выделенным двуместным предикатным символомвведяврассмотрение наряду~- Расширим синтаксис языка ИПа,с обычными ограниченныекванторы.Формулы, возможно содержащие ограниченные кванторы, будут называться RQ-формулами. Дадим точное определение RQ-формул.Определение. RQ-формулы:любая атомарная формула языка ИПа есть RQ-формула;-если Ф и ФRQ-формулы ИПа, то ~Ф,-(Ф V Ф),(Ф/\Ф),(Ф-+ Ф) суть RQ-формулы;если х-переменная,мула, то :3х ~ tФ,МожномулыФ,определитьрасширив'vxt -терм, где х1 FV(t),множествоопределениесвободныхмножестваFV(Ф) для обычной формулы Ф добавлениемFV(:3x~ tФ)(=а Ф-RQ-фор~ tФ, :3хФ, 'vхФ суть RQ-формулы.FV('vx~ tФ )) ==;переменныхRQ-форсвободныхпеременныхсоотношения 1)(FV( Ф) \{х}) UFV(t)).Для дальнейшего важны два подкласса RQ-формул: Ло-формулы и:Е-формулы.
Приведем их определения.Определение. Ло-формулы:-любая атомарная формула языка ИПЕ есть Л 0 -формула;если Ф и Ф-Ло-формулы, то ~Ф, (Ф V Ф), (Фсуть Л 0 -формулы;') Знак =. читается <<положим по определению,>./\Ф), (Ф-+ Ф)Гл.192еслих5.переменная,-Теория моделейтерм,t -iгде хаFV(t),Ф-до-формула, то Зх ~ tФ, \/х ~ tФ суть до-формулы.Определение. Е-формулы:любая до-формула есть Е-формула;-еслиФиФЕ-формулы,-то(Ф V Ф)и(Ф Л Ф)сутьЕ-формулы;если х-переменная,-терм,t -iгде хаFV(t),ФЕ-формула, то Зх ~ tФ, \/х ~ tФ, ЗхФ суть Е-формулы.Для того чтобы определить понятие истинности RQ-формулы наалгебраической системе Qt, следует рассматривать формулу Зх ~ tФкак сокращение формулы Зх(х ~кращение формулы \/х(х ~t--tЛ Ф), а формулу \/х ~ tФtФ) в случае, когда хiFV(t).как соИменно,к индукционному определению понятия истинности, данному в§ 3.2,добавим два дополнительных случая.Рассмотрим алгебраическую систему Qt сигнатуры и и интерпретацию переменных 'У: Х10.Qt=Если Ф1= Ф['У]--tА.:3х ~ tФ 0 -RQ-формула, FV(Ф) ~ Х, то отношениеимеет место тогда и только тогда, когда существует интерпретация 'Уо: ХU {х}--tА такая, что"(ОrХ \{х}= "( r Х \('Уо(х), t 21 ['Y]) Е ~ 21Qt11.= \/хЕсли Ф1=~ tФ 0 -{х},[т.
е. 'Уо(х) ~ 21 t 21 ['Y]],1= Фо['Уо].RQ-формула, FV(Ф) ~ Х, то отношениеQtФ['У] имеет место тогда и только тогда, когда Qtинтерпретации 'У: Х U {х} --t А такой, что"(о1= Фо['Уо]для любойr х \ {х} = 'У r х \ {х},Пусть Qt иIJ3,Qt ~113, -Определение. Системаалгебраические системы сигнатуры и.113называется концевым расширением системы Qt (обозначается Qt ~endIJ3),если для любых а Е А, Ь Е В изсоотношения (Ь, а) Е ~~ (Ь ~~ а) следует принадлежность Ь Е А (темсамым Ь ~ 21 а).Предложение'У:FV (Ф)--tQtА-1= Ф['У]Qt5.7.l.ПустьQt ~end113,Ф-RQ-формулаинтерпретация. Тогда~IJ31= Ф['У]1= Ф['У] =? IJ3 1= Ф['У]для любой до-формулы Ф,для любой :3-формулы Ф.иRQ-формулы и "Е-формулы§ 5.
7.До к аз ат ель ст в о.193Утверждение устанавливается индукцией попостроению формулы Ф с использованием сформулированных и доказанных ниже утверждений(1)(1)-(6).Если формула Ф атомарна и имеет вид R(to, ... , tn),. . . , tn),t ;=; (to, ...тоF R(t)['Y]2(Так как trЫ=(t~['Y], ... ,t~['Y]) Е R21..{=>t;Э[1], i ~ п, и(t~['Y], ... ,t~['Y]) ER21.{=>R2!.
= R'13n лп+I,(t~['Y], ... ,t~['Y]) ER'13имеем{=>!В pR(t)['Y].Аналогично рассматривается случай, когда формула Ф имеет видto~t1.(2)Если Фо, Ф1RQ-формулы и Т FV(Фo)-интерпретация такая, что 2( р Фi['У]{=>U FV(Ф1) --ti = О, 1,!В р Фi['У],F ~Фо['У]{=>!В2t р (Фо V Ф1)[1]{=>!В р (Фо V Ф1)Ьl,2t р (Фо /\ Ф1)[1]{=>!В2t р (Фо - Ф1)Ьl{=>!В2tА-тоF ~Фо['У],F (Фо /\ Ф1)[1],F (Фо - Ф1)['У].Утверждение следует из определения истинности формул.(3) Если Фо, Ф1 -RQ-формулы и Т FV(Фo) U FV(Ф1)интерпретация, такая, что 2( р Фi['У] =? !В р Фi['У], i2tF (Фо V Ф1)[1]=? !ВF (Фо V Ф1)[1],2tF (Фо /\ Ф1)[1]=? !ВF (Фо /\ Ф1)[1].=О,--t1,А-тоУтверждение следует из определения истинности формул.(4)Пусть 2( р Ф['У]{=>!В р Ф[1] для RQ-формулы Ф и любойинтерпретации т Х- А такой, чтоинтерпретации т FV(:3x ~ tФ) - АFV(Ф) ~ Х.
Тогда для любой2t р :3х ~ tФ[1]{=>!В р :3х ~ tФ['У],2( р{=>!В р'vx ~ tФ[1]'vx ~ tФ[1].Установим лишь первую эквивалентность, поскольку вторая выводится аналогично. Пусть 2( р :3х ~ tФ[1]. Тогда согласно случаюсуществует интерпретация 'Уо t Х~ Х, ,'оIХ \ {х}='УIU {х} -10А такая, что FV(:3x ~ tФ) ~Х \ {х}, ,'х(х) ~21.
t21.['Y], 2t р Ф[10]. Ввиду сделанных предположений !В р Ф[10] и !В р :3х ~ tФ[1]. Пусть7Ю. Л. Ершов. Е. А. ПалютинГл.194Теория моделей5.!В F 3х ~ tФ[,]. Тогда существует интерпретация ,о: Х U {х}----, Втакая, что ,о I Х \ {х} = 1 1 Х \ {х}, ,о(х) ~'JЗ t'JЗ[,] и !В F Ф[,о].Так как 1 - интерпретация в А, имеет место равенство t'JЗ [,] = t 21 [,].Кроме того, соотношение 10 (х) ~'JЗ t'JЗ [,] = t 21 [1 ] (напомним, что !В концевое расширение Qt) влечет 10 (х) Е А (и 10 (х) ~ 21 t 21 [1 ]). Но тогда ,о- t21 [I Х \ {х} = 1 1Х \ {х},1 ] и Qt р Ф[,о], поскольку !В р Ф[,о] ==> Qt F Ф[,о]. Слеинтерпретация в А такая, что ,о,о(х) ~ 21довательно, Qt(5)F 3х (tФ[,].Пусть Qt р Ф[,]==>!В р Ф[ 1 ] для RQ-формулы Ф и любойинтерпретации,: Х----, А такой, что FV(Ф) <;;;; Х. Тогда для любойинтерпретацииУстановимказываетсяF!В\:/х1 : FV(3x (Qt р 3х ( tФ[,]==>!В р 3х(Qt р \:/х ( tФ[,]==>!В р \:/х( tФ[,].лишьвторуюаналогично.( tФ[,].для любойtФ)----, АВвидуимпликацию,ПустьFQtслучая\:/хtФ[,],такдостаточно11какперваядоПокажем,чтоустановить,чтоtФ[ 1].(FV(\:/x ( tФ) U {х} ----, В такой, что,о f FV(\:/x ( tФ) \ {х} = 1 f FV(\:/x ( tФ) \ {х} и ,о(х) ('JЗ t'JЗ[,],верна формула !В F Ф[1о].
Пусть 10 такая интерпретация.Поскольку 1 интерпретация в А, имеем t'JЗ [,] = t 21 [,] Е А.Из ,о(х) ('JЗ t'JЗ[,] = t 21 [1 ] следует (с учетом Qt (end !В), что 1о(х) Е Аи 10 (х) ( 21 t 21 [1 ]. Но тогда 10 является интерпретацией в А такой, что,о I FV(\:/x ( tФ) \ {х} = 1 1FV(\:/x ( tФ) \ {х}, ,о(х) ( 21 t 21 [1 ]. В силуистинности Qt р \:/х ( tФ[,] получаем Qt р Ф[,о], откуда !В F Ф[,о].(6)интерпретации ,о:Пусть QtF Ф[,] ==>!ВF Ф[,]для RQ-формулы Ф и любойинтерпретации,: Х----, А такой, что FV(Ф) <;;;; Х.
Тогда для любойинтерпретации1 : FV (Ф) \ {х} ----,Qt р 3хФ[ 1 ]А справедлива импликация==>!В р 3хФ[ 1 ].Действительно, пусть интерпретациячто QtF 3хФ[,].тация такая, что 1ои !В р 3хФ[ 1 ].I FV(Ф) \{х}Таким образом, предложениеПустьQt -,: FV (Ф) \ {х} ----,U {х}----, А -Предположим, что ,о: FV(Ф)=15.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
