Диссертация (1104034), страница 11
Текст из файла (страница 11)
Òåì ñàìûì çàäàíîñåìåéñòâî, ïðîèíäåêñèðîâàííîå A ∈ WNα , ìîäåëåé IA òîé æå ñèãíàòóðû,÷òî è ìîäåëè èç L2n . Ïîêàæåì, ÷òî äëÿ âñÿêîé ìîäåëè (B, L1 , L2 ) ∈ L2níàéäåòñÿ A ∈ WNα òàêîå, ÷òî IA èçîìîðôíà (B; L1 , L2 ). Ïîëîæèì k = |B|.Îáîçíà÷èì ýëåìåíòû B â ñîîòâåòñòâèå ñ ïîðÿäêîì L1 :b1 L1 b2 L1 . .
. L1 bk .Äëÿ âñåõ i îò 1 äî k ïîëîæèì si ðàâíûì ìîùíîñòè ìíîæåñòâà{d ∈ B | d L2 bi }.  ñèëó ëåììû 3.2, íàéäåòñÿ òàêîå A, ÷òîu(A)= (Kk,s1 +1 , Kk,s2 +1 , . . . , Kk,sk +1 ). Íåñëîæíî âèäåòü, ÷òî IA èçîìîðôíà(B; L1 , L2 ). Òåì ñàìûì, ìû ïîñòðîèëè òðåáóåìóþ èíòåðïðåòàöèþ.Èñïîëüçóÿ òåîðåìó 5, ìû ïîëó÷àåìÑëåäñòâèå 3.4.Òåîðèÿ Th(WNω ; <0 , >, d0 , . .
. , dk , . . .) íåðàçðåøèìà. Äëÿêàæäîãî n ≥ 3 òåîðèÿ Th(WNn ; <0 , >, d0 , . . . , dn ) íåðàçðåøèìà.3.2Íåêîòîðûå òåîðèè îðäèíàëîâ è ñëîâÌû ïåðåõîäèì ê äîêàçàòåëüñòâó ðàçðåøèìîñòè ýëåìåíòàðíûõ òåîðèéTh(WNα ; <0 , >, h0i, h1i, h2i) äëÿ α ∈ [2, ω).
Äëÿ òàêèõ α ìû ïîñòðîèìèíòåðïðåòàöèè ýëåìåíòàðíîé òåîðèè Th(WNα ; <0 , >, h0i, h1i, h2i) â ðàçðåøèìîé ñëàáîé ìîíàäè÷åñêîé òåîðèè ìîäåëè (ωα ; R) [13]; çäåñü R ýòîñïåöèàëüíîå áèíàðíîå îòíîøåíèå, îïðåäåëÿåìîå ÷åðåç êîôèíàëüíûå ïîñëåäîâàòåëüíîñòè. Äëÿ ýòîãî ìû ïðè âñåõ α ∈ [2, ω) ïîñòðîèì öåïî÷êóèíòåðïðåòàöèé ìîäåëåé:1. Ìû ñòðîèì â ëåììå 3.9 èíòåðïðåòàöèþ (WNα ; <0 , >, h0i, h1i, h2i) â(ωα ; <, ψ)+ . Ìîäåëü (ωα ; <, ψ)+ ñîñòîèò èç îðäèíàëîâ ìåíüøèõ ωα ,êîíå÷íûõ ìóëüòèìíîæåñòâ îðäèíàëîâ, ñòàíäàðòíîãî ïîðÿäêà íà îðäèíàëàõ, ñïåöèàëüíîé ôóíêöèè ψ íà îðäèíàëàõ è íåêîòîðûõ åñòåñòâåííûõ ïðåäèêàòîâ äëÿ ðàáîòû ñ ìóëüòèìíîæåñòâàìè.2.  ëåììå 3.10 ìû ñòðîè èíòåðïðåòàöèÿ (ωα ; <, ψ)+ â (ωα ; <, ψ)0 .673.
Ìû ñòðîèì â ëåììå 3.12 èíòåðïðåòàöèþ (ωα ; <, ψ)0 â (ωα ; R)0 . Áèíàðíîå îòíîøåíèå R ýòî îòíîøåíèå îïðåäåëÿåìîå íà îñíîâå ñòàíäàðòíîé ñèñòåìû êîôèíàëüíûõ ïîñëåäîâàòåëüíîñòåé.Ìû íàçûâàåì êîíå÷íûì ìóëüòèìíîæåñòâîì ôóíêöèþ f òàêóþ, ÷òî åå îáëàñòü îïðåäåëåíèÿ dom(f ) êîíå÷íà è åå îáëàñòü çíà÷åíèé ran(f ) âëîæåíà â [1, ω). Êîíå÷íîå ìóëüòèìíîæåñòâî f âëîæåíî âêîíå÷íîå ìóëüòèìíîæåñòâî g , åñëè dom(f ) ⊂ dom(g) è äëÿ âñÿêîãîx ∈ dom(f ) èìååò ìåñòî f (x) ≤ g(x); ìû îáîçíà÷àåì ýòî f ⊂M g . Îïðåäåëèì if (x) êðàòíîñòü âõîæäåíèÿ x â êîíå÷íîå ìóëüòèìíîæåñòâî f .Åñëè x ∈ dom(f ), òî if (x) = f (x).
Èíà÷å, if (x) = 0. Äëÿ âñÿêîãî x èìóëüòèìíîæåñòâà f ìû îïðåäåëÿåìdefx ∈M f ⇐⇒ if (x) > 0.Äëÿ âñÿêîãî ìíîæåñòâà A ìû îáîçíà÷àåì ÷åðåç M<ω (A) ìíîæåñòâî âñåõêîíå÷íûõ ìóëüòèìíîæåñòâ, êîòîðûì ïðèíàäëåæàò ëèøü ýëåìåíòû A.Ìû îáîçíà÷àåì ÷åðåç {a1 , . . . , an }M ìóëüòèìíîæåñòâî f (x) òàêîå, ÷òîdom(f ) = {a1 , . .
. , an } è äëÿ âñÿêîãî x ∈ dom(f ) çíà÷åíèå f (x) ðàâíîìîùíîñòè ìíîæåñòâà {i | x = ai }.Ðàññìîòðèì îäíîñîðòíóþ ìîäåëü A ñ íîñèòåëåì A. Îïðåäåëèìäâóñîðòíóþ ìîäåëü A+ . Ìîäåëü A+ ÿâëÿåòñÿ ðàñøèðåíèåì A äîïîëíèòåëüíîé ïðåäìåòíîé îáëàñòüþ M<ω (A), ïðåäèêàòîì ∈M , îãðàíè÷åííûìíà A ×M<ω (A) è ïðåäèêàòîì ⊂M , îãðàíè÷åííûì íà M<ω (A)×M<ω (A).Íàïîìíèì, ÷òî ìû èñïîëüçóåì îïðåäåëåíèå îðäèíàëîâ ïî ôîíÍåéìàíó è ñîîòâåòñòâåííîα = {β ∈ On | β < α}.Äàëåå ìû äîêàæåì íåñêîëüêî ëåìì îá îïðåäåëèìîñòè íåêîòîðûõ åñòåñòâåííûõ ïðåäèêàòîâ è ôóíêöèé â ìîäåëÿõ (α; <), (α; <)0 è (α; <)+ , ãäåα ýòî îðäèíàë.
Çàìåòèì, ÷òî âñå ìíîæåñòâà, ïðåäèêàòû è ôóíêöèèîïðåäåëèìûå â (α; <) òàêæå îïðåäåëèìû â (α; <)0 è (α; <)+ .68Ëåììà 3.5.Ïóñòü äàí ïðåäåëüíûé îðäèíàë α > 0. Òîãäà â ìîäåëè(α; <) îïðåäåëèìû:1. ôóíêöèÿ S : On → On, S : β 7−→ β + 1, îãðàíè÷åííàÿ íà α;2. ýëåìåíò 0;3. ïðåäèêàò x ∈ Lim, ãäå Lim êëàññ âñåõ îòëè÷íûõ îò 0 íåïîñëåäîâàòåëüíûõ îðäèíàëîâ;4. îãðàíè÷åííîå íà α îòíîøåíèå ýêâèâàëåíòíîñòè FinDif(x, y), ãäådefFinDif(β, γ) ⇐⇒ ∃n ∈ ω(β + n = γ ∨ β = γ + n).Äîêàçàòåëüñòâî. Äëÿ âñÿêèõ β, γ ∈ α èìåþò ìåñòî ñëåäóþùèå ýêâèâàëåíòíîñòè:1.
S(β) = γ ⇐⇒ β < γ ∧ ∀δ ∈ α(γ ≤ δ ∨ δ ≤ β);2. β = 0 ⇐⇒ ∀δ ∈ α(β ≤ δ);3. β ∈ Lim ⇐⇒ β 6= 0 ∧ ∀γ ∈ α(β 6= S(γ));4. FinDif(β, γ) ⇐⇒ (β < γ ∧ ∀δ ∈ α(β < δ ≤ γ → δ 6∈ Lim))∨(γ < β ∧ ∀δ ∈ α(γ < δ ≤ β → δ 6∈ Lim))∨β = γ.Ýòè ýêâèâàëåíòíîñòè ïîêàçûâàþò îïðåäåëèìîñòü òðåáóåìûõôóíêöèé, ýëåìåíòîâ è ïðåäèêàòîâ.Ëåììà 3.6.Ïóñòü α ∈ On.
Òîãäà â ìîäåëè (α; <)0 âûðàçèìà ôóíêöèÿmin : P <ω (α) \ {∅} → αè â ìîäåëè (α; <)+ âûðàçèìà ôóíêöèÿmin : M<ω (α) \ {∅M } → α.Äîêàçàòåëüñòâî. Äëÿ âñÿêîãî Q ∈ P <ω (α) \ ∅ è β ∈ α èìååò ìåñòîýêâèâàëåíòíîñòümin(Q) = β ⇐⇒ β ∈ Q ∧ ∀γ ∈ α(γ < β → γ 6∈ Q).Çàìåòèì, ÷òî òåì ñàìûì ìû ïîñòðîèëè èñêîìîå îïðåäåëåíèå äëÿ (α; <)0 .Äëÿ ìîäåëè (α; <)+ äîêàçàòåëüñòâî àíàëîãè÷íî.69Ëåììà 3.7.Ïóñòü A ìîäåëü ñ îäíèì óíèâåðñóìîì A. Òîãäà â ìîäåëèA+ âûðàçèìû1. ïðåäèêàòCLess(x, X, Y),âûïîëíÿþùèéñÿíàâñÿêîéòðîéêå(a, Q1 , Q2 ) ∈ A × M<ω (A) × M<ω (A) òîãäà è òîëüêî òîãäà, êîãäàêðàòíîñòü âõîæäåíèÿ a â Q1 ìåíüøå êðàòíîñòè âõîæäåíèÿ a âQ2 ;2. ïðåäèêàòCEq(x, X, Y),âûïîëíÿþùèéñÿíàâñÿêîéòðîéêå(a, Q1 , Q2 ) ∈ A × M<ω (A) × M<ω (A) òîãäà è òîëüêî òîãäà,êîãäà êðàòíîñòü âõîæäåíèÿ a â Q1 ðàâíà êðàòíîñòè âõîæäåíèÿa â Q2 ;3.
ïðåäèêàòCS(x, X, Y),âûïîëíÿþùèéñÿíàâñÿêîéòðîéêå(a, S1 , S2 ) ∈ A × M<ω (A) × M<ω (A) òîãäà è òîëüêî òîãäà, êîãäàêðàòíîñòü âõîæäåíèÿ a â Q1 ìåíüøå êðàòíîñòè âõîæäåíèÿ a âQ2 ðîâíî íà 1;Äîêàçàòåëüñòâî. Äëÿ âñåõ òðîåê (a, Q1 , Q2 ) ∈ A × M<ω (A) × M<ω (A)î÷åâèäíî èìåþò ìåñòî ñëåäóþùèå ýêâèâàëåíòíîñòè:1. CLess(a, Q1 , Q2 ) ⇐⇒ ∃Q3 ∈ M<ω (A)(∀b ∈ A(b ∈M Q3 ↔ a = b)∧Q3 ⊂M Q2 ∧ ¬Q3 ⊂M Q1 );2. CEq(a, Q1 , Q2 ) ⇐⇒ ¬CLess(a, Q1 , Q2 ) ∧ ¬CLess(a, Q2 , Q1 );3. CS(a, Q1 ,Q2 ) ⇐⇒ CLess(a, Q1 , Q2 )∧∀Q3 ∈ M<ω (A)(¬(CLess(a, Q3 , Q2 ) ∧ CLess(a, Q1 , Q3 ))).Îòñþäà ñëåäóåò âûðàçèìîñòü ïðåäèêàòîâ èç óñëîâèÿ ëåììû.Îïðåäåëèì ôóíêöèþ ψ : On → On:1.
ψ(0) = ω ;2. ψ(ω α1 + ω α2 + · · · + ω αn ) = ω α1 + ω α2 + · · · + ω αn−1 + ω αn +1 , ãäå n ≥ 1è α1 ≥ α2 ≥ . . . ≥ αn .Ìû íàçûâàåì îðäèíàë α çàìêíóòûì îòíîñèòåëüíî ôóíêöèè ψ ,åñëè äëÿ âñÿêîãî β < α ìû èìååì ψ(β) < α.Íåñëîæíî âèäåòü,÷òî èìååì ìåñòî ñëåäóþùàÿ ëåììà.70Ëåììà 3.8.Îðäèíàë α çàìêíóò îòíîñèòåëüíî ψ òîãäà è òîëüêî òî-ãäà, êîãäà ëèáî α = 0, ëèáî α = ω ω·β äëÿ íåêîòîðîãî β > 0.Ëåììà 3.9.Ïóñòü α îðäèíàë îò 2 äî ω . Òîãäà â ìîäåëè (ωα ; <, ψ)+èíòåðïðåòèðóåòñÿ ìîäåëü (WNα ; <0 , >, h0i, h1i, h2i).Äîêàçàòåëüñòâî.
Ïåðåä ïîñòðîåíèåì èíòåðïðåòàöèè îòìåòèì äâà ôàêòà. Â ñèëó ëåììû 3.8, îðäèíàë ωα çàìêíóò îòíîñèòåëüíî ψ . Ôóíêöèÿ o1ÿâëÿåòñÿ áèåêöèåé ìåæäó ìíîæåñòâàìè WNα ∩ S 1 è ωα .Ðàññìîòðèì ñëîâî A ∈ WNα è îïðåäåëèì åãî èíòåðïðåòàöèþ ìóëüòèìíîæåñòâî AI . Ñëîâî A åäèíñòâåííûì îáðàçîì ïðåäñòàâëÿåòñÿ ââèäå A1 0 . . .
0An äëÿ íåêîòîðûõ n ≥ 0 è A1 , . . . , An ∈ WNα ∩ S1 . ÏîëîæèìAI = {A1 , . . . , An }M .Íåñëîæíî âèäåòü, ÷òî îïðåäåëåííîå òåì ñàìûì îòîáðàæåíèå A 7→ AI<ωÿâëÿåòñÿ áèåêöèåé ìåæäó WNα è M (ωα ).Îïðåäåëèì èíòåðïðåòàöèþ ïðåäèêàòà <0 ïðåäèêàò <I0 :X <I0 Y ∃x(CLess(x, X, Y) ∧ ∀y > x(CEq(y, X, Y))).Äîêàæåì, ÷òî <I0 äåéñòâèòåëüíî ÿâëÿåòñÿ èíòåðïðåòàöèåé <0 .Ïîêàæåì, ÷òî äëÿ âñÿêèõ A, B ∈ WNα ìû èìååìA <0 B ⇐⇒ AI <I0 BI .Ìû íàõîäèì A1 , . . . , An , B1 , .
. . , Bm ∈ S1 òàêèå, ÷òî A ðàâíî A1 0A2 0 . . . 0Anè B ðàâíî B1 0B2 0 . . . 0Bm . Ìû îáîçíà÷àåì ÷åðåç A ìóëüòèìíîæåñòâî AIè îáîçíà÷èì ÷åðåç B ìóëüòèìíîæåñòâî BI . Ïîêàæåì, ÷òîA1 0A2 0 . . . 0An <0 B1 0B2 0 . . . 0Bm ⇐⇒ (ωα ; <, ψ)+ |= A <I0 B.Ïóñòü èìååò ìåñòî(ωα ; <, ψ)+ |= A <I0 B.Ïîêàæåì, ÷òî A1 0A2 0 . . . 0An <0 B1 0B2 0 . . . 0Bm . Òîãäà íàéäåòñÿ îðäèíàëγ òàêîé, ÷òî êðàòíîñòü âõîæäåíèÿ γ â A ìåíüøå êðàòíîñòè âõîæäåíèÿ71γ â B è äëÿ âñÿêèõ δ èç èíòåðâàëà (γ, ωα ) êðàòíîñòè âõîæäåíèÿ δ âA è B ñîâïàäàþò.
Ïóñòü êðàòíîñòü âõîæäåíèÿ γ â A ðàâíà l, à êðàòíîñòü âõîæäåíèÿ γ â B ðàâíà e. Ïóñòü k ÿâëÿåòñÿ (e − l)-ûì, â ñìûñëå ñòàíäàðòíîãî ïîðÿäêà íà íàòóðàëüíûõ ÷èñëàõ, ýëåìåíòîì ìíîæåñòâà{i | o1 (Bi ) = γ}; çàìåòèì, ÷òî â ñèëó îïðåäåëåíèÿ <I0 òàêîå k íàéäåòñÿ.Íåñëîæíî âèäåòü, ÷òî äëÿ i îò 0 äî m − k − 1 ìû èìååì An−i = Bm−i .Ïðèòîì, ëèáî n = m − k − 1, ëèáî An−(m−k) <0 Bk . Îòìåòèì, ÷òî ñèëó îïðåäåëåíèÿ NF, ïðè âñåõ j îò 1 äî n − (m − k) ìû òàêæå èìååìAj <0 Bk . Òåì ñàìûì, èñïîëüçóÿ îïðåäåëåíèå o0 , ìû óñòàíàâëèâàåì, ÷òîA1 0 .
. . 0An <0 B1 0 . . . 0Bm .Òåïåðü ïðåäïîëîæèì, ÷òî A1 0 . . . 0An <0 B1 0 . . . 0Bm è ïîêàæåì,÷òî (ωα ; <, ψ)+ |= A <I0 B. Íåñëîæíî âèäåòü, ÷òî íàéäåòñÿ l < m òàêîå,÷òî äëÿ âñåõ i îò 0 äî l − 1 ìû èìååì An−i = Bm−i è ïðèòîì ëèáî n = l,ëèáî An−l <0 Bm−l . Èç ïîñëåäíåãî ñëåäóåò, ÷òî äëÿ âñåõ i îò l äî n − 1 ìûèìååì Ai <0 Bm−l , à òåì ñàìûì è o1 (Ai ) < o1 (Bm−l ).  êà÷åñòâå èñêîìîãîx èç îïðåäåëåíèÿ <I0 âûáåðåì o1 (Bm−l ) è ïîëó÷èì (ωα ; <)+ |= A <I0 B.Òåì ñàìûì, <I0 ÿâëÿåòñÿ èíòåðïðåòàöèåé <0 .Ôóíêöèÿ h0i è êîíñòàíòà > îïðåäåëèìû â (WNα ; <0 ) è òåì ñàìûììîãóò áûòü ïðîïóùåíû ïðè ïîñòðîåíèå èñêîìîé èíòåðïðåòàöèè.Çàìåòèì, ÷òî äëÿ âñÿêîãî A ∈ NF ∩ S1 èìååò ìåñòî òîæäåñòâîψ(o1 (A)) = o1 (h2iA).Îïðåäåëèì ôóíêöèè h1iI è h2iI èíòåðïðåòàöèè ôóíêöèé h1i èh2i:h1iI X = Y (X = ∅M → Y = {1}M ) ∧ (X 6= ∅M →∀x > S(min(X))(CEq(x, X, Y))∧CS(S(min(X)), X, Y)∧∀x < S(min(X))(¬x ∈M Y)),72h2iI X = Y (X = ∅M → Y = {ω}M ) ∧ (X 6= ∅M →∀x > ψ(min(X))(CEq(x, X, Y))∧CS(ψ(min(X)), X, Y)∧∀x < ψ(min(X))(¬x ∈M Y)).Ëåãêî âèäåòü, ÷òî ýòè îïðåäåëåíèÿ h1iI è h2iI ìîãóò áûòü âûðàæåíûïåðâîïîðÿäêîâûìè ôîðìóëàìè â ñòðóêòóðå (ωα ; <, ψ)+ .
Ïîêàæåì êîððåêòíîñòü îïðåäåëåíèÿ èíòåðïðåòàöèè h2i, êîððåêòíîñòü îïðåäåëåíèÿèíòåðïðåòàöèè h1i äîêàçûâàåòñÿ àíàëîãè÷íî. Ðàññìîòðèì ïðîèçâîëüíîåNñëîâî A ∈ WNα , èìåþùåå âèä A1 0 . . . 0An , ãäå A1 , . . . , An ∈ Wα ∩ S1 . Âñèëó àëãîðèòìà ïðèâåäåíèÿ ñëîâ ê íîðìàëüíîé ôîðìå (ñì. ðàçäåë 2.1)íîðìàëüíîé ôîðìîé d2 (A) ÿâëÿåòñÿ ñëîâ 2A1 0Ak 0Ak+1 0 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
