Matematiska Institutionen Uppsala Universitet Anton Setzer

VT 2000 Övning 2

Övningar i Bevisteori

Övning 5 (1 poäng)

(a) Anta φ(0) = 0. Visa φ_{α}0 = 0.

(b) Låt φ(α) = α. Visa φ_{α}β = β.

Övning 6 (2 poäng) Anta α =_{NF} ω^{α_{0}} + ⋯ + ω^{α_{k}}, β =_{NF} ω^{β_{0}} + ⋯ + ω^{β_{l}} (k, l ≥ 0). Visa

α + β =_{NF} ω^{α_{0}} + ⋯ + ω^{α_{i}} + ω^{β_{0}} + ⋯ + ω^{β_{l}} ,

där i maximal så att α_{i} ≥ β_{0}.

Övning 7 (6 poäng)

(a) Låt α =_{NF} ω^{α_{0}} + ⋯ + ω^{α_{n}}. Visa α · ω = ω^{α_{0}} · ω.

(b) Visa

α^{ω} = \{ \begin{matrix}0 & α = 0 \\ 1 & α = 1 \\ ω & 1 < α < ω \\ ω^{α_{0}·ω} & ω ≤ α =_{NF} ω^{α_{0}} + ⋯ + ω^{α_{n}} \end{matrix}

Övning 8 (3 poäng) α är ett multiplikativt huvudtal omm α > 2 och ∀β, γ < α.β · γ < α. Visa: Mängden av multiplikativa huvudtal är {ω^{(ω^{γ})} | γ ∈ Ord}.

Övning 9 (4 poäng) Låt ≺, ≺′ vara välgrundade relationer, M en mängd. Låt

a ≺′′ b :⇔ ∃a_{0}, a_{1}, b_{0}, b_{1}.(a = ⟨a_{0}, a_{1}⟩ ∧ b = ⟨b_{0}, b_{1}⟩ ∧

((a_{0} ≺ b_{0} ∧ a_{1} ∈ M) ∨ (a_{0} = b_{0} ∧ a_{1} ≺′ b_{1}))

Visa ≺′′ är välgrundad.

Övning 10 (4 poäng) Låt A vara en klass av ordinaltal så att

• 0 ∈ A

• ω^{α_{0}}# ⋯ #ω^{α_{n}} ∈ A ⇔ {α_{0}, …, α_{n}} ⊆ A.

Visa α, β ∈ A ⇒ α + β, α · β, α^{β} ∈ A. Övning 11 (6 poäng) Låt A vara en klass av ordinaltal och A_{0} := ⋃_{α∈A} E(α), där

• E(0) = ∅,

• E(α#β) = E(α) ∪ E(β) (α, β ≠ 0)

• E(ω^{α}) = E(α) (α < ω^{α}) och

• E(γ) = {γ} för ε-tal γ. Låt vidare \overline{A} vara den minsta mängden, så att

• A ∪ \{0\} ⊆ \overline{A} och

• \overline{A} sluten på + och λα.ω^{α}. Visa

(a) \overline{A} = \{α | E(α) ⊆ A_{0}\}.

(b) \overline{A} uppfyller betingelserna för A i övning 10.