Proof for the question: In how many ways you can choose a subset of $X={x_1,x_2,...,x_n}$?

Question

In how many ways you can choose a subset of $X={x_1,x_2,...,x_n}$ ?

Proof: In order to justify the result in a formal way we can construct a bijection:

$2^X=$ {all subsets of $X $ } $⇌^ \alpha_\beta $ $\{(e_1,...,e_n) \mid e_i \in \{0,1\}\}=Y$
$A\subseteq X \rightarrow^\alpha \alpha(A)=(e_1,e_2,...,e_n)$ such that $e_i=\begin{cases} 1, & \text{if $x_i\in A$ } \\ 0, & \text{if $x_i\notin A$} \end{cases}$
$$\beta((e_1,e_2,...,e_n))=\{x_i \mid if \quad e_i=1\} \leftarrow^\beta (e_1,e_2,...,e_n)$$
It is easy to see that $\alpha \circ\beta=id_Y$ and $\beta\circ\alpha=id_{2^X}$
This bijection gives us that $|2^X |=2^n=|Y|$

This piece is in the lecture notes, and I couldn't follow the reasoning in the proof. Could somebody explain the whole proof to me ?

Answer 1

You want to show that $2^X$ and $Y$ have the same cardinality, so you construct bijections between them: $\alpha$ and $\beta$. The definition of $\beta$ is not very clear, but $\beta((e_1,\dots,e_n))$ is the subset of $X$ consisting of those $x_i$ for which $e_i=1$. For instance, if $(e_1,\dots,e_n)=(1,0\dots,0)$, then $\beta$ gives you $\{x_1\}$. So what do $\alpha$ and $\beta$ do? If you have a subset of $X$, $\alpha$ "labels" with $1$ the elements that belong to it and with $0$ those that do not. If you have a labeling of the elements of $X$ by $0$ and $1$'s, $\beta$ assigns to this labeling the subset of $X$ consisting of the elements with label $1$. It should be clear, after a brief thought, that $\alpha$ and $\beta$ are inverses, and therefore bijections.

What have you gained? Two sets that are in bijection have the same number of elements, so if you know that $2^X$ has cardinality $2^n$, you also know that the same holds for $Y$, and viceversa. It corresponds to the number of different subsets of $X$ (or of any other set with $n$ elements).

Answer 2

Here is the idea behind the construction of the bijection:

You can create a subset of $X$ as follows: flip a coin, and if it is heads, select $x_1$ for your subset. If it is tails, do not select $x_1$.

Repeat $n-1$ times with $x_2$, $x_3$, etc.

$n$ coin flips will uniquely determine a subset of $X$. There are $2$ outcomes to each flip, hence $2^n$ possible outcomes of the sequence of flips. Thus there are $2^n$ subsets of $X$.

Answer 3

Well, I don't know if it's informal but you can think of it as the following:

For each element $x_i$, suppose it represents the $i^{th}$ digit of the binary number $B$ with $n$ digits in total. If $x_i = 1$, we take $x_i$ to the subset. If $x_i = 0$, we don't. Then number of subsets is the total number of binary numbers with $n$ digits, starting from $B=\underbrace{00...0}_{n \text{ digits}}$ to $B=\underbrace{11...1}_{n \text{ digits}}$. And these numbers in decimal form are $0$ and $2^n-1$, respectively. Therefore there are $2^n$ subsets in total.