Induktionsbasis:

´n = 0´ ´=> #M = 0´ ´=> M = O/´ ´=> P(M) = {O/}´ ´=> #P(M) = 1 = 2^0´

Induktionsvorraussetzung:

´AA n in NN: #P(M) = 2^n´

Induktionsschluss:

Sei ´M_(n+1)´ eine Menge für die gelte: ´#M_(n+1) = (n+1)´ ´M_(n+1) = {e_1, e_2, …, e_(n+1)}´

Nun betrachen wir die Teilmenge ´M_n´. Es gilt: ´P(M_n) = 2^n´ (Induktionsvorraussetzung) ´P(M_n) = {T(1), …, T(2^n)}´

´=> P(M_(n+1)) = {T(1), …, T(2^n), T(1) uu {e_(n+1)}, …, T(2^n) uu {e_(n+1)}}´ ´=> #P(M_(n+1)) = 2^n + 2 = 2 * 2^n = 2^(n+1)´