0
$\begingroup$

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,

$\endgroup$
  • $\begingroup$ The line "Let's assume we found some a,a' in A such that (f o g)(a) = (f o g)(a')" doesn't make much sense. You just assumed that $f\circ g$ is injective, so we know $a=a'$. $\endgroup$ – saulspatz Apr 11 '18 at 23:22
  • $\begingroup$ Yes, but I also want to show it cannot be the case in general. See, that's what I'm trying to lead to, I have explicitly put that up to bring that 'that does not make sense moment', a.k.a contradiction. $\endgroup$ – Florian Suess Apr 11 '18 at 23:25
  • $\begingroup$ You have just assumed that it cannot be the case, in the previous sentence. It would be very easy to prove things if you were just allowed to assume they are true. $\endgroup$ – saulspatz Apr 11 '18 at 23:31
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.