# prove surjectivity of a function

I have problems in evaluating the surjectivity of the function $$F$$ defined below.

Let A be any set and consider the power set P(A) of A and the set $$\{0,1\}^A$$ of all functions with domain $$A$$ and codomain $$\{0,1\}$$. The characteristic function $$\chi_B : A \to \{0,1\}$$ of a subset $$B \subseteq A$$ is defined by

$$\chi_B(a)=\begin{cases} 1,&\text{if }a\in B\\ 0,&\text{if }a\notin B\;. \end{cases}$$

The function that assigns the characteristic function to a subset:

$$F: P(A) \to \{0,1\}^A$$

$$A \mapsto \chi_A$$

is a bijection.

I can prove injectivity easily but I am stuck at surjectivity. To prove that a function $$f:A \to B$$ is surjective one has to prove that $$Im\, f = B$$

In this case $$Im\, F = \{\chi_B \in \{0,1\}^A | \chi_B = F(B) \text{ for some } B \in P(A)\}$$

My manual furnishes this proof:

To prove surjectivity of $$F$$, suppose that $$f \in \{0,1\}^A$$ is a function and define the set:

$$B = \{ a \in A : f(a) =1\}$$

then $$\chi_B = f$$ and $$F(A) = f$$ and surjecitivty is proved.

I don't understand it, why that definition of the B set proves surjectiviy??

I understand that, lets do an example, if $$A = \{1,2,3\}$$ and consider the subset $$B = \{1,2\}$$ this is equivalent to the characteristic function $$f(1) = 1, f(2) = 1, f(3) = 0$$

$$B = \{a \in A: f(a) =1\}$$

so that $$\chi_B = f \in \{0,1\}^A$$, but I don't understand how this is a proof of surjectivity of $$F$$

• For an arbitrary $f\in\{0,1\}^A$ it is shown that we can find a set $B$ such that $f=\chi_B$. This $\chi_B$ is obviously an element of the image of $F$. So for an arbitrary $f\in\{0,1\}^A$ it is shown that it is an element of the image of $F$. This implies that every $f\in\{0,1\}^A$ is an element of the image of $F$, which means exactly that $F$ is surjective. Feb 27, 2020 at 10:11

Hint: You have to show that $$\chi_B=f$$. Take any $$a$$ and verify that $$\chi_B(a)=f(a)$$. Both sides are $$0$$ or $$1$$. See when they are equal to $$1$$ and when they are equal to $$0$$.