elementary set theory - Prove that there is a bijection between the set of all subsets of $X$, $P(X)$, and the set of functions from $X$ to ${0,1}$.

Given any set $X$, let $P(X)$ be the set of all subsets of $X$, and let $\{0,1\}^X$ be the set of all functions $X \rightarrow \{0,1\}$. Construct a bijection (and its inverse) between P(X) and $\{0,1\}^X$.

Let us define $f: P(X) \rightarrow \{0,1\}^X$ by $f(\alpha) = g_{\alpha}$ where $\alpha \in P(X)$ and $g_{\alpha} : X \rightarrow \{0,1\}$ is defined by

$$g_{\alpha}(x) =\begin{cases}
1 & x \in \alpha \\

0 & x \in X-\alpha
\end{cases}$$

We need to check if this function is well-defined. Let $\alpha, \beta \in P(X)$. If $\alpha=\beta$, then $\alpha$ and $\beta$ correspond to the same set, and so correspond to the same function since both $g_{\alpha}$ and $g_{\beta}$ send that set to 1 and the ($X-$that set) to 0.

If we have a function $g_{\alpha} \in \{0,1\}$, then $\alpha$ is a set in $X$ that is sent to 1. But since $P(X)$ is the set of all sets of $X$, we must have $\alpha \in P(X)$. So the function is surjective.

Finally, if $g_{\alpha}=g_{\beta}$ then both $g_{\alpha}$ and $g_{\beta}$ send the set $\alpha$ or $\beta$ to 1. So $\alpha$ and $\beta$ must be same set. In other words, the function is injective; and hence bijective.

The inverse function is $f^{-1}: \{0,1\}^X \rightarrow P(X)$ where $f^{-1}(g_{\alpha}) = \alpha$.

---

Another way to prove this is to first construct the inverse function, show that it is well defined, and then show that $ff^{-1}$ and $f^{-1}f$ are the identity functions, right?

So if we let $g_{\alpha}=g_{\beta}$, then $\alpha=\beta$, because otherwise $g_{\alpha} (\beta)=0$ and $g_{\beta} (\beta)=1$; a contradiction.

Now we have $f \circ f^{-1} (g_{\alpha}) = f(\alpha) = g_{\alpha}$ and $f^{-1} \circ f(\alpha) = f^{-1}(g_{\alpha}) = \alpha$ , and so $f$ and $f^{-1}$ must be bijective.

Answer

You need to show that the function $f$ that you defined is a bijection.

In order to show that $f$ is surjective, the argument you've posted begins by saying "If we have a function $g_\alpha,\ldots$". But that notation presuposes that there is such an $\alpha$, the very thing to be proved. I would say "If we have a function $g$ on $X$ (i.e. whose domain is $X$) taking values is $\{0,1\}$, then..." and set out to show there is some set $\alpha\subseteq X$ such that $g=g_\alpha$. You have to define that set by using the function $g$, without assuming in advance that such an $\alpha$ exists. And of course the set that will serve as $\alpha$ is $\{x\in X: g(x)=1\}$.

To show that $f$ is one-to-one, you need to show that $f(\alpha)=f(\beta)$ ONLY if $\alpha=\beta$. That's the same as saying if $\alpha\ne\beta$ then $f(\alpha)\ne f(\beta)$.
If $\alpha\ne\beta$ then either there exists $x\in\alpha$ that is not a member of $\beta$ or vice-versa. At this point you can observe that no generality is lost by assuming the first alternative: just call the one that has a member that the other one doesn't have "$\alpha$". The think about $g_\alpha(x)$ and $g_\beta(x)$ where $x$ is that one member.