0
$\begingroup$

I am self-studying Discrete Mathematics, and I have the following question:

Let $X$ be a set with exactly $n$ distinct elements. How many elements does have $\mathcal{P}(X)?$

I know that there are $2^{n}$ subsets. I know how to prove it by using induction on $n$, but I want to solve this question by counting all the elements in $\mathcal{P}(X).$ I am not allowed to use the binomial theorem, or binomial coefficients because they were not defined yet. Is that possible?

2 Answers 2

4

It is. Let $X=\{x_1,\dots,x_n\}$. Now imagine that you are choosing a subset of $X$ by running through the list $x_1,\dots,x_n$ and saying yes, you're in my set or no, you're not in my set to each $x_k$ in turn. You will make $n$ choices, and each of those choices can be made in $2$ ways, so there are altogether $2^n$ ways to make the string of choices. Thus, there are $2^n$ possible subsets of $X$ to choose.

2

In order to choose a subset of $X$, for each element of $X$ you have to decide whether to include it in your subset or not. This gives two possibilities for each element which, multiplied together, gives a total of $2^n$ possibilities.

Another way to state this is that there is a bijection between the subsets of $X$ and the maps from $X$ to $\{0,1\}$ where a subset $A$ of $X$ corresponds to the map $\chi_A$ that maps $x$ to $1$ if it is contained in $A$ and $0$ otherwise. Since there are $2^n$ maps from $X$ to $\{0,1\}$ there must be $2^n$ subsets of $X$.