2
$\begingroup$

Could someone verify my proof?

Proposition: Let $ f: X \rightarrow Y $ and $ g: Y \rightarrow Z $ be functions. Show that, if $ g(f(x)) $ is injective and $ f $ is surjective, then $ g $ is injective.

Proof: Let $ g(f(x)) $ be injective. So, for all $ x_1, x_2 \in X $, if $ x_1 \neq x_2 $, then $ g(f(x_1)) \neq g(f(x_2)) $. By the definition of function, that implies $ f(x_1) \neq f(x_2) $, hence $ f $ is injective.

Since $f$ is injective, for all $ x_1, x_2 \in X $, if $ x_1 \neq x_2 $, then $ f(x_1) \neq f(x_2) $ and, since $ f $ is surjective (for all $ y_1, y_2 \in Y , \exists x_1, x_2 \in X $ such that $ y_1 = f(x_1) $ and $ y_2 = f(x_2) $), then $ y_1 \neq y_2 $. So, $ x_1 \neq x_ 2 \Rightarrow y_1 \neq y_2 \Rightarrow g(y_1) \neq g(y_2) $. Therefore, g is injective.

Q.E.D.

$\endgroup$
  • $\begingroup$ Looks good to go. $\endgroup$ – Adam Hughes Sep 9 '14 at 20:45
  • $\begingroup$ Looks ok too but you can also notice that $g=(g\circ f)\circ f^{-1}$ :). $\endgroup$ – Krokop Sep 9 '14 at 20:50
1
$\begingroup$

The general idea of your proof is ok, but in the second paragraph you didn't say what are $y_1$ and $y_2$. You should the second paragraph by writing "let $y_1, y_2 \in Y$ such that $y_1 \neq y_2$" or something like that.

I would change it to: Let $y_1, y_2 \in Y$ and suppose $y_1 \neq y_2$. We must show that $g(y_1)\neq g(y_2)$. Since $f$ is surjective, there exists $x_1, x_2 \in X$ such that $f(x_1)=y_1$ and $f(x_2)=y_2$. Since $y_1 \neq y_2$, it follows that $x_1 \neq x_2$. Therefore $g(y_1)=g(f(x_1))\neq g(f(x_2))=g(y_2)$ and the proof is complete.

Notice that I didn't need to show that $f$ is injective.

$\endgroup$
2
$\begingroup$

The second paragraph has a bit of a problem, since you don't really define $y_1,y_2$. Also, I would use the contrapositive of the injective definition, since equal signs are generally easier to work with. Here's my version.

Choose any $y_1,y_2 \in Y$ such that $g(y_1) = g(y_2)$. We want to show that $y_1 = y_2$. Indeed, notice that since $f$ is surjective, we know that there exist $x_1,x_2 \in X$ such that $y_1 = f(x_1)$ and $y_2 = f(x_2)$. Substituting, we know that $g(f(x_1)) = g(f(x_2))$. But since $g(f(x))$ is injective, we know that $x_1 = x_2$. Thus, since $f$ is a well-defined function, it follows that $f(x_1) = f(x_2)$ so that $y_1 = y_2$, as desired.

$\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.