Question

DIscrete Math

Answer 1

Answer:

Step-by-step explanation:

As the statement is ‘‘if and only if’’ we need to prove two implications

1. $f : X \rightarrow Y$ is surjective implies there exists a function $h : Y \rightarrow X$ such that  $f\circ h = 1_Y$.
2. If there exists a function $h : Y \rightarrow X$ such that  $f\circ h = 1_Y$, then $f : X \rightarrow Y$ is surjective

Let us start by the first implication.

Our hypothesis is that the function $f : X \rightarrow Y$ is surjective. From this we know that for every $y\in Y$ there exist, at least, one $x\in X$ such that $y=f(x)$.

Now, define the sets $X_y = \{x\in X: y=f(x)\}$. Notice that the set $X_y$ is the pre-image of the element $y$. Also, from the fact that $f$ is a function we deduce that $X_{y_1}\cap X_{y_2}=\emptyset$, and because  $f$ the sets $X_y$ are no empty.

From each set $X_y$  choose only one element $x_y$, and notice that $f(x_y)=y$.

So, we can define the function $h:Y\rightarrow X$ as $h(y)=x_y$. It is no difficult to conclude that $f\circ h(y) = f(x_y)=y$. With this we have that $f\circ h=1_Y$, and the prove is complete.

Now, let us prove the second implication.

We have that there exists a function  $h:Y\rightarrow X$  such that $f\circ h=1_Y$.

Take an element $y\in Y$, then $f\circ h(y)=y$. Now, write $x=h(y)$ and notice that $x\in X$. Also, with this we have that $f(x)=y$.

So, for every element $y\in Y$ we have found that an element $x\in X$ (recall that $x=h(y)$) such that $y=f(x)$, which is equivalent to the fact that $f$ is surjective. Therefore, the prove is complete.