Betrachten wir exemplarisch, wie gefordert, die Mengen $\{\mathrm{1,2}\}$ und $\{\mathrm{1,2,3}\}$:Wir sehen: Die Mächtigkeit der Potenzmenge entspricht scheinbar $|P(A)|=2^{|A|}$.

Beweis:Die Mächtigkeit der Potenzmenge entspricht der Anzahl an möglichen Teilmengen (nach Definition). Wir können ein Element dabei hineinnehmen oder es herauslassen, wir haben also $2$ Möglichkeiten pro Element und wir müssen für die Teilmenge jedes Element betrachten. Dabei haben wir $|A|$ Elemente. Daher:

Außerdem gilt: $|A|<|P(A)|=2^{|A|}$

Beweis:(Anmerkung: Es gibt sicherlich einen schöneren Beweis…)

Induktionsbeginn: $A=\varnothing \Rightarrow |A|=0<1=|P(A)|$

Induktionsannahme: $|A|<|P(A)|$ gilt für beliebige Mengen.

Induktionsschritt (mit beliebigem Element $a$):