Transcript
Logik II - Wintersemester 2015-16 ¨ Ubungsaufgaben
Dr. Philipp Schlicht
Serie 3
Universit¨at M¨ unster
Aufgabe 8 (6 Punkte).
(1) Zeigen Sie, dass es f¨ ur alle Ordinalzahlen α, β ein-
deutige Ordinalzahlen γ und δ < β gibt, so dass α = (β ⊗ γ) ⊕ δ. (2) (Cantor-Normalform) Zeigen Sie, dass es f¨ ur jede Ordinalzahl α eindeutige α0 ≥ · · · ≥ αk gibt, so dass α = ω ⊗α0 ⊕ · · · ⊕ ω ⊗αk .
Aufgabe 9 (14 Punkte).
(1) (a) Jede Teilmenge einer endlichen Menge ist
endlich. (b) Das Bild einer endlichen Menge unter einer Abbildung ist endlich (c) Die Vereinigung von endlich vielen endlichen Mengen ist endlich. (d) Die Potenzmenge jeder endlichen Menge ist endlich. (2) (a) Das Bild einer abz¨ ahlbarer Menge unter einer Abbildung ist abz¨ahlbar. (b) Jede Teilmenge einer abz¨ahlbaren Menge ist abz¨ahlbar. (c) Die Vereinigung von abz¨ahlbar vielen abz¨ahlbaren Mengen ist abz¨ahlbar. Aufgabe 10 (4 Punkte). Angenommen X ist eine unendliche Menge und S := [X]<ω ist die Menge der endlichen Teilmengen von X. Dann ist |S| = |X|.
Aufgabe 11 (4 Punkte). Angenommen (L, <) ist eine lineare Ordnung, so dass |pred< (x)| < κ f¨ ur alle x ∈ L. Zeigen Sie, dass |L| ≤ κ. Eine schwach monoton wachsende Funktion f : Ord → Ord heisst stetig, wenn supα<β f (α) = f (β) f¨ ur alle Limesordinalzahlen β gilt. Sie d¨ urfen verwenden, dass es f¨ ur jede unendliche Limesordinalzahl γ eine streng monoton wachsende stetige kofinale Funktion f : cof(γ) → γ gibt. Der Beweis des Satzes von K¨onig verallgemeinert den Beweis des Satzes von Cantor, die folgende Aufgabe ist eine weitere Verallgemeinerung des Satzes von Cantor. Aufgabe 12 (6 Punkte). Zeige Sie, dass κcof(κ) > κ f¨ ur alle unendlichen Kardinalzahlen κ gilt.
(Hinweis: nehmen Sie ¨ ahnlich wie im Beweis des Satzes von Cantor
an, dass es eine Liste der L¨ ange κ gibt, die alle Funktionen f : cof(κ) → κ aufz¨ ahlt. Konstruieren Sie ein Funktion g : cof(κ) → κ, die nicht in der Liste vorkommt.) Eine unendliche Kardinalzahlκ ist regul¨ ar, wenn cof(κ) = κ und singul¨ ar, wenn cof(κ) < κ.
2
Aufgabe 13 (Zusatzaufgabe, 6 Punkte). Beweisen Sie die folgenden Aussagen. (1) Jede streng monoton wachsende stetige Funktion f : Ord → Ord besitzt einen Fixpunkt. (2) Die ℵ-Funktion hat einen Fixpunkt. (3) Wenn κ ein regul¨ arer Fixpunkt der ℵ-Funktion ist, dann gibt es einen singul¨aren Fixpunkt µ < κ der ℵ-Funktion.
Abgabe: Montag, den 16. November 2015, 18:00, in Briefkasten 174.
