0
$\begingroup$

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$

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – drhab
    Feb 27, 2020 at 10:11

1 Answer 1

2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .