One-to-One and Onto Proof

Question

I am having a hard time wrapping my head around the logic behind a proof to a problem in Velleman's "How to Prove It." I feel I've found a logical error due to the problem not being specific enough. Note there is no official solution to this problem so what I have thus far is the best I've been able to come up with.

The problem:
Suppose $f: A\rightarrow B$ and $g:B\rightarrow C$. Prove that if $f$ is onto and $g$ is not one-to-one, then $g \circ f$ is not one-to-one.

My proof:
Suppose $f$ is onto and $g$ is not one-to-one. If $g$ is not one-to-one, then $g(y_1)=g(y_2)$ and $y_1\neq y_2$. Hence $(y_1,g(y_1)=g(y_2))$ and $(y_2,g(y_1)=g(y_2))$ are elements of $B\times C$. If $f$ is onto then $\forall y\in B\exists x\in A(g(x)=y)$. It follows that $(x,y_1),(x,y_2)\in A\times B$.

This is where I am lost. If I continued the proof with what I have, I would only prove that $(x,g(y_1)=g(y_2))\in A\times C$, which says nothing about whether or $g \circ f$ is one-to-one. Such an approach would only work if I let the $x$-values in my last part be unique. In fact, this is what others who have posted solutions on the internet did to complete the proof. This leads me to my problem and the possible logical error: $f$ being onto says nothing at all about its input values having unique corresponding output values. In fact, as best as I can tell, it's equally possible for the function $f$ to have $x$-values such that $(x,y_1),(x,y_2)\in A\times B$ (i.e. the same $x$-value) or $(x_1,y_1),(x_2,y_2)\in A\times B$ $\land$ $x_1 \neq x_2$ (i.e. unique $x$-values, the technique others have used). I cannot assume one or the other without more information. Am I missing something or are the instructions in this problem incomplete?

Answer 1

You may have made your life too complicated. You are also disregarding that $g$ and $f$ are functions: necessarily, this means that any given input value can only have one output value.

Because $g$ is not one-to-one, there exist $b_1,b_2\in B$, $b_1\neq b_2$, so that $g(b_1)=g(b_2)$.

Because $f$ is onto, there are $a_1,a_2\in A$ such that $f(a_1)=b_1$ and $f(a_2)=b_2$. Note that, necessarily, $a_1\neq a_2$: otherwise, $a_1=a_2$ implies $b_1=f(a_1)=f(a_2)=b_2$, contradicting the fact that $b_1\neq b_2$.

But, we then have $$ g\circ f(a_1)=g(b_1)=g(b_2)=g\circ f(a_2), $$ proving that $g\circ f$ is not one-to-one.

Answer 2

I think you're overcomplexifying the proof.

If g is not 1-1, then there are distinct elements m,n in B, such that g(m)=g(n)=p for some p in C.

Since f is onto, then there are distinct elements u,v in A such that f(u)=m and f(v)=n.

Therefore g o f(u) = g(m) = p = g(n) = g o f(v). So g o f is not 1-1.

Answer 3

$g:B\to C$ is not one to one. So there exist $y_1, y_2 \in B; z \in C$ so that there $g(y_1) = g(y_2)$ and $(y_1, z), (y_1, z) \in g = \{(y,g(y)|y\in B\}\subset B \times C$.

$f:A\to B$ is onto so there exist $x_1 \in A$ so that $f(x_1) = y_1$ and $x_2 \in A$ so that $f(x_2) = y_2$.

(You were trying to get that somehow $y_1$ is equivalent to $y_2$ (because $g(y_1) = g(y_2)$) and therefore somehow there is a single $x$ so that $f(x) = y_1$ and $f(x) = y_2$. But that is nonsense and violates the very definition of function.)$

As $y_1 \ne y_2$ and $f$ is a function $x_1\ne x_2$. (otherwise $y_1 = f(x_1) = f(x_2)=y_2$).

So $(x_1, y_1),(x_2, y_2) \in f=\{(x,f(x))|x \in A\} \subset A\times B$.

And therefore $g\circ f(x_1) = g(y_1) = z$ and $g\circ f(x_2) = z$ and $(x_1, z), (x_2, z) \in g\circ f=\{(x,g\circ f(x))|x \in A\} \subset A\times C$.

So $g\circ f$ is not one-to one.

.....

Actually, I'm not sure what significance $(y_1, g(y_1)=g(y_2)) \in B \times C$ was supposed to have. As ANY $b \in B; c\in C$ will yield $(b,c) \in B \times C$ regardless of what $g(b) $ is or whether there is any $y$ so that $g(y) = c$ or not, that doesn't have any significance.

I assumed you were thinking that $g \subset B\times C$ where $(y, g(y)) \in g$. (That is $f = \{(x,y)\in A\times B| y = f(x)\}$ and $g = \{(y,z) \in B\times C|g(y) = z\}$ and $g\circ f = \{(x,z)\in A\times C|g(f(x)) = z\}$.

If so then a simple proof follows:

$g$ is not one to one mean there exist $y_1,y_2, z$ so that $(y_1, z),(y_2,z) \in g$.

$f$ is onto so there exists $x_1,x_2$ so that $(x_1,y_1), (x_2,y_1) \in f$ and therefore by definition of $g\circ f = \{(x,z)\in A\times C| \exists y\in B: (x,y) \in f, (y,z) \in g\}$ we have $(x_1,z),(x_2,z)\in g\circ f$.

So $g\circ f$ is not one-to-one.