1. ## Surjection

Let $\displaystyle f: X \to Y$ be a function. Prove that there exists a function $\displaystyle g: Y \to X$ such that $\displaystyle f \circ g = I_Y$ if and only if $\displaystyle f$ is a surjection.

So we first construct $\displaystyle g$(using axiom of choice) by picking a point in the preimage of $\displaystyle y$ for all $\displaystyle y$( $\displaystyle \overleftarrow{f}(Y)$). If $\displaystyle f(g(y)) = f(x) = y, \ \forall x \in X$ then $\displaystyle f$ is a surjection. If $\displaystyle f$ is a surjection, then $\displaystyle \forall y \in Y, \exists x \in X, y = f(x)$. Then $\displaystyle f(g(y)) = f(x) = y$ as required.

Is this correct?

2. Originally Posted by shilz222
Let $\displaystyle f: X \to Y$ be a function. Prove that there exists a function $\displaystyle g: Y \to X$ such that $\displaystyle f \circ g = I_Y$ if and only if $\displaystyle f$ is a surjection.
So we first construct $\displaystyle g$(using axiom of choice) by picking a point in the preimage of $\displaystyle y$ for all $\displaystyle y$( $\displaystyle \overleftarrow{f}(Y)$). If $\displaystyle f(g(y)) = f(x) = y, \ \forall x \in X$ then $\displaystyle f$ is a surjection. If $\displaystyle f$ is a surjection, then $\displaystyle \forall y \in Y, \exists x \in X, y = f(x)$. Then $\displaystyle f(g(y)) = f(x) = y$ as required.
Is this correct?
No it is most definitely not correct. You have confused the two-way proof.

First assume that $\displaystyle g: Y \to X$ such that $\displaystyle f \circ g = I_Y$.
In which case there is no need to construct g because you already have it assumed.
Now just go about proving f is surjective.

That part done, then assume that f is surjective and go about constructing g such that $\displaystyle f \circ g = I_Y$.

3. didnt I do that? Plus it says prove that there exists a function $\displaystyle g: Y \to X$. THat is separate from the other part of the proof.

So the two parts are: Prove existence of function $\displaystyle g: Y \to X$, and the two-way proof.

So I proved: (1)$\displaystyle f \circ g = I_y \Leftrightarrow f$ is surjective and (2) that such a function $\displaystyle g: Y \to X$ exists.

So how come the question didn't given both functions $\displaystyle f: X \to Y$ and $\displaystyle g: Y \to X$?

4. Do you have difficulty understanding the problem? Here is what this problem says.
GIVEN $\displaystyle f: X \to Y$ be a function.
Now we are working in a universe of discourse where $\displaystyle f: X \to Y$ is a fixed function.

Now for the problem:
PROBLEM Prove that there exists a function $\displaystyle g: Y \to X$ such that $\displaystyle f \circ g = I_Y$ if and only if $\displaystyle f$ is a surjection.

1) Show that $\displaystyle g: Y \to X$ such that $\displaystyle f \circ g = I_Y$ implies that $\displaystyle f$ is a surjection.
Here the function g implicitly given from which you are proving something about the function f.

2) Show that $\displaystyle f$ is a surjection implies that there exists a function $\displaystyle g: Y \to X$ such that $\displaystyle f \circ g = I_Y$.
In this part, from an assumed property of f you are constructing a function g having a required property.

Now if you think you have done that, then you mistaken.

5. Originally Posted by shilz222
Actually the $\displaystyle \Leftarrow$ direction is as follows: Given $\displaystyle f$ is a surjection prove that there exists a function $\displaystyle g$ such that $\displaystyle f \circ g = I_Y$. It is here where we construct the function $\displaystyle g$.
Well, you have finally seen the light.
But of course, I said that in my very first reply.

The point of $\displaystyle f$ being a surjection means that the collection $\displaystyle \left\{ {\overleftarrow f (y)} \right\}_{y \in Y}$ forms a partition of $\displaystyle X$.
Now one does have to use the axiom of choice on that collection in order to construct $\displaystyle g$.