elementary set theory - Show that there is a bijection between powersets and indicator functions. (I don't understand the solution)

Let X be a set, and A a subset of X (In other words : $A \subset X$)

$\chi_A (x)$ : $X \rightarrow \left \{ 0,1 \right \}$ is an indicator function, which gives 1 if $x \in A, 0$ otherwise.

$\left \{0,1 \right \}^X$ is the set of all functions $X \rightarrow \left \{0,1 \right \}$ and $P(X)$ is the power set of X.

Show that the following is a bijection :

$$χ: P(X) \rightarrow \left \{0,1 \right \}^X$$

$$A \rightarrow χ_A$$

SOLUTION:

Let us define a function $\phi$ as the following:

$$φ : \left \{0,1 \right \}^X \rightarrow P(X)$$

$$f \rightarrow f^{-1} (1)$$

which maps every $f : X \rightarrow \left \{0,1 \right \}$ to the inverse image $\left \{x \in X | f(x)=1 \right \}$ of 1.

Now we verify that $\phi$ is an inverse to $\chi$, in other words that $\phi \circ \chi$ is the identity to P(X), that $\chi \circ \phi$ is the identity to $\left \{ 0,1 \right \}^X$.

Thus $\chi$ is bijective.

---

I don't really understand why this proves that $\chi$ is bijective.

Bijective means that the function is both surjective and injective, that every element of {0,1} has exactly one inverse image. How can we be sure that 0 and 1 have exactly one preimage ?

In fact, I don't see at all why they use this kind of proof, why they use a function $\phi$ defined as above to prove a bijection. How can that prove that $\chi$ is bijective ?

Thanks for your help.

(Sorry if my english is bad, it isn't my mother tongue and I translated the exercise above from german.)

Answer

It turns out that a function is bijective if and only if it is invertible. That is, a function $f : A \to B$ is both injective and surjective exactly when there exists a function $g : B \to A$ such that $f(g(b)) = b$ and $g(f(a)) = a$.

To see this, suppose that $g$ exists. Then

• $f$ is injective because $f(a) = f(a')$ implies $a = g(f(a)) = g(f(a')) = a'$.




• $f$ is surjective because given $b \in B$ if we put $a = g(b)$ then $f(a) = f(g(b)) = b$.

Conversely, if $f$ is bijective, then we can define $g : B \to A$ by setting $g(b) = a$ where $f(a) = b$. Such an $a$ exists because $f$ is surjective and this $a$ is unique because if $f(a') = b$ then injectivity means that $a' = a$. Given this definition, $f(g(b)) = f(a) = b$ and $g(f(a)) = g(b) = a$. Thus $g : B \to A$ is the inverse of $f$.