# Graphs

• Jul 28th 2007, 11:01 PM
tukeywilliams
Graphs
Given $f: X \to Y$ is a function with graph $G_f \subseteq X \times Y$ prove that $f$ is surjective $\Leftrightarrow \forall y \in Y, (X \times \{y \} \cap G_f) \neq \emptyset$.

Proof: ' $\Rightarrow$' direction: If $f$ is surjective, then $\forall y \in Y, \exists x \in X, y = f(x)$. Then $X \times \{y \} \cap G_f \Rightarrow x \in X$ and $y \in \{y \}$ or $y = y$. Then $X \times \{y \} \cap G_f \neq \emptyset$ because by definition $f$ is surjective.

' $\Leftarrow$' direction: If $\forall y \in Y, (X \times \{y \} \cap G_f) \neq \emptyset$ then $x \in X$ and $y = y$ so that $X \times \{y \} \cap G_f \neq \emptyset$. Then $\forall y \in Y, \exists x \in X, y = f(x)$ so that $f$ is surjective. $\square$

Is this proof correct?

Thanks
• Jul 29th 2007, 03:13 AM
Plato
Quote:

Originally Posted by tukeywilliams
Is this proof correct?

Yes it is correct and well done.