2
$\begingroup$

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: enter image description here

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$.
$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$
  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).

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.