Show that for a finite set $A$ of cardinality $n$, the cardinality of $P(A)$ is $2^n$.

Question

How do you show that for a finite set $A$ of cardinality $n$, the cardinality of $P(A)$ is $2^n$? (P is the power set). Can someone check my steps? Here is what I have so far:

n=1 case: |A|=1, |P(A)|=$2^1$=2. (∅, {1})

Assume it is true for n, then it implies that the n+1 case is true by standard induction.

let |A|=n+1 and {a} ∈ A, then n=|A\{a}|, |P(A\{a})|=$2^n$

then A=A\{a} + {a} = n+1

|P(A\{a})|+|P({a})| = $2^n$ + $2^1$ = 2^(n+1)

Therefore, the cardinality of P(A) is $2^n$.

Answer 1

There are $2^n$ strings of length $n$ in the alphabet $\{0,1\}$ (*). Let $A = \{a_1, \ldots, a_n\}$ and consider the map $$ \pi((b_1, \ldots, b_n)) \mapsto \{a_i \mid i \le n \wedge b_i = 1 \}, $$ where $b_i \in \{0,1\}$. Show that $\pi$ is a bijection from the set of strings of length $n$ in the alphabet $\{0,1\}$ onto $\mathcal P(A)$.

(*) If you don't already know this, you can prove it easily by an induction on $n$.

Answer 2

We have $n$ elements and for each one we can choose whether or not insert it into the set, thus we have 2 choice for n times and for the Rule of Product

$$|\mathcal P(A) |=\stackrel{\color{red}{n \,times}}{2\cdot 2\cdot 2\cdot 2\cdot ...\cdot 2}=2^n$$

Answer 3

There are $\binom{n}{0}=1$ ways to create a subset of cardinality 0 (the empty set), $\binom{n}{1}=n$ ways to create a subset of cardinality 1, and so on ...

So the total number of subsets is $$\binom{n}{0}+\binom{n}{1}+\dots+\binom{n}{n}$$ By the binomial theorem, $$(1+1)^n=\sum_{i=0}^{n}\binom{n}{i}$$ this sum is equal to $2^n$.