Assertion
The power set P(M) of a set M with n elements contains 2n elements.
Proof
base case: n = 0
The set which contains 0 elements is the empty set \(\emptyset = \{~\}\).
Its power set contains 1 element (1 = 20), namely the empty set: \(P(\emptyset) = \{\emptyset\} = \{\{~\}\}\).
Iinductive step: A(n) => A(n+1)
Let \(M_{n+1}\) be a set with n+1 elements. \(e_1,~e_2,~\dots~e_{n},~e_{n+1}\).
It hast the subset \( M_{n} \) with n elements \( e_1,~e_2,~\dots~e_{n} \).
\( P(M_{n}) \) has \( 2^n \) elements (assumption), namely the \( 2^n \) subsets of \( M_{n} \): \( T_{1},~T_{2},\dots~T_{2^n} \).
They are the subsets of \( M_{n} \) that implies that they are subsets of \( M_{n+1}\) so they are elements of \(P(M_{n+1})\).
Additionally contains \( P(M_{n+1}) \) the subsets ofon \( M_{n+1} \) that contain the element \( e_{n+1} \)
Those can be constructed by joining \( T_i \quad i\in\{1\dots 2^n\}\) with \( e_{n+1} \)
Each subset \( T_i \) adds one element: \( e_{n+1} \). \(T_i‘ = T_i \cup e_{n+1}\). The number of subsets doubles.
We have:
\( P(M_{n+1}) = \{T_{1},~T_{2},\dots~T_{2^n},~T_{1}‘,~T_{2}‘,\dots~T_{2^n}’\}\)
The power set has \( 2^n + 2^n = 2\cdot 2^n = 2^{n+1} \) elements.
q.e.d.