7
$\begingroup$

Let $f:A\rightarrow B$ and $g:B\rightarrow C$ be functions, prove that if $g\circ f$ is injective and $f$ is surjective then $g$ is injective.

I need advise or correction if something is incorrect with my proof. Thank you beforehand.

We must show that $g$ is injective, i.e for $x,y\in B, g(x)=g(y)\implies x=y$

Let $x,y\in B$ such that $g(x)=g(y)$. Because $f$ is surjective there exists $a,b \in A$ such that $f(a)=x$ and $f(b)=y$

$\implies g(f(a))=g(f(b))$

$\implies g\circ f(a)=g\circ f(b)$

$\implies a=b$ (by injectivity of $g\circ f$)

$\implies f(a)=f(b)$

$\implies x=y$

Would appreciate any correction in proof writing also!

$\endgroup$
  • 4
    $\begingroup$ This is correct. $\endgroup$ – Mr.Fry Dec 14 '13 at 6:08
  • $\begingroup$ I was suspicious with the last two implications, didn't know if they were true but it seems there is no problem. Thank you Faraad! $\endgroup$ – AndreGSalazar Dec 14 '13 at 6:24
  • $\begingroup$ @AndrewGSM, it is a general principle that if $a=b$, then $f(a)=f(b)$, so long as $f$ is a function and both $a$ and $b$ are elements of the domain of $f$. $\endgroup$ – goblin Dec 14 '13 at 11:25
5
$\begingroup$

Your proof is correct. I myself would prove it exactly the same. But, I think it's useful to know more than one way, so here is an alternative solution. It's not profoundly different, but I think it's still worth mentioning.

I'm assuming that $A$ is nonempty (and, since there is a map from $A$ to $B$, $B$ is also nonempty). When $A$ is empty there's not much to prove.

The solution uses left and right inverses. A function with non-empty domain is injective iff it has a left inverse, and a function is surjective iff it has a right inverse.

So, we know that $g\circ f$ has a left inverse $h:C \to A$ and $f$ has a right inverse $k: B \to A$. We want to show that $g$ has a left inverse. Just observe that $$ (f \circ h) \circ g = (f \circ h) \circ g \circ (f \circ k) = f \circ (h \circ g \circ f) \circ k = f \circ \mathrm{id}_A \circ k = f \circ k = \mathrm{id}_B, $$ so $(f \circ h)$ is a left inverse for $g$. It follows that $g$ is an injection.

PS: this solution is actually worse than your original one, because this one relies on the axiom of choice (it is used when we say that surjectivity is equivalent to having a right inverse). But it is good in the sense that we don't look at particular elements and manipulate maps as "opaque" objects.

$\endgroup$
  • $\begingroup$ You write: "a function is injective iff it has a left inverse." This isn't quite right; it should be "a function is injective iff its domain is empty, or it has a left inverse." $\endgroup$ – goblin Dec 14 '13 at 11:27
  • $\begingroup$ @user18921 You are right. Nice catch! I've made the correction. $\endgroup$ – Dan Shved Dec 14 '13 at 12:07
  • $\begingroup$ If you weaken $f$ having a right inverse to $f$ being epic, is it still possible to show that $g$ is monic? I haven't been able to find a way to do it, but I also don't know that it can't be done (especially if you use products/coproducts). $\endgroup$ – dfeuer Dec 14 '13 at 18:52
  • $\begingroup$ Another idea: although AC is needed to prove that an onto mapping has a right inverse, it's not necessary to show that a one-to-one and onto mapping has an inverse. $\endgroup$ – dfeuer Dec 14 '13 at 19:13
2
$\begingroup$

I need advise or correction if something is incorrect with my proof.

Your proof is good!

Would appreciate any correction in proof writing also!

To this, I would respond: its good to read different people's writing just for style. So here's my version of the proof, which is logically similar to yours but just differs on a few stylistic dimensions.

A few noteworthy points:

  • You may prefer to write function arrows "backwards", as in $f : B \leftarrow A.$ See below.
  • A fraction line can be used to mean "implies," see below.
  • I prefer ending sentences without a big mass of symbols, using phrases like "as follows" and "below," and then putting the symbols immediately afterwards. See below.
  • The word "fix" is a nice alternative to "let" when the latter has the right "basic meaning" but doesn't work grammatically. See below.
  • If you're going to have a sequence of implications, I'd suggest making it as long as possible, and omitting the symbol $\implies.$ See below.

With that said, here's the proof:

Proposition. Let $g : C \leftarrow B$ denote a function and $f : B \leftarrow A$ denote a surjection. Then whenever $g \circ f$ is injective, so too is $g$.

Proof. Assume that $g \circ f$ is injective, and fix $b,b' \in B.$ The following implication will be proved. $$\frac{g(b)=g(b')}{b=b'}$$

Since $f$ is surjective, begin by fixing elements $a,a' \in A$ satisfying the equations immediately below.

$$b = f(a),\;\; b'=f(a')$$

Then each statement in the following sequence implies the next.

  1. $g(b)=g(b')$
  2. $g(f(a)) = g(f(a'))$
  3. $(g \circ f)(a) = (g \circ f)(a')$
  4. $a=a'$
  5. $f(a)=f(a')$
  6. $b=b'$.
$\endgroup$
1
$\begingroup$

Here is alternative method

note that : $$ g\circ f \mbox{ injective } \implies f \mbox{ injective } $$ we have :

  • $ f \mbox{ is injective and surjective } \implies f \mbox{ bijective (one-to-one correspondence) } $

Since $f$ is a bijection, it has an inverse function $f^{-1}$ which is itself a bijection.

  • $f^{-1} \mbox{is bijective} \implies f^{-1} \mbox{ injective } $
  • $$ \begin{cases} g\circ f \mbox{ injective } & \\ f^{-1} \mbox{ injective } & \\ f^{-1}(B)\subset A &\\ \end{cases} \implies g\circ f \circ f^{-1} \mbox{ injective}$$

  • Since $$\forall x\in B \qquad \begin{align} (g\circ f)\circ f^{-1}(x)&=g\circ (f\circ f^{-1})(x)\\ &=g\circ {\rm id}_{B}(x)\\ &=g({\rm id}_{B}(x))\\ (g\circ f)\circ f^{-1}(x)&=g(x)\\ \end{align}$$ then $$(g\circ f)\circ f^{-1}=g$$ since $(g\circ f)\circ f^{-1}$ injective then $g$ is injective

$\endgroup$
0
$\begingroup$

I've proved it on my own like this:

Pick two arbitrary elements of $B$, $y_1$ and $y_2$, with $g(y_1)=g(y_2)$. Since $f$ is surjective, $y_1=f(x_1)$ and $y_2=f(x_2)$ for some $x_1,x_2 \in A$. Then $g(f(x_1))=g(f(x_2))$. Since $f \circ g$ is injective, $x_1=x_2$, and so $f(x_1)=f(x_2)$, or $y_1=y_2$. Finally, $g$ is injective.

$\endgroup$
  • $\begingroup$ Seems to be exactly the same proof as the one in the question and in goblin's answer. Please consider whether you're contributing something new before answering, particularly given that (1) this question already has an accepted answer, and (2) the question is 3 years old. $\endgroup$ – epimorphic Feb 3 '17 at 23:44
  • $\begingroup$ Of course I'm contributing something new, and I always consider it. My proof doesn't look like the others at all... And ironically, two of the other answers recommended OP reading different styles of proofs... So yeah, I'm contributing to future people who stumble here looking for help. And, also, the three answers are basically "your proof is correct, here's an alternative proof/how I did it". Also, are you a moderator? $\endgroup$ – anon Feb 4 '17 at 15:28
  • $\begingroup$ The two answers by others not prefaced with "here's my version of the proof, which is logically similar to yours but just differs on a few stylistic dimensions" each have a different sequence of implications, not just a different "style". That's what the "more than one way" in the first answer usually means, and what "I've proved it on my own like this" seems to suggest to me. I'd be willing to reverse my vote if you would explicitly say something like "here's a more prose-like style". $\endgroup$ – epimorphic Feb 4 '17 at 19:08
  • $\begingroup$ To answer your last question: Primary moderation on this site is provided by the community. IIRC I found your answer through the review queues, where the only posts visible are this answer, the question, and any attached comments. And here's an answer to an old question that claims "I've proved it on my own like this" and yet looks logically identical to the proof in the OP... $\endgroup$ – epimorphic Feb 4 '17 at 19:08

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.