Vollständige Induktion Potenzmenge

Question

Sei A eine Menge. Die Potenzmenge  P(A)  wir definieren

induktiv, für alle k ≤ 1,

P^k(A) =   P(A) , falls k = 1,

P(P ^k−1(A)) , sonst.

Wir definieren außerdem die Funktion g: ( ℕ \ {0})² → ℕ induktiv

durch g(1, n) = 2ⁿ , für alle n ≥ 1,

und g(k, n) = 2^g(k−1,n) , für alle n ≥ 1 und k ≥ 2.

Beweisen Sie per vollständiger Induktion.

Für alle k ≥ 1 gilt: |P^k(A)| = g(k, |A|).

Answer 1

Ind. anf. k=1  dann ist |P(A)| = 2^n wobei n=|A| ist; denn offenbar ist A eine endliche Menge,

Das fehlt zwar bei der Angabe der Voraussetzungen,

ansonsten wäre die ganze Sache unsinnig.

Und die Aussage: Die Potenzmenge einer n-elementigen Menge hat 2^n Elemente ist ja wohl bekannt.

Sei  nun k ≥ 1 und |P^k(A)| = g(k, |A|).  

Dann gilt P^k+1(A)= P(  P^k(A)) also ist die Elementezahl davon

= 2 ^{Elementezahl von Pk(A)} = 2 ^{g(k, |A|)}   und nach der Def. von g ist das

= g(k+1, |A|).  q.e.d.