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 $\mathcal{P}(X)$ have?
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?
Best Answer
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.