Suppose $f \circ g$ is one-to-one and $f$ is not one-to-one. Show that $g$ is not onto.

Question

Given $A,B,C$ are sets and $g$ and $f$ are functions such that $g: A\rightarrow B, f: B\rightarrow C$.

Intuitively, I can ambiguously argue why this is true with a couple of sketches, but I'm having trouble proving this formally.

My proof goes as follows: (by contradiction)

Suppose $f \circ g$ is injective, $f$ is not injective and $g$ is surjective. I want to show this is impossible.

Let's assume we found $a,a'\in A$ such that $(f\circ g)(a) = (f\circ g)(a') \iff f\big(g(a)\big) = f\big(g(a')\big)$

Well, we know $g$ is surjective, that means for all $b\in B$, there exists $a \in A$ such that $g(a) = b$, thus we can conclude that both $g(a),g(a')$ are in B.

So we know there exists $b, b'\in B$ such that $b = g(a)$ and $b' = g(b') \iff f(b) = f(b')$

Now this is where I feel like I can create the contradiction by saying there exists $b$ and $b'$ such that $f(b) = \big(f(b')\big)\implies b \not= b'.$ (Given $f$ is not $f$ is not injective).

But how do I do this? I can show that $b \not= b'$, but how can I use that to show that there exists $a, a' \in A$ such that $(f \circ g)(a) = (f\circ g)(a') \implies a \not= a'$, thus raising that contradiction?

Thanks,

Answer 1

Your starting assumption

Let's assume we found some a,a' in A such that (f o g)(a) = (f o g)(a')

is problematic. What contradiction could possibly arise from that?

Instead, get the contradiction from the assumptions of the hypothesis together with the assumption that $g$ is surjective.

Here's one way . . .

Assume $g:A\to B$, and $f:B\to C$ are such that

• $f{\,\circ\,}g$ is injective.
• $f$ is not injective.
• $g$ is surjective.

Our goal is to derive a contradiction.

Since $f$ is not injective, there exist $b,b' \in B$, with $b\ne b'$ such that $f(b)=f(b')$.

Since $g$ is surjective, there exist $a,a'\in A$, such that $g(a)=b$, and $g(a')=b'$,

Since $b\ne b'$, we have $g(a)\ne g(a')$, hence, since $g$ is a function, it follows that $a\ne a'$.

But then $$(f{\,\circ\,}g)(a) = f(g(a)) = f(b) = f(b') = f(g(a'))=(f{\,\circ\,}g)(a')$$ so we have $a\ne a'$, and $(f{\,\circ\,}g)(a) = (f\circ g)(a')$, contrary to assumption that $f{\,\circ\,}g$ is injective.

Answer 2

If $f$ is nor one-to-one, then there exists $a\ne b, f(a)=f(b).$ If we assume by way of contradiction that $g$ is surjective, then there are $c,d$ such that $g(c)=a, g(d)=b.$

Take it from here.