Surjection

**shilz222** · August 23rd 2007, 05:14 AM

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

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

Is this correct?

**Plato** · August 23rd 2007, 05:58 AM

Originally Posted by shilz222

Let $f: X \to Y$ be a function. Prove that there exists a function $g: Y \to X$ such that $f \circ g = I_Y$ if and only if $f$ is a surjection.
So we first construct $g$ (using axiom of choice) by picking a point in the preimage of $y$ for all $y$ ( $\overleftarrow{f}(Y)$ ). If $f(g(y)) = f(x) = y, \ \forall x \in X$ then $f$ is a surjection. If $f$ is a surjection, then $\forall y \in Y, \exists x \in X, y = f(x)$ . Then $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 $g: Y \to X$ such that $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 $f \circ g = I_Y$ .

**shilz222** · August 23rd 2007, 06:07 AM

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

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

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

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

**Plato** · August 23rd 2007, 07:29 AM

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

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

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

2) Show that $f$ is a surjection implies that there exists a function $g: Y \to X$ such that $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.

**Plato** · August 23rd 2007, 08:46 AM

Originally Posted by shilz222

Actually the $\Leftarrow$ direction is as follows: Given $f$ is a surjection prove that there exists a function $g$ such that $f \circ g = I_Y$ . It is here where we construct the function $g$ .

Well, you have finally seen the light.
But of course, I said that in my very first reply.

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

Thread: Surjection

LinkBack

Thread Tools

Display

Surjection

Similar Math Help Forum Discussions

Injection and Surjection

Surjection

surjection proof

surjection

Surjection

Search Tags