MATHEMATISCHES INSTITUT DER UNIVERSITÄT BONN Prof. Dr. Philip Welch

Bonn, den 10.07.2002

Berechenbarkeitstheorie Aufgabenblatt 11

Aufgabe 1 Ein Ideal I ist eine Menge I ⊆ D, so daß gilt:

(i) \underline{a} ≤_{T} \underline{b} ∈ I → \underline{a} ∈I; (ii) \underline{a}, \underline{b} ∈ I → \underline{a} ∪ \underline{b} ∈ I. Zeigen Sie: Wenn I ein abzählbares Ideal ist, so gibt es ein exaktes Paar \underline{b}, \underline{c} für I. (Ein Paar \underline{b}, \underline{c} ist exakt für I, wenn gilt: \underline{a} ∈I⟷ [\underline{a} ≤ \underline{b} ∧ \underline{a} ≤ \underline{c}].) Hinweis: Benutzen Sie direkt den Satz von Kleene-Post-Spector.

Aufgabe 2 Zeigen Sie, daß K nicht einfach ist.

Homepage der Vorlesung:

http://www.math.uni-bonn.de/people/logic/Lectures/SoSe2002/Welch.html
Newsgroup: uni-bonn.math.logik