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$.