Proof for Surjections

Question

I'm reading through Basic Algebra I (which I enjoy so far. Thoughts on this for self-studying?) and am having a difficult time proving surjection. I believe I understand the concept, but when it comes to the proof I'm not sure how I'm supposed to prove it. Is this an acceptable proof, or is it at least part of the final proof?

$f$ and $g$ are surjective $\implies f \circ g$ surjective

Known: $$\forall y\in Y, \exists x \in X \mid y = f(x)$$ $$\forall z\in Z, \exists y \in Y \mid z = g(y)$$

Therefore: $$\forall y\in Y \texttt{ and }\forall z\in Z, \exists x \in X \mid y = f(x), z = g(y) = g(f(x)) = (g \circ f)(x)$$

So I guess the final line should be:

$$\forall z \in Z, \exists x \in X \mid z = (g \circ f)(x)$$

P.S. This is my first post here, so hopefully the style isn't too bad.

EDIT: What if I included an extra set that includes the members of Y that exist for z = g(y)?

$$A = \{ y \in Y \mid z = g(y)\}$$ $$\forall y_A \in A, z \in Z, \exists x \in X \mid y = f(x) \texttt{ and } z = g(y_A) = g(f(x))$$

$$\forall z \in Z, \exists x \in X \mid z = g(f(x))$$

(Perhaps I'm not explaining it right)

Answer 1

It is not correct to say that $$\forall y\in Y \texttt{ and }\forall z\in Z, \exists x \in X \mid y = f(x), z = g(y) = g(f(x)) = (f \circ g)(x)$$ You cannot guarantee that $z=g(y),\forall y,z$. For example, let $X=Y=Z$ and $f,g$ be the identity map. It is clearly incorrect that $\forall y,z(\exists x(y=x,z=y=x))$.

Instead, argue through inference rules of predicative logic, like universal instantiation and existential instantiation: $$(\forall z\in Z(\exists y \in Y (z = g(y)))) \\\Rightarrow (\exists y \in Y (z_v = g(y))) \\\Rightarrow z_v=g(y_0) $$ and universal instantiation and existential instantiation: $$(\exists x \in X (y_0 = f(x))) \\\Rightarrow (y_0 = f(x_0)) $$

hence $z_v=g(f(x_0)$. Then existential generalization and universal generalization: $$(\exists x \in X (z_v=g(f(x)) \\\Rightarrow \forall z \in Z(\exists x \in X(z=g(f(x))) $$

This is basically a rigor version of human intuition.

Answer 2

You write:

$$ \text{Therefore, } \forall (y,z) \in Y \times Z, \exists x \in X \mid y = f(x), z = g(y) = g(f(x)) =: (g \circ f)(x). $$

What this is saying is that if $f : X \to Y$ and $g : Y \to Z $ are surjective, then there always exists an $x \in X$ such that the calculation $(f(x), g(f(x)))$ will lead you to any desired $(y,z)$ combination in $Y \times Z$; however, this is incorrect, and here is a simple counterexample:

$$ X := Y := Z := \{0,1\} \\ f(x) := \begin{cases}1 & x = 0 \\ 0 & \text{otherwise} \end{cases} \\ g(x) := \begin{cases}1 & x = 1 \\ 0 & \text{otherwise} \end{cases} \\ g(f(x)) = \begin{cases} g(1) = 1 & x = 0 \\ g(0) = 0 & \text{otherwise} \end{cases} =: f(x). $$

All possible $(y,z)$ tuples selected from $Y \times Z$ are $(0,0), (0,1), (1,0), (1,1)$. But the only ones we can reach from the calculation $(f(x), g(f(x)))$ for $x \in X$ are $(0,0)$ and $(1,1)$ (for $x = 0$ and $x = 1$ respectively).

This wasn't our goal, anyway. We would like to prove that for any surjective functions $f : X \to Y$ and $g : Y \to Z $, there always exists an $x \in X$ such that the calculation $g(f(x))$ will lead you to any desired $z$ in $Z$ (in other words, $(g \circ f) : X \to Z$ is also surjective).

If you remove that line from your proof, then you already have a decent proof, but somewhat tautological (like "$2+2=4$ because $2+2=4$") unless you back it up with some lower level logic. Here's a proof I came up with:

$$ \begin{align*} & \forall y \in Y, \exists x \in X \mid f(x) = y, & (1) \\ & \forall z \in Z, \exists y \in Y \mid g(y) = z. & (2) \\ \\ & \text{Therefore, } \\ & \forall z \in Z, \exists y \in Y \mid (\exists x \in X \mid f(x) = y), \, g(y) = z. & (3) \\ & \forall z \in Z, \exists y \in Y \mid (\exists x \in X \mid f(x) = y, \, g(f(x)) = z). & (4) \\ & \forall z \in Z, \exists x \in X \mid (\exists y \in Y \mid f(x) = y, \, g(f(x)) = z). & (5) \\ & \forall z \in Z, \exists x \in X \mid (\exists y \in Y \mid f(x) = y), \, g(f(x)) = z. & (6) \\ & \forall z \in Z, \exists x \in X \mid (g(f(x)) = z). & (7) \\ \end{align*} $$

(3) follows from (1) and (2) by universal instantiation ("(1) holds for all $y$ in $Y$. Therefore, it holds for this particular $y$ in $Y$.").

(4) follows from (3) by existential generalization ("$g(y) = z$. Therefore, there exists some value of $x$ in $X$ such that $g(y) = z$.") and equality ("$y = f(x)$. Therefore, $g(y) = g(f(x))$.").

(5) follows from (4) by quantifier rearrangement ("The existence of $x$ does not depend on the existence of $y$, nor vice versa. Therefore the quantifiers can be swapped."). I'm not sure if this has a more formal name or if it can be proved using additional logic, but here are some links I found that suggest that it's a valid mathematical argument: [1] [2]

(6) follows from (5) by existential instantiation ("$g(f(x)) = x$ for some value of $y$, which we can call $y_0$. The truth of the statement $g(f(x)) = x$ does not depend on the value of $y_0$. Therefore, $g(f(x)) = x$ (in general).").

(7) is a weaker version of (6), and it follows by simplification ("P and Q. Therefore, Q.").