Question

DIscrete Math

Show that the function f : X → Y is surjective iff there exists a function h : Y → X such that f · h = 1Y

Answer 1

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.