Sei A eine Menge. Die Potenzmenge P(A) wir definieren
induktiv, für alle k ≤ 1,
Pk(A) = P(A) , falls k = 1,
P(P k−1(A)) , sonst.
Wir definieren außerdem die Funktion g: ( ℕ \ {0})2 → ℕ induktiv
durch g(1, n) = 2n , für alle n ≥ 1,
und g(k, n) = 2g(k−1,n) , für alle n ≥ 1 und k ≥ 2.
Beweisen Sie per vollständiger Induktion.
Für alle k ≥ 1 gilt: |Pk(A)| = g(k, |A|).