Zeigen Sie mit vollständiger Induktion: #P(Xℓ) = 2ℓ.

Question

Aufgabe:

a) Sei ℓ ∈ N und Xℓ := {1, 2, . . . , ℓ}. Zeigen Sie mit vollständiger Induktion: #P(X_ℓ) = 2^ℓ.
b) Sei M eine unendliche und N eine abzählbare Menge. Zeigen Sie: M und M ∪ N sind
gleichmächtig.
Hinweis: In b) wird erwartet, dass Sie ein bijektive Abbildung zwischen M und M ∪N definieren
und deren Bijektivität begründen. Ein Blick auf Bemerkung :

(SeiM eine Mengen, deren Elemente selbst wieder Mengen sind, also z.B.

M = {N,N0,Q,R,∅, {π}} oder M = P (N) etc.6
. Esist nicht schwer zu zeigen, dass M ∼ N :⇔ M und N sind gleichmächtig auf M eine Äquivalenzrelation definiert.
Problem/Ansatz:

Comments

a) sollte leicht sein, Was hast du bei b versucht

Bitte zeig erst deine Überlegungen, dann frage genauer nach und stell nicht einfach umkommentiert HA als Frage.

lul

Answer 1

a)  Für ℓ=1 ist Xℓ := {1}, also P(Xℓ) = {∅ ; Xℓ}  also #P(Xℓ) = 2 = 2¹ .

Aussage stimmt für ℓ=1.

Ind. Vor. Es stimmt für ein ℓ ∈ℕ.

==>   X_ℓ+1 = Xℓ ∪ {ℓ+1}.

Betrachte alle Elemente (Teilmengen von X_ℓ+1 )  von P(X_ℓ+1), die  ℓ+1

nicht enthalten. Das sind genau die Elemente von P( Xℓ), also laut IV 2^ℓ Stück.

Die anderen Elemente von P(X_ℓ+1) sind genau die, die man dadurch erhält,

dass man zu einer Menge aus P(X_ℓ) das Element ℓ+1 hinzufügt, also

wieder 2^ℓ Stück.

Somit gilt #P(X_ℓ+1)=2^ℓ + 2^ℓ = 2*2^ℓ = 2^ℓ+1  q.e.d.