Matematiska Institutionen Uppsala Universitet Anton Setzer

VT 2000 Övning 4

Övningar i Bevisteori

Övning 16 (4 poäng) Definera fundamentalföljder för {α ∈ Ord | α < Γ_{0}} och visa att de verkligen är fundamentalföjder.

Övning 17 (8 poäng) Modifiera fundamentalföljderna i Övning 16 så att Bachmann-villkoret gäller och visa det.

Övning 18 (4 poäng) Låt f ∈ PR^{2} så att relationen ≺:= {(m, n) ∈ ℕ^{2} | f(m, n) = 0} är välgrundad. Låt (s ≺ t) :≡ f(s, t) = 0. Visa för n ∈ ℕ:

Z^{∞} ⊢_{0}^{2+4|n|_{≺}} ¬Prog_{≺}(X), ∀y(y ≺ \underline{n} → y ∈ X) .

Övning 19 (8 poäng) Låt f, ≺ vara som i övning 17 och ≺ dessutom vara transitiv. Låt för U ⊆ ℕ |n|_{U} := sup{|i|_{U} + 1 | i ≺ n ∧ i ∉ U}, U^{α} := {n ∈ ℕ | |n|_{U} < α} ∪ U. För M ⊆ ℕ och slutna X-positiva sekvenser Γ i L[X] definerar vi: ⊧ Γ[M] :⇔ Γ är sannt i N med interpretation av X som M.

(a) Visa för U ⊆ ℕ, m_{0} ∈ ℕ \ U och U′ := U ∪ {m_{0}}: |n|_{U} ≤ |n|_{U′} + 1 för n ∈ ℕ. [Hänvisning: Visa först: m_{0} ⊀ n ⇒ |n|_{U} = |n|_{U′}.]

(b) Visa för slutna X-positiva sekvenser Γ:

(Z^{∞} ⊢_{0}^{α} ¬Prog_{≺}(X), \underline{m_{1}} ∉ X, …, \underline{m_{k}} ∉ X, Γ) ⇒⊧ Γ[U^{α}] med U := \{m_{1}, …, m_{k}\} .