# Help to prove $f$ is surjective $\Leftrightarrow \forall y \in Y, (X \times \{y\} \cap G_f ) \ne \emptyset$

Let $f:X \rightarrow Y$ be a function with graph $G_f \subseteq X \times Y$. Prove that $f$ is surjective if and only if $\forall y \in Y, (X \times \{y\} \cap G_f ) \ne \emptyset$

I have some difficulty with $\forall y \in Y, (X \times \{y\} \cap G_f ) \ne \emptyset \Rightarrow f$ is surjective

My attempt:

\begin{align} \forall y \in Y (X \times \{y\} \cap G_f) \ne \emptyset & \Rightarrow & \forall y \in Y, \exists x \in X, (x,y) \in (X \times \{y\} \cap G_f) \\ & \Rightarrow & \forall y \in Y, \exists x\in X, (x,y) \in G_f \\ & \Rightarrow & \forall y \in Y, \exists x \in X, f(x)=y, \text{ since } (x,y) \text { is in } G_f\\ \end{align}

Are there any shortcomings in my proof?

The solution provided was:

There are 3 things I don't understand about the solution:

1. How are we able to conclude $x_0=x_1$ at the end?
2. Why did we choose $(x_1,y_1)$ instead of $(x_1,y_0)$, since we start with $y_0 \in Y$?
3. If we say $x_0=x_1$, doesn't this also mean that $f$ is an injection, since any $y$ will only have 1 image, $x$.

How are we able to conclude $x_0=x_1$ at the end?

They do not 'conclude' $x_0=x_1$, they observe that they can pick $x_0=x_1$. After assuming the antedecent, the statement to prove is $\forall y_0\in Y\exists x_0\in X(f(x_0)=y_0)$. So they begin by taking an arbitrary $y_0\in Y$ and the goal becomes $\exists x_0\in X(f(x_0)=y_0)$. By virtue of the proof they demonstrate that there exists $x_1\in X$ such that $f(x_1)=y_0$, so in the notation $\exists x_0\in X(f(x_0)=y_0)$ you can pick $x_0:=x_1$ to finalize the proof.

Why did we choose $(x_1,y_1)$ instead of $(x_1,y_0)$, since we start with $y_0 \in Y$?

You know that $\forall y \in Y \left(X \times \{y\} \cap G_f \right) \ne \varnothing$, so particularizing to the previously fixed $y_0$ one gets $X\times \{y_0\}\cap G_f\neq \varnothing$. You can, of course, skip the $y_1$ part and assume the second coordinate of the elements of this set is always $y_0$, but the author choose to be slower and not do that. In all rigor, one should write something like "Since $X\times \{y_0\}\cap G_f\neq \varnothing$, there exists $z\in X\times \{y_0\}\cap G_f$. Thus $z\in X\times \{y_0\}$ and therefore $z=(x_1, y_1)$, for some $x_1\in X$ and $y_1\in \{y_0\}$...". With this I want to illustrate that by assuming any element in that set is an ordered pair you're already skipping another (obvious) step. The author simply chose not to skip the $y_1$ bit.

If we say $x_0=x_1$, doesn't this also mean that $f$ is an injection, since any $y$ will only have 1 image, $x$.

No, you never had $f(x_0)=f(x_1)\implies x_0=x_1$ (and even this wouldn't be enough to prove injectivity due to non-arbitrariness of $x_0$ and $x_1$).

As for your proof, it is fine. Alternatively you can prove the contrapositive. If $f$ isn't surjective, there exists $y_0\in Y$ such that $\forall x\in X(f(x)\neq y)$, therefore $\forall x\in X((x,y_0)\not \in G_f)$ which means $X\times \{y_0\}=\varnothing$.

1. You don't, you just need to find one $x$ that works, so that $x_0$ doesn't bring much to the problem. Remember that you can have multiple different $x_0$ that works.

2. your $y_1$ is an element of $\{y_0 \} \cap Y$. Then it is in particular an element of $\{y_0 \}$ so it has to be $y_0$. The proof is just trying to show you the step by step reasoning.

3. No: counter example $f(x)=5$, $\mathbb{R} \rightarrow \{5\}$. This is definitely a surjection but not an injection (any $x$ works).

• @GitGud indeed, I corrected the typo. – Matt B. Jul 16 '14 at 17:26