Matematiska Institutionen Uppsala Universitet Anton Setzer

VT 2000 Övning 5

Övningar i Bevisteori

Övning 20 (4 poäng) Visa för systemet (OT, ≺), som har ordningstyp Bachmann-Howard, att (OT, ≺) är linjär.

Övning 21 (6 poäng) Anta (T_{i}, ≺_{i}) är prim. rek. ordningar (i = 0, 1).

(a) Visa TI((T_{0}, ≺_{0}) ◯ ≺ (T_{1}, ≺_{1})) reducerar i { \atop PRA} till TI(T_{0}, ≺_{0}), TI(T_{1}, ≺_{1}) med hänsyn till (k_{0}, k_{1}), där med T := ({0} × T_{0}) ∪ ({1} × T_{1}) k_{i} : T →_{ω} T_{i}, k_{i}(⟨j, a⟩) := {a | i = j}.

(b) Visa TI(Lex((T_{0}, ≺_{0}), (T_{1}, ≺_{1}))) reducerar i { \atop PRA} till TI(T_{0}, ≺_{0}), TI(T_{1}, ≺_{1}) med hänsyn till (k_{0}, k_{1}), där k_{i} : (T_{0} × T_{1}) → T_{i}, k_{i}(⟨a_{0}, a_{1}⟩) = a_{i}.

(c) Visa: Om f : (T_{0}, ≺_{0}) → (T_{1}, ≺_{1}) är ordningstrogen, bevislig i PRA, så reducerar TI(T_{0}, ≺_{0}) i { \atop PRA} till TI(T_{1}, ≺_{1}) med hänsyn till λx.\{f(x)\} : T_{0} →_{ω} T_{1}.

Övning 22 (8 poäng) Utför detaljerna i beviset att för ordinaltalbeteckningssystemet av ordningstyp Bachmann-Howard (OT, ≺) gäller, med α_{0} := 1, α_{n+1} := Ω^{α_{n}}, för varje n: det finns ≺′, k, lh så att (OT ∩ D_{0}(α_{n}), ≺, ≺′, k, lh) är ett ordinalsystem.

Övning 23 (4 poäng) Definiera Acc(T, ≺) utan att använda potensmängden på det följande sättet: Definiera rekursivt a_{α} så att a_{α} = min{a ∈ T | ∀β < α.a_{β} ≺ a_{α}}, om ett sådant a_{α} finns (annars ta det minsta elementet i (T, ≺) om ett sådant finns; vad gör man om det inte finns?). Acc(T, ≺) := {a_{α} | α ∈ Ord}. Visa Acc(T, ≺) = {a_{α} | α < κ}, där κ är ett kardinaltal större än kardinaliteten av T. Alltså är Acc(T, ≺) en mängd. Visa att Acc(T, ≺) är ett välgrundat initialt segment av (T, ≺) och om F är en klass, F ett välgrundat initialt segment av (T, ≺), sår är F ⊆ Acc(T, ≺). (Det blir en definition som kan genomföras i Kripke-Platek mändläran).

Övning 23 (8 poäng) Låt ID_{1}^{O,int} vara begränsning av den intuitionistiska versionen av ID_{1} till bara ett predikat P_{A} så att standardinterpretationen av P_{A} är Kleenes O. Låt CT (Church’s thesis) vara kollektion av axiomen

(∀x.∃y.φ(x, y)) → ∃e.∀x.∃y({e}(x) ≃ y ∧ φ(x, y))

för alla formler φ i språket av ID_{1}^{O,int}. T := ID^{O,int} +CT är föreningen av dessa två axiomsystem. Visa att |T | ≥ |ID_{1}|. Tips: Visa att ID_{1}^{O} bevisar transfinit induktion för varje elementärt ordinalsystem (varför?). Det kan göras genom att simulera Acc(T, ≺) i T för en primitivrekursiv ordning (T, ≺) (varför?). Definiera en formel φ(s, t), så att φ(s, t) omm s är ett delträd av t där “s är delträd av t” är den transitiva avslutningen av relationen “s är omdelbart delträd av t” (enligt Kleenes O). φ(s, t) kan definieras som: det finns en följd, så att första element är t, sista elementet är s och det (i + 1)ta elementet är omedelbart delträd av det ita elementet. Definiera s ⪯^{tree} t omm s = t eller s är ett delträd av t. Definiera x ∈ Acc(T, ≺) omm det finns t i Kleenes O och en partiell-rekursiv funktion f (dvs. ett e, och i det följande är f = {e}), så att det gäller:

• f(t) ≃ x,

• för alla s ⪯^{tree} t är f(s) ↓ ∧f(s) ∈ T,

• för alla s ⪯^{tree} t och a ≺ f(s) så att a ∈ T gäller: det finns ett s′, som är omedelbar delträd av s så att f(s′) ≃ a.

Visa nu att T visar (ID1), (ID2) för P_{A}, där A är en formel så att i standardmodellen gäller I_{A} = Acc(T, ≺).

Övning 24 (4 poäng) Definera i ID_{α} formellt Acc_{α} som i välordningsbeviset för elementära α-ordinal system.

Övning 25 (8 poäng) Definiera en teori ID_{inacc} som har styrka KPI och är konstruerad som teorierna ID_{α}, dvs. så att variabler står för naturliga tal, ID_{inacc} innehåller Z, och så att det vidare finns ett eller flera predikat P_{A}, för några formler A med några axiom, som liknar de av ID_{α}. Tips: Definiera P_{A}, så att det för varje I-OS finns ett A, så att man med hjälp av P_{inacc} kan definiera W för det I-OS som i välordningsbeviset.

Övning 26 (8 poäng) Definiera ett ordinaltalbeteckningssystem av ordningstyp ψ_{Ω_{1}}(ϵ_{I+1}) med hjälp av funktionerna ψ_{κ} som infördes i föreläsningen. Det räcker att visa att detta system är linjärt ordnat. (Ersätter + mot Cantor-normalform. Tillfoger φ_{α}β bara om α > 0 och α, β < φ_{α}β. Tillfoga ψ_{κ}(α) bara om α ∈ C_{κ}(α).

Övning 27 (12 poäng) Låt (T_{n}, ≺_{n}) vara begränsningen av systemet från övning 26 (eller en liten variant) till ordinaltal som är byggda av ordinaltal mindre än den n-gånger itererade omegapotensen av I + 1. Definiera för varje n ett elementärt ordinalsystem (T_{I}, (T_{i})_{i∈T_{I}}, ≺, ≺′, k, lh, L, ˜≺, level, k̃), så att T_{n} = T_{I} ∪ ⋃_{i∈T_{I}} T_{i} och ≺=≺_{n}.