Question

If A is a finite set having n elements, prove that A has exactly

2ⁿ distinct subsets

Answer 1

Apply Induction on n.

If $|A|=1$, then $A$ as exactly two subsets namely $\phi$ and $A$. So claim is true for $n=1$.

Induction hypothesis: For any set having exactly $n-1$ elements, the

number of subsets is $2^{n-1}$. Let now $A=\{a_1,\dots,a_n\}$ be a set with $|A|=n$. Any subset $X$ of $A$ is either contained in $B=\{a_1,\dots,a_{n-1}\}$ or $a_n\in X$. By induction hypothesis, there are exactly $2^{n-1}$ subsets of $A$ contained $B$. Any other subset $X$ is of the form. $X=\{a\}\cup Y$ where $Y$ is subset of $B$. Their number is therefore equal to the number of subsets of $B$, i. e. $2^{n-1}$. Then the number of all subsets of $A$ is $2^{n-1}+2^{n-1}=2^n$.