Graphs

**tukeywilliams** · July 28th 2007, 11:01 PM

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