Übungen zur Vorlesung “Mengenlehre” WS 2009/2010, Blatt 1

Aufgabe 1: Eine Menge A ist transitiv, wenn x ⊆ A für alle x ∈ A (wenn also aus x ∈ A und y ∈ x sich y ∈ A ergibt). Man zeige:

a) ∅ ist transitiv.

b) Ist x transitiv und y ⊆ x, so ist x ∪ {y} transitiv. Insbesondere ist x ∪ {x} transitiv.

c) Sind x und y transitiv, so auch x ∩ y und x ∪ y; allgemeiner: Ist A eine nicht leere Menge von transitiven Mengen, so sind ⋂ A und ⋃ A transitiv.

Aufgabe 2: Sei d ∈ ℕ, d ≥ 2. Für n ∈ ℕ mit n ≥ 1 bezeichne [n]_{d} die Darstellung von n zur Basis d.

[23]_{2} = 2^{4} + 2^{2} + 2^{1} + 2^{0}, [23]_{3} = 2 · 3^{2} + 3^{1} + 2 · 3^{0}, [23]_{4} = 4^{2} + 4^{1} + 3 · 4^{0}

Ersetzt man in ihr in den Exponenten, Exponenten von Exponenten,… alle Zahlen größer als d, wiederum durch durch ihre Darstellung zur Basis d, so erhält man schließlich die Superdarstellung [[n]]_{d} von n zur Basis d, also etwa

[[23]]_{2} = 2^{2^{2}} + 2^{2} + 2^{1} + 2^{0}.

Oder etwa

[266]_{2} = 2^{8} + 2^{3} + 2^{1} und [[266]]_{2} = 2^{2^{2+1}} + 2^{2+1} + 2^{1}.

Für n ∈ ℕ und d ≥ 2 sei G(d, n) ∈ ℕ wie folgt definiert:

• Wenn n = 0, so G(d, n) = 0.

• Wenn n ≥ 1, so erhält man G(d, n) in dem man in der Superdarstellung [[n]]_{d} von n zur Basis d alle vorkommenden d durch d + 1 ersetzt und von der dadurch resultierenden Zahl 1 subtrahiert.

Somit

G(2, 23) = 3^{3^{3}} + 3^{3} + 3^{1} + 3^{0} − 1 = 3^{3^{3}} + 3^{3} + 3^{1}
G(2, 266) = 3^{3^{3+1}} + 3^{3+1} + 3^{1} − 1 = 3^{3^{3+1}} + 3^{3+1} + 2 · 3^{0}.

Für n ≥ 1, definiert man nun die Folge

n_{1}, n_{2}, n_{3}, …

wie folgt:

• n_{1} := n

• n_{ℓ+1} := G(ℓ + 1, n_{ℓ}), also

n_{1} = n, n_{2} = G(2, n_{1}), n_{3} = G(3, n_{2}), …

So erhalten wir für n = 266

266_{1} = 266 = 2^{2^{2+1}} + 2^{2+1} + 2^{1}
266_{2} = 3^{3^{3+1}} + 3^{3+1} + 3^{1} − 1 = 3^{3^{3+1}} + 3^{3+1} + 2 · 3^{0}
266_{3} = 4^{4^{4+1}} + 4^{4+1} + 2 · 4^{0} − 1 = 4^{4^{4+1}} + 4^{4+1} + 1 · 4^{0}
266_{4} = 5^{5^{5+1}} + 5^{5+1} + 1 · 5^{0} − 1 = 5^{5^{5+1}} + 5^{5+1}
⋮

Man zeige: Für alle n ≥ 1 gibt es ein ℓ ≥ 1 mit n_{ℓ} = 0.

Abgabe: Mittwoch, 28.Oktober, vor der Vorlesung.

Die Übungsblätter findet man auch unter

http://home.mathematik.uni-freiburg.de/bjoern/lehre/ml0910/ml0910.html