1

Why does the total no. of subsets of $n$ elements equal $2^n$?

I was taught that it is because each element has two choices either making a set or not. Thus giving $2×2×2\ldots$ subsets.

But I didn't understand how does it work in giving this result.

J. W. Tanner
  • 60,406
ananya bht
  • 11
  • 1

2 Answers2

2

Proof by induction.

When $n=0$ then $\mathcal P(\emptyset)=\{\emptyset\}$ so $|\mathcal P(\emptyset)|=1.$

Now, assume it is true for all $|S|=n,$ and assume $|T|=n+1.$

Pick one element $x\in T.$ Then let $T_0=T\setminus \{x\}.$ We have $|T_0|=n.$

Then for every $M\subseteq T_0$ there are exactly two subsets of $T,$ $M$ and $M\cup\{x\}.$

So $$|\mathcal P(T)|=2|\mathcal P(T_0)|=2\cdot 2^{n}=2^{n+1}.$$

We could be alightly more rigorously prove this by defining a function $f:\mathcal P(T)\to \mathcal P(T_0)\times \{1,2\}$ and prove it is a bijection.

We define, for $M\subseteq T,$ $$f_2(M)=\begin{cases}1&x\in M\\2&x\notin M \end{cases}$$

Then $f(M)=(M\cap T_0,f_2(M)).$

Showing this is a bijection is tedious work, but direct.

Thomas Andrews
  • 177,126
0

Suppose you number the elements $1,2,\cdots,n$. Then each element of the power set can be represented by a binary string of length $n$: Namely, a subset of the $n$ elements, say $S$, will be denoted by the $n$-bit string $b(S)=(b_1(S),b_2(S),\cdots,b_n(S))$, where $b_i(S)=1$ if the $i$-th elements belongs to $S$, or $b_i(S)=0$, otherwise. Note that each subset corresponds to a unique $n$-bit string, and vice versa. Now the number of $n$-bit strings is $2^n$. Hence the number of subsets is also $2^n$.

QED
  • 12,644