Диссертация (1104034), страница 9
Текст из файла (страница 9)
, xskk ) òàêàÿ, ÷òîA |= F(a1 , a2 , . . . , ak ) ⇐⇒ (a1 , a2 , . . . , ak ) ∈ S;â òàêîì ñëó÷àå ìû ãîâîðèì, ÷òî F îïðåäåëÿåò ìíîæåñòâî S. Åñëè èìååòñÿ îïðåäåëèìîå ìíîæåñòâî, òî ìû ìîæåì ðàñøèðèòü ñèãíàòóðó ìîäåëèA íîâûì ïðåäèêàòíûì ñèìâîëîì, îöåíêîé êîòîðîãî áóäåò ýòî ìíîæåñòâî. Ïðè ýòîì ñòàíäàðòíûì îáðàçîì ñòðîèòñÿ ðåêóðñèâíàÿ ôóíêöèÿïåðåâîäÿùàÿ ôîðìóëû ðàñøèðåííîãî ÿçûêà â ýêâèâàëåíòíûå èì íàä Aôîðìóëû èñõîäíîãî.
 òàêîì ñëó÷àå ìû ãîâîðèì îá îïðåäåëèìûõ ïðå-äèêàòàõ. Àíàëîãè÷íî ââîäèòñÿ ïîíÿòèå îïðåäåëèìîé ôóíêöèè.Ïóñòü äàíû ìîäåëü A ñèãíàòóðû σ1 è ìîäåëü B ñèãíàòóðû σ2 .Èíòåðïðåòàöèÿ ìîäåëè B â ìîäåëè A ñîñòîèò èç1. ôóíêöèè i(t) èç ñîðòîâ ñèãíàòóðû σ2 â ñîðòà ñèãíàòóðû σ1 ;2. ñåìåéñòâà, ïðîèíäåêñèðîâàííîãî ñîðòàìè t èç σ2 , ôîðìóë Ut (xi(t) )ñèãíàòóðû σ1 äëÿ âñåõ ñîðòîâ t èç σ2 ;3. ñåìåéñòâà, ïðîèíäåêñèðîâàííîãî ñîðòàìè t èç σ2 , ñþðúåêòèâíûõôóíêöèè pt èç ìíîæåñòâà âñåõ ýëåìåíòîâ óíèâåðñóìà ñîðòà i(t) ìîäåëè A, íà êîòîðûõ âûïîëíÿåòñÿ Ut â óíèâåðñóì ñîðòà t ìîäåëè B(äëÿ êàæäîãî îáúåêòà a ñîðòà i(t) èç îáëàñòè îáëàñòè îïðåäåëåíèÿôóíêöèè pt ìû ãîâîðèì, ÷òî a ÿâëÿåòñÿ èíòåðïðåòàöèåé pt (a));4. äàíà ôîðìóëà Eqt (xi(t) , y i(t) ), îïðåäåëÿþùàÿ ïðåäèêàò ðàâåíñòâà çíà÷åíèé ôóíêöèè pt ;5.
äëÿ êàæäîãî P ∈ Predσ2 , PTypeσ2 (f ) = (s1 , . . . , sk ), â A âûáðàíàîïðåäåëÿþùàÿ ôîðìóëà äëÿ ìíîæåñòâà{(a1 , . . . , ak ) | B |= P (ps1 (a1 ), . . . , psk (ak ))};6. äëÿ êàæäîãî f ∈ Funσ2 , FTypeσ2 (f ) = h(s1 , . . . , sk ), ri, â A âûáðàíàîïðåäåëÿþùàÿ ôîðìóëà äëÿ ìíîæåñòâà{(a1 , . . . , ak , b) | B |= f (ps1 (a1 ), .
. . , psk (ak )) = pr (b)}.54Îòìåòèì, ÷òî èç òàêîãî âûáîðà åñòåñòâåííûì îáðàçîì èçâëåêàåòñÿ èíòåðïðåòàöèÿ Γ, êîòîðàÿ ÿâëÿåòñÿ èíòåðïðåòàöèåé Th(B) â Th(A). Ïóñòüòåïåðü äàíà íåêîòîðàÿ èíòåðïðåòàöèÿ Γ ñèãíàòóðû σ2 â ñèãíàòóðå σ1 òàêàÿ, ÷òî â σ2 íåò ôóíêöèîíàëüíûõ ñèìâîëîâ è èíòåðïðåòàöèè ðàâåíñòââ Γ àáñîëþòíû. È êðîìå òîãî, ïóñòü äàíà ìîäåëü A ñèãíàòóðû σ1 .
Òîãäàîòñþäà åñòåñòâåííûì îáðàçîì âîññòàíàâëèâàåòñÿ åäèíñòâåííàÿ, ñ òî÷íîñòüþ äî èçîìîðôèçìà, ìîäåëü B ñèãíàòóðû σ2 è åå èíòåðïðåòàöèÿ âA òàêàÿ, ÷òî èíòåðïðåòàöèÿ èçâëåêàåìàÿ èç íåå ñîâïàäàåò ñ Γ. ßñíî,÷òî òåì ñàìûì Γ çàäàåò ïðåîáðàçîâàíèå ìîäåëåé ñèãíàòóðû σ1 â ìîäåëèñèãíàòóðû σ2 .Èíòåðïðåòàöèè òåîðèé è ìîäåëåé íàçûâàþòñÿ ýôôåêòèâíûìè, åñëè ðåêóðñèâåí ñîîòâåòñòâóþùèé èì ïåðåâîä ôîðìóë (äëÿ åãî ðåêóðñèâíîñòè íåîáõîäèìî è äîñòàòî÷íî òîãî, ÷òîáû ôóíêöèÿ ñòàâÿùàÿ â ñîîòâåòñòâèå ôóíêöèîíàëüíûì è ïðåäèêàòíûì ñèìâîëàì èõ èíòåðïðåòàöèè îêàçàëàñü ðåêóðñèâíîé).
Âñå èíòåðïðåòàöèè, êîòîðûå âñòðå÷àþòñÿ âýòîé äèññåðòàöèè ÿâëÿþòñÿ ýôôåêòèâíûìè è èõ ýôôåêòèâíîñòü âñåãäàáóäåò î÷åâèäíà èç èõ êîíñòðóêöèè.  ñèëó ýòîãî, ìû, íè÷åãî äîïîëíèòåëüíî íå îãîâàðèâàÿ, ãîâîðÿ îá èíòåðïðåòàöèÿõ ïðåäïîëàãàåì, ÷òî îíèýôôåêòèâíû.Ñ ýôôåêòèâíûìè èíòåðïðåòàöèÿìè ñâÿçàíû äâà õîðîøî èçâåñòíûõ óòâåðæäåíèÿ, êîòîðûå ïîçâîëÿþò äîêàçûâàòü ðåçóëüòàòû î ðàçðåøèìîñòè è íåðàçðåøèìîñòè òåîðèé.Ïðåäëîæåíèå 2.25.Åñëè òåîðèÿ T2 íåðàçðåøèìà è èìååòñÿ ýôôåê-òèâíàÿ èíòåðïðåòàöèÿ òåîðèè T2 â òåîðèè T1 , òî òåîðèÿ T1 íåðàçðåøèìà.Ïðåäëîæåíèå 2.26.Åñëè òåîðèÿ T1 ðàçðåøèìà è èìååòñÿ ýôôåêòèâ-íàÿ èíòåðïðåòàöèÿ òåîðèè T2 â òåîðèè T1 , òî òåîðèÿ T2 ðàçðåøèìà.Äëÿ âñÿêîãî ìíîæåñòâà A ìû îáîçíà÷àåì ÷åðåç P <ω (A) ìíîæåñòâîâñåõ åãî êîíå÷íûõ ïîäìíîæåñòâ.
Ðàññìîòðèì ìîäåëü A îäíîñîðòíîãî èñ÷èñëåíèÿ ïðåäèêàòîâ ñ íîñèòåëåì A. Îïðåäåëèì ìîäåëü, ðàñøèðÿþùóþ55A äîïîëíèòåëüíûì óíèâåðñóìîì. Ìîäåëü A0 ÿâëÿåòñÿ ðàñøèðåíèåì Aäîïîëíèòåëüíîé ïðåäìåòíîé îáëàñòüþ P <ω (A) è ïðåäèêàòîì ∈, ÿâëÿþùèìñÿ îãðàíè÷åííûì íà A × P <ω (A) áèíàðíûì îòíîøåíèåì ïðèíàäëåæíîñòè. Îòìåòèì, ÷òî òåîðèÿ Th(A0 ) íàçûâàåòñÿ ñëàáîé ìîíàäè÷å-ñêîé òåîðèåé ìîäåëè A. Òàêæå ìû îïðåäåëÿåì òðåõñîðòíóþ ìîäåëü A00 ,ðàñøèðÿþùóþ A0 äîïîëíèòåëüíîé ïðåäìåòíîé îáëàñòüþ P <ω (P <ω (A)) èïðåäèêàòîì ∈1 , ÿâëÿþùèìñÿ îãðàíè÷åííûì íà P <ω (A) × P <ω (P <ω (A))áèíàðíûì îòíîøåíèåì ïðèíàäëåæíîñòè.Õîðîøî èçâåñòíî, ÷òî òåîðèÿ Th((N; S)0 ) ðàçðåøèìà [14]. Íåñëîæíî âèäåòü, ÷òî ýëåìåíòàðíàÿ òåîðèÿ Th((N; S)00 ) íåðàçðåøèìà; íèæå ïðèâîäèòñÿ ïðîñòîå äîêàçàòåëüñòâî ýòîãî ôàêòà. ÿçûêàõ òåîðèé Th((N; S)0 ) è Th((N; S)00 ) ïåðåìåííûå x, y, z, .
. .ïðîáåãàþò ìíîæåñòâî N, ïåðåìåííûå X, Y, Z, . . . ïðîáåãàþò P <ω (N). Âÿçûêå òåîðèè Th((N; S)00 ) ïåðåìåííûå Γ, ∆, Θ, . . . ïðîáåãàþò ìíîæåñòâîP <ω (P <ω (N)).Ëåììà 2.27.Òåîðèÿ Th((N; S)00 ) íåðàçðåøèìà.Äîêàçàòåëüñòâî. Ðàññìîòðèì îáîãàùåíèå ìîäåëè (N; S)0 ôóíêöèåéH(x) = 2x.
Ýëåìåíòàðíàÿ òåîðèÿ ýòîé ìîäåëè, êàê èçâåñòíî, íåðàçðåøèìà [18]. Ïîñòðîèì èíòåðïðåòàöèþ ýòîé òåîðèè â (N; S)00 , îòñþäà ìûïîëó÷èì íåðàçðåøèìîñòü Th((N; S)00 ).Ìû áóäåì ñ÷èòàòü äâîè÷íîé çàïèñüþ ÷èñëà n ôóíêöèþ ζn : N →{0, 1} òàêóþ, ÷òî äëÿ íåêîòîðîãî k ïðè âñåõ l > k èìååò ìåñòî ζn (l) =X0 è2i ζn (i) = n. Êàê íåñëîæíî âèäåòü, äëÿ âñÿêîãî íàòóðàëüíîãîi≤k÷èñëà åãî äâîè÷íàÿ çàïèñü, â îïèñàííîì âûøå ñìûñëå, ñóùåñòâóåò èåäèíñòâåííà.Íàòóðàëüíûå ÷èñëà ìû áóäåì ïðåäñòàâëÿòü ýëåìåíòàìè P <ω (N)äëÿ êàæäîãî íàòóðàëüíîãî ÷èñëà n ìû ïîëàãàåì åãî èíòåðïðåòàöèþ nIðàâíîénI = {k | ζn (k) = 1}.56Êîíå÷íûå ìíîæåñòâà íàòóðàëüíûõ ÷èñåë ìû áóäåì ïðåäñòàâëÿòü ìíîæåñòâàìè, ñîñòàâëåííûìè èç ïðåäñòàâëåíèé èõ ýëåìåíòîâ:X 7→ X I := {nI | n ∈ X}.Íåñëîæíî âèäåòü, ÷òî äëÿ ïîñòðîåíèÿ èíòåðïðåòàöèè íàì îñòàëîñü îïðåäåëèòü èíòåðïðåòàöèè S I (X) è H I (X) ôóíêöèé S(x) è H(x)ñîîòâåòñòâåííî.
Âûðàçèì ôóíêöèþ H I (X):H I (X) = Y 0 6∈ Y ∧ ∀x(x ∈ X ↔ S(x) ∈ Y ).Ðàññìîòðèì ôóíêöèþ Tran : P <ω (N) → P <ω (N), çàäàâàåìóþ ñëåäóþùåéýêâèâàëåíòíîñòüþ, âûïîëíåííîé äëÿ âñåõ íàòóðàëüíûõ ÷èñåë n è k:defk ∈ Tran(nI ) ⇐⇒ ζn (k) 6= ζn+1 (k).Çàìåòèì, ÷òî ôóíêöèÿ Tran(X) îïðåäåëèìà â U :Tran(X) = Y ⇐⇒ 0 ∈ Y ∧ ∀x(S(x) ∈ Y ↔ x ∈ Y ∧ x ∈ X).Òåïåðü âûðàçèì ôóíêöèþ S I (X):S I (X) = Y x ∈ Y ↔ (x ∈ X ∧ x 6∈ Tran(X)) ∨ (x 6∈ X ∧ x ∈ Tran(X)).Ëåììà 2.28.Ïóñòü α îðäèíàë òàêîé, ÷òî 2 ≤ α ≤ ω . Òîãäà â ìîäåëèTh(Sα ) èíòåðïðåòèðóåòñÿ ìîäåëü Th((N; S)00 ).Äîêàçàòåëüñòâî. Ñåé÷àñ ìû ïîñòðîèì èíòåðïðåòàöèþ ìîäåëè ñ èñïîëüçîâàíèåì íåòðèâèàëüíîé èíòåðïðåòàöèè ðàâåíñòâà äëÿ P <ω (N) èP <ω (P <ω (N)).
Ïîñòàâèì â ñîîòâåòñòâèå êàæäîìó íàòóðàëüíîìó ÷èñëó nýëåìåíò h2in >. Çàìåòèì, ÷òî ýëåìåíòó x ∈ WNα ñîîòâåòñòâóåò íåêîòîðîåíàòóðàëüíîå ÷èñëî òîãäà è òîëüêî òîãäà, êîãäà x ∈ S2 ∩WN2 . Ïðåäèêàò ðàâåíñòâà äëÿ íàòóðàëüíûõ ÷èñåë èíòåðïðåòèðóåòñÿ ðàâåíñòâîì äëÿ êëàññîâ ýêâèâàëåíòíîñòè ñëîâ. Ôóíêöèÿ S èíòåðïðåòèðóåòñÿ ôóíêöèåé d2 .57Ìíîæåñòâà P <ω (N) è P <ω (P <ω (N)) ìû áóäåì èíòåðïðåòèðîâàòü ìíîæåñòâàìè S1 è S0 , ñîîòâåòñòâåííî.
Ïðåäèêàò ∈ ìû áóäåì èíòåðïðåòèðîâàòüïðåäèêàòîì In1 . Çàäàäèì ïðåäèêàò ∈I1 , èíòåðïðåòèðóþùèé ∈1 :c2 (In1 (w, y) ↔ In1 (w, z))).y ∈I1 x ∃z ∈ Sb1 (In0 (z, x) ∧ ∀w ∈ Sb2 ∩ WÎïðåäåëèì èíòåðïðåòàöèþ ðàâåíñòâà =I2 äëÿ P <ω (N) è èíòåðïðåòàöèþ ðàâåíñòâà =I3 äëÿ P <ω (P <ω (N)) ïî ýêñòåíñèîíàëüíîñòè.x =I2 y ∀z(z ∈I x ↔ z ∈I y)x =I3 y ∀z(z ∈I1 x ↔ z ∈I1 y)Çàìåòèì, ÷òî â ñèëó ëåììû 2.24 èíòåðïðåòàöèÿ ïîñòðîåíà êîððåêòíî.Èñïîëüçóÿ ëåììû 2.27 è 2.28 ìû ïîëó÷àåì ñëåäóþùóþ òåîðåìó.Òåîðåìà 3.Ïóñòü α îðäèíàë òàêîé, ÷òî 2 ≤ α ≤ ω . Òîãäà òåîðèÿTh(Sα ) íåðàçðåøèìà.2.5Ñëîâà èç äâóõ ñèìâîëîâÄëÿ äîêàçàòåëüñòâà ðàçðåøèìîñòè òåîðèè Th(S1 ) ìû äàëåå ïîñòðîèìåå èíòåðïðåòàöèþ â ðàçðåøèìîé òåîðèè Th(ω ω ; <, +) [29].Ëåììà 2.29. òåîðèè Th(ω ω ; <, +) îïðåäåëèìû ñëåäóþùèå ôóíêöèèè ìíîæåñòâà:1.
ìíîæåñòâî {ω x | 1 ≤ x < ω};2. îãðàíè÷åííàÿ íà ìíîæåñòâå {ω x | 1 ≤ x < ω}, ôóíêöèÿ óìíîæåíèÿ íà ω ñïðàâà x 7→ x · ω ;3. ìíîæåñòâî {x ∈ ω ω | `(x) = 0}.Äîêàçàòåëüñòâî. 1. Äîêàæåì, ÷òî äëÿ âñÿêîãî α ∈ ω ωα ∈ {ω x | 1 ≤ x < ω} ⇐⇒ α 6= 0 ∧ α 6= 1 ∧ ∀x < α(∀y < α(x + y < α)).58Çàìåòèì, ÷òî åñëè α ∈ {0, 1}, òî îáå ÷àñòè ðàññìàòðèâàåìîé ýêâèâàëåíòíîñòè ëîæíû. Òåì ñàìûì ìû ïåðåõîäèì ê ñëó÷àþ α 6∈ {0, 1}.Èìïëèêàöèÿ ñëåâà íàïðàâî èìååòñÿ â ñèëó ëåììû 2.21.Äîêàæåì èìïëèêàöèþ ñïðàâà íàëåâî.
Ïóñòü α 6∈ {ω x | 1 ≤ x < ω}.Íàéäåì îðäèíàëû β, γ < α òàêèå, ÷òî β + γ ≥ α. Ðàññìîòðèì êàíòîðîâñêóþ íîðìàëüíóþ ôîðìó α = ω α1 + · · · + ω αn , ãäå α1 ≥ . . . ≥ αnè n ≥ 2. Çàìåòèì, ÷òî (ω α1 + · · · + ω αn−1 ) + (ω α1 + · · · + ω αn−1 ) ≥ω α1 + · · · + ω αn−1 + ω α1 ≥ ω α1 + · · · + ω αn = α. Òåì ñàìûì ìû ìîæåìïîëîæèòü β = γ = ω α1 + · · · + ω αn−1 .2. ω α · ω = β ⇐⇒ β = min({ω x | 1 ≤ x < ω} ∩ {x|x > ω α }).3. `(α) = 0 ⇐⇒ α = 0 ∨ ∃x(α = x + 1).Òåîðåìà 4.Òåîðèÿ Th(S1 ) ðàçðåøèìà.Äîêàçàòåëüñòâî. Õîòÿ âûøå ìû ðàññìîòðåëè ïîíÿòèå èíòåðïðåòàöèèëèøü â îäíîìåðíîì ñëó÷àå, â ýòîì äîêàçàòåëüñòâå íàì ïîòðåáóþòñÿ ìíîãîìåðíûå èíòåðïðåòàöèè äëÿ ñëó÷àÿ îäíîñîðòíûõ ìîäåëåé.  n-ìåðíîéèíòåðïðåòàöèè îäíîñîðòíûõ òåîðèé, îáúåêòû èíòåðïðåòèðóåìîé òåîðèè ñîîòâåòñòâóþò n-êàì îáúåêòîâ èíòåðïðåòèðóþùåé òåîðèè (êëàññè÷åñêèì ïðèìåðîì òàêîé èíòåðïðåòàöèè ÿâëÿåòñÿ èíòåðïðåòàöèÿ òåîðèèïîëÿ êîìïëåêñíûõ ÷èñåë â òåîðèè ïîëÿ âåùåñòâåííûõ, êîãäà êîìïëåêñíîå ÷èñëî èíòåðïðåòèðóåòñÿ ïàðîé ñîñòîÿùåé èç ñâîåé âåùåñòâåííîé èìíèìîé ÷àñòåé).
Ïîäðîáíîå îïðåäåëåíèå ñì. [21, ãëàâà 5]. Äëÿ äîêàçàòåëüñòâà ðàçðåøèìîñòè òåîðèè Th(Sα ) ïîñòðîèì åå ýôôåêòèâíóþ ìíîãîìåðíóþ èíòåðïðåòàöèþ â òåîðèè Th(ω ω ; <, +) è äàëåå âîñïîëüçóåìñÿðàçðåøèìîñòüþ ïîñëåäíåé.Äëÿ êàæäîãî ñëîâà A ∈ WN1 ðàññìîòðèì ìíîæåòâî R(A) âñåõ ïàðîðäèíàëîâ hα, βi òàêèõ, ÷òî ñóùåñòâóåò ñëîâî B ∈ B0 ∩ W1 òàêîå, ÷òîhα, βi = ho0 (h1 (A)), o0 (Bi è h1 (A)B ∼ A. Î÷åâèäíî, ÷òî R(A) íåïóñòîäëÿ âñåõ A ∈ WN1 . ßñíî, ÷òî åñëè hα, β) ∈ R(A), òî o0 (A) = α + β .00Ñëåäîâàòåëüíî äëÿ ëþáûõ A, A0 ∈ WN1 , åñëè A 6= A , òî R(A) ∩ R(A ) = ∅.590Êðîìå òîãî îòñþäà äëÿ A, A0 ∈ WN1 , hα, β) ∈ R(A) è hγ, δ) ∈ R(A )ðàâåíñòâî A = A0 ýêâèâàëåíòíî òîìó, ÷òî α + β = γ + δ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
