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