2
$\begingroup$

If $g \circ f$ is injective, so is $g$

I don't think this is true. I think that $f$ has to be surjective.

So I am going to try to prove that:

If $g \circ f$ is injective, and $f$ is surjective, then $g$ is injective.

First off, $g \circ f$ means that $(g \circ f)(a) = (g \circ f)(b)$ then $a=b$.

And $f$ being surjective means that $\forall b \in B, \exists a\in A$ such that $f(a)=b$

Proof

Suppose that $g$ was not injective.

$g(f(a))= g(f'(a))$ and $f(a)\ne f'(a)$

But $g(f(a)) = g(f(b)) \to a=b$ $g(f(a))= g(f(b)) \to f(a)=f(b) \to a=b$ Hence contradiction, since $g$ is not injective.

So $g$ is injective.

Is this an acceptable proof, I think my logic is iffy around the second last paragraph.

$\endgroup$
1
$\begingroup$

Here is a proof which does not use contradiction.

Let $g$ be a function from $Y$ to $Z$. Suppose that $f:X\to Y$ is surjective and $(g\circ f):X\to Z$ is injective.

Let $y_1,y_2\in Y$ and suppose that $g(y_1)=g(y_2)$. Since $f$ is surjective we can write $y_1=f(x_1)$ and $y_2=f(x_2)$ for some $x_1,x_2\in X$, so $$(g\circ f)(x_1)=g(f(x_1))=g(y_1)=g(y_2)=g(f(x_2))=(g\circ f)(x_2)\ .$$ Since $g\circ f$ is injective $x_1=x_2$ and so $y_1=y_2$. Thus $g$ is injective.

$\endgroup$
  • $\begingroup$ So we use surjection to get our $y_1,y_2$ and then our injection of $g$(that was assumed) to show that it meets our injection of the $g \circ f$ Is it possible that this just describes some cases, being that it doesn't break? Would it definitely break at some point if it wasn't true(giving a contradiction to show that $g$ isn't injective) Not sure if that was clear enough $\endgroup$ – user142198 Jun 24 '14 at 1:57
  • $\begingroup$ Sorry, I don't understand what you are asking in your comment. We prove $g$ is injective by showing: if $g(y_1)=g(y_2)$ then $y_1=y_2$. $\endgroup$ – David Jun 24 '14 at 2:03
  • $\begingroup$ Sorry, yeah that is good, I prefer this proof. It is cleaner somehow. $\endgroup$ – user142198 Jun 24 '14 at 2:05
1
$\begingroup$

You wrote things in a rather messed up way; you mention something by the name of $f'$ which is left undefined; there is a $b$ which seems to have no relation to $a$. Here is a different organization:

Suppose $g$ is not injective. Then there are $a$ and $b$ in the domain of $g$ such that $g(a)=g(b)$ and $a\neq b$. Now $f$ is surjective, so there are $x$ and $y$ in the domain of $f$ such that $f(x)=a$ and $f(y)=b$. Then $$g(f(x))=g(a)=g(b)=g(f(y))$$ and $x\neq y$, because $f(x)=a\neq b=f(y)$. This is impossible if $g\circ f$ is injective.

$\endgroup$
  • $\begingroup$ Thank you. So your contradiction exists by putting the surjection of $f$ into $g(f)$ and showing that this can only be the case if injection is held by $g$ $\endgroup$ – user142198 Jun 24 '14 at 2:23

Your Answer

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