Диссертация (1104034), страница 10
Текст из файла (страница 10)
Èñïîëüçóÿïðåäëîæåíèå 2.1 ìû ïîëó÷àåì, ÷òî äëÿ hα, β) ∈ ω ω ×ω ω , ïðèíàäëåæíîñòüíåêîòîðîìó R(A) ýêâèâàëåíòíà òîìó, ÷òî α ∈ {0} ∪ {ω x | 1 ≤ x < ω}è β ïîñëåäîâàòåëüíûé îðäèíàë < ω ω èëè 0; òåì ñàìûì ýòî ñâîéñòâîâûðàçèìî â Th(ω ω ; <, +).Èíòåðïðåòàöèåé AI ñëîâà A ∈ WN1 ìû ñ÷èòàåì ïàðó hα, β) ∈ R(A)òàêóþ, ÷òî äëÿ ëþáûõ hα0 , β 0 ) ∈ R(A) ìû èìååì β 0 ≥ β (íàïîìíèì, ÷òîçäåñü α âñåãäà ðàâåí α0 ). Î÷åâèäíî, ó÷èòûâàÿ äîêàçàííîå â ïðåäûäóùåìωàáçàöå, ÷òî ìíîæåñòâî âñåõ ïàð {AI | A ∈ WN1 } îïðåäåëèìî â (ω ; <, +).Èç ëåììû 2.4 è ñëåäñòâèÿ 2.6 ñëåäóåò, ÷òî åñëè hα, β) ∈ R(A) è hγ, δ) ∈R(B), òî (maxhα, γ), max(β, δ)) ∈ R(A u B).
Òåì ñàìûì èíòåðïðåòàöèÿuI ôóíêöèè u âûðàçèìà.60Ãëàâà 3Ýëåìåíòàðíûå òåîðèè ñèñòåìûîðäèíàëüíûõ îáîçíà÷åíèéÁåêëåìèøåâà è åå ôðàãìåíòîâ3.1Ñèñòåìû îðäèíàëüíûõ îáîçíà÷åíèé ñ íåðàçðåøèìûìè ýëåìåíòàðíûìè òåîðèÿìè ýòîì ðàçäåëå ìû ïîêàæåì, ÷òî1. òåîðèÿ Th(WNω ; <0 , d0 , . . . , dk , . . .) íåðàçðåøèìà;2.
äëÿ âñÿêîãî ÷èñëà n ≥ 3 òåîðèÿ Th(WNn ; <0 , d0 , . . . , dn ) íåðàçðåøèìà.Äëÿ ýòîãî ìû ïîêàæåì, ÷òî äëÿ âñÿêèõ íàòóðàëüíûõ p, q è îðäèíàëà αòàêèõ, ÷òî 0 < p < q ≤ α ≤ ω òåîðèÿ (WNα ; <0 , dp , dq ) íåðàçðåøèìà. Êàêáûëî ïîêàçàíî È.À. Ëàâðîâûì, ýëåìåíòàðíàÿ òåîðèÿ Th(L2n ) âñåõ êîíå÷íûõ ìíîæåñòâ, ñíàáæåííûõ ïàðîé ëèíåéíûõ ïîðÿäêîâ íàñëåäñòâåííîíåðàçðåøèìà [5]. Ìû ïîêàçûâàåì, ÷òî èìååòñÿ ïðàâàÿ òîòàëüíàÿ èíòåðïðåòàöèÿ (ìû îïðåäåëÿåì ýòî ïîíÿòèå äàëåå â ýòîì ðàçäåëå) Th(L2n ) âTh(WNα ; <0 , dp , dq ), ÷òî äàåò íàì íåðàçðåøèìîñòü ïîñëåäíåé òåîðèè.Ïîä îïðåäåëèìîñòüþ íèæå ìû ïîäðàçóìåâàåì îïðåäåëèìîñòüôîðìóëàìè ïåðâîãî ïîðÿäêà.NÏóñòü ñëîâà A ∈ WN3 \ {>} è B ∈ W3 \ {>} òàêîâû, ÷òî A =C1 0C2 0 .
. . 0Cn , B = Cm 0Cm+1 0 . . . 0Cn äëÿ íåêîòîðûõ n ≥ 1 è 1 ≤ m ≤ n,Ci ∈ S1 .  òàêîì ñëó÷àå ìû áóäåì ãîâîðèòü, ÷òî B ÿâëÿåòñÿ ñðåçîì A.61Äëÿ êàæäîãî p ≥ 1 îáîçíà÷èì ÷åðåç Up ìíîæåñòâî âñåõ ñëîâA1 0A2 0 . . . 0An , ãäå âñå Ai ∈ Sp .Ëåììà 3.1.Ïóñòü α îðäèíàë, p íàòóðàëüíîå ÷èñëî è 0 < p ≤α ≤ ω . Òîãäà èìååòñÿ ïåðâîïîðÿäêîâàÿ ôîðìóëà Slp (x, y) ÿçûêà ìîäåëèNN(WNα ; <0 , dp ) òàêàÿ, ÷òî äëÿ âñåõ A ∈ Up ∩ Wα è B ∈ Wα ñëîâî B ÿâëÿ-åòñÿ ñðåçîì A òîãäà è òîëüêî òîãäà, êîãäà â (WNα ; <0 , dp ) âûïîëíÿåòñÿSlp (A, B).Äîêàçàòåëüñòâî. ÏîëîæèìSlp (x, y) x 6= > ∧ y 6= > ∧ y ≤0 x ∧ x <0 dp (y).(3.1)NÐàññìîòðèì ïðîèçâîëüíûå A ∈ Up ∩ WNα è B ∈ Wα . Ïóñòü ÷èñëàNn, m, ñëîâà A1 , .
. . , An ∈ Sp ∩ WNα è ñëîâà B1 , . . . , Bm ∈ S1 ∩ Wα òàêîâû,÷òî A = A1 0A2 0 . . . 0An , à B = B1 0B2 0 . . . 0Bm .Ïðåäïîëîæèì, ÷òî B ÿâëÿåòñÿ ñðåçîì A è äîêàæåì, ÷òî Slp (A, B)èìååò ìåñòî â ðàññìàòðèâàåìîé ìîäåëè. Èç ïðåäïîëîæåíèÿ íåïîñðåäñòâåííî ñëåäóåò, ÷òî A 6= >, B 6= > è B ≤0 A. Êðîìå òîãî, â ñèëóïðåäïîëîæåíèÿ, m ≤ n è Bm−i = An−i ïðè âñåõ i îò 0 äî m − 1. Òàêæåíåñëîæíî âèäåòü, ÷òî äëÿ âñåõ i îò 1 äî n − m − 1 ìû èìååì Ai <1 hpiB1 .Îòñþäàω o1 (An−m+1 ) + ω o1 (An−m ) + · · · + ω o1 (A1 ) < ω o1 (hpiB1 ) .Òåì ñàìûì, o0 (A) < o0 (hpiB) è ñëåäîâàòåëüíî A <0 dp (B).Òåïåðü ïðåäïîëîæèì, ÷òî Slp (A, B) èìååò ìåñòî â ðàññìàòðèâàåìîé ìîäåëè è äîêàæåì, ÷òî B ÿâëÿåòñÿ ñðåçîì A.
Åñëè A = B, òî òðåáóåìîå î÷åâèäíî è ïîýòîìó áåç îãðàíè÷åíèÿ îáùíîñòè ìû ïðåäïîëàãàåì,÷òî B <0 A. Ðàññìîòðèì íàèáîëüøåå íàòóðàëüíîå ÷èñëî l îò 1 äî n + 1òàêîå, ÷òî Al 0Al+1 0 . . . 0An ≥0 B. Î÷åâèäíî, ÷òî l 6= n + 1. Îáîçíà÷èìAl 0Al+1 0 . . . 0An ÷åðåç A0 .Ðàññìîòðèì ñëó÷àé Al ≤0 B1 .
Ìû èìååìo0 (Al+1 0 . . . 0An ) + ω o1 (Al ) ≥ o0 (A0 ) ≥ o0 (B) = o0 (B2 0 . . . 0Bm ) + ω o1 (B1 ) .62Òàê êàê ω o1 (Al ) ≤ ω o1 (B1 ) ìû èìååì ëèáîo0 (Al+1 0 . . . 0An ) + ω o1 (Al ) = o0 (B2 0 . . . 0Bm ) + ω o1 (B1 )è ω o1 (Al ) = ω o1 (B1 ) , ëèáîo0 (Al+1 0 . . . 0An ) ≥ o0 (B2 0 . . . 0Bm ) + ω o1 (B1 ) .Ïîñëåäíåå ïðîòèâîðå÷èò ìèíèìàëüíîñòè l. Îòñþäà o0 (B) = o0 (A0 ) è òåìñàìûì B = A0 è B ÿâëÿåòñÿ ñðåçîì A.Òåïåðü ðàññìîòðèì ñëó÷àé B1 <0 Al è ïîêàæåì, ÷òî îí íåâîçìîæåí.  ýòîì ñëó÷àåhp (B) = hp (B1 ) ≤0 B1 <0 Al = hp (A0 ).Òàê êàê hp (B1 ) <0 Al , ìû èìååì hp (B1 ) <p Al è ñîîòâåòñòâåííîhpihp (B1 ) ≤p Al .
Òåì ñàìûì ïî ëåììå 2.5 GLP ` Al → hpihp (B1 ). Ïóñòü Còàêîâî, ÷òî B1 = hp (B)C. Îòìåòèì, ÷òî t(C) < p. Òàê êàê GLP ` B1 → Cìû ïîëó÷àåì C <0 Al è â ñèëó ñëåäñòâèÿ 2.7 ìû ïîëó÷àåì GLP ` Al → C.Çàìåòèì, ÷òî 0B2 0 . . . 0Bm ≤0 A0 è, â ñèëó òîãî, ÷òî t(A0 ) = t(Al ) 6= 0 ìûèìååì 0B2 0 . . . 0Bm 6= A0 . Òåì ñàìûì, 0B2 0 . . .
0Bm <0 A0 è ñ ïîìîùüþëåììû 2.5 ìû ïîëó÷àåì GLP ` A0 → 0B2 0 . . . 0Bm . Ïîýòîìó,dp (B) ∼ hpihp (B) ∧ C ∧ 0B2 0 . . . 0Bm .Òàêèì îáðàçîì GLP ` A0 → dp (B). Îòñþäà, åñëè áû A0 <0 dp (B), òî ìûáû èìåëè A0 <0 A0 , ÷òî ïðîòèâîðå÷èò èððåôëåêñèâíîñòè <0 .Ôèêñèðóåì íåêîòîðûå íàòóðàëüíûå ÷èñëà p,r è q òàêèå, ÷òî 0 <p < r < q.
Îáîçíà÷èì ÷åðåç Is ñëîâî rqs äëÿ s ≥ 0. Äëÿ íàòóðàëüíûõ÷èñåë k è c òàêèõ, ÷òî 1 ≤ k ≤ c îáîçíà÷èì ÷åðåç Kc,k ñëîâî qk Ik Ik+1 . . . Ic−1è ÷åðåç Lc ñëîâî I1 . . . Ic−1 . Îòìåòèì, ÷òî äëÿ âñåõ òàêèõ k è c, ÷òî 1 ≤k ≤ c ìû èìååìqk−1 Ik . . . Ic−1 ≤0 Lc <0 qk Ik . . . Ic−1 = Kc,k .63Òàêæå îòìåòèì, ÷òîKc,1 <0 Kc,2 <0 . .
. <0 Kc,c .Ïóñòü ñëîâî A∈NF èìååò âèä A1 0A2 0 . . . 0Ae , ãäå âñå AiS1 . Ñîïîñòàâèì ñëîâó A êîíå÷íóþ ïîñëåäîâàòåëüíîñòü ñëîâu(A)∈=(u1 (A), . . . , ue (A)), ãäå äëÿ âñÿêîãî i ∈ {1, . . . , e} ìû ïîëàãàåì ui (A) =dq (Ai 0Ai+1 0 . . . 0Ae ).Ëåììà 3.2.Ïóñòü äàíû íàòóðàëüíûå ÷èñëà c ≥ 1, e è íàáîð íåíóëåâûõíàòóðàëüíûõ ÷èñåë k1 , . . . , ke ≤ c. Òîãäà íàéäåòñÿ A ∈ WNq òàêîå, ÷òîïîñëåäîâàòåëüíîñòü u(A) ðàâíà ïîñëåäîâàòåëüíîñòè Kc,k1 , . . . , Kc,ke .Äîêàçàòåëüñòâî. Ïðè i îò 1 äî e îáîçíà÷èì ÷åðåç Ci ñëîâî qki −1 Iki . .
. Ic−1 .Ïîëîæèì:A = C1 (pLc )0 0 . . . 0Ce−1 (pLc )e−2 0Ce (pLc )e−1 .Ðàññìîòðèì íåêîòîðîå i îò 1 äî e. Ñëîâî ui (A) ðàâíî íîðìàëüíîé ôîðìå ñëîâà qCi (pLc )i−1 0 . . . 0Ce−1 (pLc )e−2 0Ce (pLc )e−1 . Òàê êàê Lc <0 Kc,ki èKc,ki = qCi ìû èñïîëüçóÿ àëãîðèòì ïðèâåäåíèÿ ê íîðìàëüíîé ôîðìå ïîëó÷àåì, ÷òî íîðìàëüíàÿ ôîðìà qi (pLc )i−1 ðàâíà Kc,ki . Òàê êàê äëÿ âñåõ jîò i + 1 äî e ìû èìååì Lc <r Kc,ki è Cj <r Kc,ki , èñïîëüçóÿ îïðåäåëåíèå opìû ïîëó÷àåì Cj (pLc )j−1 <p Kc,ki . Òåì ñàìûì, íîðìàëüíàÿ ôîðìà ñëîâàqCi (pLc )i−1 0 . .
. 0Ce−1 (pLc )e−2 0Ce (pLc )e−1ðàâíà Kc,ki . Ñëåäîâàòåëüíî, u(A) èìååò òðåáóåìûé âèä.Ïðàâûå òîòàëüíûå èíòåðïðåòàöèè.Îäèí èç ìåòîäîâ äîêàçàòåëüñòâà íåðàçðåøèìîñòè òåîðèé îñíîâàí íàïðàâûõ òîòàëüíûõ èíòåðïðåòàöèÿõ (ñì. [4, ãëàâà 5, 1], ãäå ýòîò ìåòîäíàçûâàåòñÿ ìåòîäîì îòíîñèòåëüíî ýëåìåíòàðíîé îïðåäåëèìîñòè). Íèæåìû äàäèì îïðåäåëåíèå ïîíÿòèÿ ïðàâîé òîòàëüíîé èíòåðïðåòàöèè. Äëÿóïðîùåíèÿ òåõíè÷åñêèõ ìîìåíòîâ ìû äàåì åãî òîëüêî äëÿ ñëó÷àÿ ñèãíàòóðû èíòåðïðåòèðóåìîé òåîðèè áåç ôóíêöèîíàëüíûõ ñèìâîëîâ è àáñîëþòíîé èíòåðïðåòàöèè ðàâåíñòâà.64Ïóñòü äàíû òåîðèÿ T1 ñèãíàòóðû σ1 è òåîðèÿ T2 ñèãíàòóðû σ2áåç ôóíêöèîíàëüíûõ ñèìâîëîâ. Ïóñòü äàíà èíòåðïðåòàöèÿ Γ ñèãíàòóðûσ2 â σ1 è åé ñîîòâåòñòâóåò ïåðåâîä ôîðìóë trΓ : F 7−→ F? .
Ïðè ýòîì ìûïðåäïîëàãàåì, ÷òî Γ èíòåðïðåòèðóåò ðàâåíñòâà ðàâåíñòâàìè. Ìû íàçûâàåì Γ ïðàâîé òîòàëüíîé èíòåðïðåòàöèåé [21, ãëàâà 5.3], åñëè âñÿêàÿïåðâîïîðÿäêîâàÿ ôîðìóëà A ñèãíàòóðû σ2 òàêîâà, ÷òî åñëè åå ïåðåâîäA? ÿâëÿåòñÿ òåîðåìîé T1 , òî è ñàìà A îêàçûâàåòñÿ òåîðåìîé òåîðèè T2 .Îòìåòèì, ÷òî ýòî îïðåäåëåíèå îòëè÷íî îò îáû÷íîãî ïîíÿòèÿ èíòåðïðåòàöèè, êîòîðîå, â ðàìêàõ òàêîé òåðìèíîëîãèè, ìîæíî íàçûâàòü ëåâîéòîòàëüíîé èíòåðïðåòàöèåé. Ïðàâàÿ òîòàëüíàÿ èíòåðïðåòàöèÿ íàçûâàåòñÿ ýôôåêòèâíîé, åñëè ñîîòâåòñòâóþùèé åé ïåðåâîä ðåêóðñèâåí.
 ñèëóòîãî, ÷òî íàì áóäóò âñòðå÷àòüñÿ òîëüêî ýôôåêòèâíûå ïðàâûå òîòàëüíûå èíòåðïðåòàöèè è èõ ýôôåêòèâíîñòü âñåãäà áóäåò î÷åâèäíà èç èõêîíñòðóêöèè, ìû âñåãäà, íè÷åãî äîïîëíèòåëüíî íå îãîâàðèâàÿ, ïðåäïîëàãàåì ýôôåêòèâíîñòü ïðàâûõ òîòàëüíûõ èíòåðïðåòàöèé.Ïóñòü èìåþòñÿ êëàññû ìîäåëåé A ñèãíàòóðû σ1 è B ñèãíàòóðû σ2 ,à òàêæå èíòåðïðåòàöèÿ Γ ñèãíàòóðû σ2 â ñèãíàòóðå σ1 . Ðàññìîòðèì êëàññìîäåëåé C ñèãíàòóðû σ2 , ÿâëÿþùèéñÿ ñîâîêóïíîñòüþ îáðàçîâ âñåõ ìîäåëåé èç A ïîä äåéñòâèå ïðåîáðàçîâàíèÿ ìîäåëåé, çàäàâàåìîãî Γ. ßñíî,÷òî Γ ÿâëÿåòñÿ ïðàâîé òîòàëüíîé èíòåðïðåòàöèåé Th(A) â Th(B) òîãäàè òîëüêî òîãäà, êîãäà äëÿ êàæäîé ìîäåëè èç B íàéäåòñÿ èçîìîðôíàÿ åéìîäåëü èç C.Òåîðèÿ T íàçûâàåòñÿ íàñëåäñòâåííî íåðàçðåøèìîé, åñëè âñÿêàÿåå ïîäòåîðèÿ íåðàçðåøèìà.Ëåììà 3.3.Åñëè òåîðèÿ T2 íàñëåäñòâåííî íåðàçðåøèìà è èìååòñÿýôôåêòèâíàÿ ïðàâàÿ òîòàëüíàÿ èíòåðïðåòàöèÿ òåîðèè T2 â òåîðèèT1 , òî òåîðèÿ T1 íåðàçðåøèìà.Äîêàçàòåëüñòâî.
Ïóñòü σ1 ñèãíàòóðà òåîðèè T1 , à σ2 ñèãíàòóðà òåîðèèT2 , Γ ÿâëÿåòñÿ ýôôåêòèâíîé ïðàâîé òîòàëüíîé èíòåðïðåòàöèåé T2 â T1 èΓ ñîîòâåòñòâóåò ïåðåâîä trΓ : F 7−→ F? . Äëÿ çàâåðøåíèÿ äîêàçàòåëüñòâà65ïðåäïîëîæèì ïðîòèâíîå è ïðèäåì ê ïðîòèâîðå÷èþ ïðåäïîëîæèì T1ðàçðåøèìà. Ðàññìîòðèì òåîðèþ E ñèãíàòóðû σ2 :A ∈ E ⇐⇒ A? ∈ T1 .Î÷åâèäíî, E â ñàìîì äåëå ÿâëÿåòñÿ òåîðèåé. E ðàçðåøèìà â ñèëó ýôôåêòèâíîñòè trΓ è ðàçðåøèìîñòè T1 . Íî â ñèëó òîãî, ÷òî Γ ÿâëÿåòñÿïðàâîé òîòàëüíîé èíòåðïðåòàöèåé, E ÿâëÿåòñÿ ïîäòåîðèåé T2 è òåì ñàìûì íåðàçðåøèìà ïðîòèâîðå÷èå.Òåîðåìà 5.Åñëè α îðäèíàë ≤ ω , à p è q íàòóðàëüíûå ÷èñëà òàêèå,÷òî 0 < p è p +1 < q < α, òî òåîðèÿ Th(WNα ; <0 , hpi, hqi) íåðàçðåøèìà.Äîêàçàòåëüñòâî.
Ðàññìîòðèì L2n êëàññ âñåõ ìîäåëåé âèäà (B, L1 , L2 ),ãäå B êîíå÷íîå ìíîæåñòâî, à L1 è L2 ñòðîãèå ëèíåéíûå ïîðÿäêè íà íåì.Èçâåñòíî, ÷òî ýëåìåíòàðíàÿ òåîðèÿ êëàññà L2n íàñëåäñòâåííî íåðàçðåøèìà [5].Ïóñòü c êîíñòàíòíûé ñèìâîë. Ðàññìîòðèì ìíîæåñòâî A âñåõìîäåëåé âèäà (WNα ; <0 , hpi, hqi, c), ãäå c îöåíèâàåòñÿ ïðîèçâîëüíûì ñëîNâîì A ∈ WNα . Çàìåòèì, ÷òî òåîðèè Th(A) è Th(Wα ; <0 , hpi, hqi) ðàçðå-øèìû èëè íåðàçðåøèìû îäíîâðåìåííî.  ñàìîì äåëå, èç ðàçðåøèìîñòè ïåðâîé î÷åâèäíî ñëåäóåò ðàçðåøèìîñòü âòîðîé. Åñëè æå ðàçðåøèìàTh(WNα ; <0 , hpi, hqi), òî ñëåäóþùàÿ ýêâèâàëåíòíîñòü äàåò ðàçðåøèìîñòüTh(A):F(c) ∈ Th(A) ⇐⇒ (∀x(F(x))) ∈ Th(WNα ; <0 , hpi, hqi),äëÿ âñåõ ôîðìóë F(x) ñèãíàòóðû ìîäåëè (WNα ; <0 , hpi, hqi).Äàëåå ìû ñòðîèì ïðàâóþ òîòàëüíóþ èíòåðïðåòàöèþ Th(L2n ) âTh(A) è òåì ñàìûì ñ ïîìîùüþ ëåììû 3.3 ïîëó÷àåì èñêîìîå.
Ìû ïîëàãàåì, ÷òî óíèâåðñóì èíòåðïðåòàöèè çàäàåòñÿ ôîðìóëîé Sl(c, x). Ïðåäèêàò x1 L1 x2 èíòåðïðåòèðóåòñÿ ôîðìóëîé x1 <0 x2 , à ïðåäèêàò x1 L2 x2èíòåðïðåòèðóåòñÿ ôîðìóëîé hqix1 <0 hqix2 .Îïðåäåëèì ìîäåëü IA êàê ðåçóëüòàò ïðåîáðàçîâàíèÿ, çàäàâàåìîãî îïðåäåëåííîé âûøå èíòåðïðåòàöèåé, ïðèìåíåííîãî ê ìîäåëè66(WNα ; <0 , hpi, hqi, c) ñ êîíñòàíòîé c îöåíèâàåìîé êàê A.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
