Whats wrong with this proof? (trying to prove a function is surjective)

Question

Let $f : A → B$ and $g : A' → B'$ be functions that are onto, and $h : A × A' → B × B'$ be the function $h(x, y) = (f(x), g(y))$.

Part1. Dr. Bob tries to prove that $h$ is onto with the following argument. Let $A = B = \{1, 2\}$, $A' = B' = \{a, b\}$, $f$ be given by $f(1) = 2$ and $f(2) = 1$, and $g$ be given by $g(a) = a$ and $g(b) = b$. Then clearly $h$ is onto, because $h(2, a) = (1, a)$, $h(1, a) = (2, a)$, $h(2, b) = (1, b)$, and $h(1, b) = (2, b)$. What is wrong with Dr. Bob’s proof?

I can't figure out what is wrong, bob has the outputs for $h$ as $(1,a)$, $(2,a)$, $(1,b)$, and $(2,b)$. Isn't that every element that is possible for the output? Isn't that enough to make it onto?

The second part of this problem is to correctly prove that $h$ is onto, but my proof would like bob's proof, which is incorrect.

Answer 1

What if $A, B$ are different sets than $\{1, 2\}$? What if $A = \mathbb{Q}$ and $B = \mathbb{N}$?

You can't proof a general statement by specializing to a convenient case.

Answer 2

You need to get back to basics and definition.

Take $\forall z\in A'\times B'$, $z=(z_x,z_y)$, with $z_x\in A'$ and $z_y\in B'$.

Since $z_x\in A'$, $\exists x\in A$ such that $f(x)=z_x$ (by definition of $f$)

Similarly $\exists y\in B$ such that $g(y)=z_y$

Thus

$\forall z=(z_x,z_y)\in A' \times B'$, $\exists (x,y)\in A \times B$ such that $h(x,y)=(f(x),g(y))=(z_x,z_y)$

Answer 3

This is a common error that a lot of undergrads make when they first start doing rigorous maths. The reason for it is usually due to the lack of distinction between justification and proof.

It is easy to get into the habit of thinking, "well it works for this one example so yeah its probably true" rather than, "it works in all cases so IS true".

Here is a silly example that will convince you to stop trying to prove things by example.

Claim - All numbers are $\pi$.

Proof - Hmmmm, $\pi$ is a number and $\pi$ is $\pi$...so YEAHHHHHHHH all numbers are $\pi$.

Clearly this isn't a valid proof, it hasn't proved that ALL numbers are $\pi$ since it only gives ONE possible number as an example, that happens to be $\pi$ itself.

Dr. Bob seems to make this mistake too. He has tried to prove a statement about ANY four sets and ANY two onto functions by making up one particular example.

---

EDIT: Here is a valid proof that $h$ is onto, with discussion.

What do we need to do to prove $h$ is onto? We have to show that every element of $B\times B'$ is $h$ of some element of $A\times A'$.

Ok so let's take an arbitrary element $(b,b')\in B\times B'$. Now what do we know? I know that $b = f(a)$ for some $a\in A$ (since $f$ is onto). I also know that $b' = g(a')$ for some $a'\in A'$ (since $g$ is onto).

So $h(a,a') = (f(a), g(a')) = (b,b')$. I am now done since $(a,a')\in A\times A'$ maps onto $(b,b')$, as required.

---

Do you see how the above proof would work for ANY sets and ANY onto functions? At no point did I choose a specific example!