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

Accepted Solution

Answer:Step-by-step explanation:As the statement is ‘‘if and only if’’ we need to prove two implications[tex]f : X \rightarrow Y[/tex] is surjective implies there exists a function [tex]h : Y \rightarrow X[/tex] such that  [tex]f\circ h = 1_Y[/tex].If there exists a function [tex]h : Y \rightarrow X[/tex] such that  [tex]f\circ h = 1_Y[/tex], then [tex]f : X \rightarrow Y[/tex] is surjectiveLet us start by the first implication. Our hypothesis is that the function [tex]f : X \rightarrow Y[/tex] is surjective. From this we know that for every [tex]y\in Y[/tex] there exist, at least, one [tex]x\in X[/tex] such that [tex]y=f(x)[/tex].Now, define the sets [tex]X_y = \{x\in X: y=f(x)\}[/tex]. Notice that the set [tex]X_y[/tex] is the pre-image of the element [tex]y[/tex]. Also, from the fact that [tex]f[/tex] is a function we deduce that [tex]X_{y_1}\cap X_{y_2}=\emptyset[/tex], and because  [tex]f[/tex] the sets [tex]X_y[/tex] are no empty.From each set [tex]X_y[/tex]  choose only one element [tex]x_y[/tex], and notice that [tex]f(x_y)=y[/tex].So, we can define the function [tex]h:Y\rightarrow X[/tex] as [tex]h(y)=x_y[/tex]. It is no difficult to conclude that [tex]f\circ h(y) = f(x_y)=y[/tex]. With this we have that [tex]f\circ h=1_Y[/tex], and the prove is complete.Now, let us prove the second implication.We have that there exists a function  [tex]h:Y\rightarrow X[/tex]  such that [tex]f\circ h=1_Y[/tex]. Take an element [tex]y\in Y[/tex], then [tex]f\circ h(y)=y[/tex]. Now, write [tex]x=h(y)[/tex] and notice that [tex]x\in X[/tex]. Also, with this we have that [tex]f(x)=y[/tex]. So, for every element [tex]y\in Y[/tex] we have found that an element [tex]x\in X[/tex] (recall that [tex]x=h(y)[/tex]) such that [tex]y=f(x)[/tex], which is equivalent to the fact that [tex]f[/tex] is surjective. Therefore, the prove is complete.