13
$\begingroup$

The Problem:

Let $X, Y, Z$ be sets and $f: X \to Y, g:Y \to Z$ be functions.

(a) Show that if $g \circ f$ is injective, then so is $f$.

(b) If $g \circ f$ is surjective, must $g$ be surjective?

Where I Am:

So, I really have trouble with these, for some reason. I can draw pictures and make sense of the problems, but writing down proofs is very difficult for me.

Basically, for (a), I ended up with some complicated statement involving an implication implying another implication and then tried to derive a contradiction. It just got so convoluted that I couldn't make sense of it anymore, and I know there's a quick, elegant way to show it.

For (b), I know that $g$ need not be surjective. Once again, though, proving it directly from definitions has given me a bit of a headache.

Any help here would be appreciated. Thanks in advance.

The Proofs!

Ok, I did it. Thanks for the help, everyone! Let me know if there's anything wrong with these proofs, or if they could bet any better.

(a) Suppose $f$ is not injective. Then $$ f(x_1)=f(x_2) \implies x_1 \ne x_2 \text{ }(*).$$ Let $f(x_1)=y_0=f(x_2)$ and let $g(y_0)=z_0$. Then $$ (g \circ f)(x_1) = (g \circ f)(x_2) = g(y_0) = z_0. $$
Since $g \circ f$ is injective, $$ (g \circ f)(x_1) = (g \circ f_2) \implies x_1 = x_2. $$ However, this contradicts $(*)$. Therefore, $f$ must be injective.

(b) Suppose $g$ is not surjective. Then

$$ \forall y \in Y, \exists z \in Z \text{ such that } g(y) \ne z \text{ }(**).$$

Since, $g \circ f$ is surjective,

$$ \forall z \in Z, \exists x \in X \text{ such that } g(f(x)) = z \text{ } (***). $$

Let $f(x) = y$. Then,

$$ g(f(x)) = g(y) = z. $$

Because of $(***)$, this is true for all $z \in Z$, which contradicts $(**)$. Therefore, $g$ must be surjective.

$\endgroup$
12
$\begingroup$

(a) Let $f(x_1)=f(x_2)$. Then, $g(f(x_1))=g(f(x_2))$, but since $g\circ f$ is injective...

(b) $g(Y)\supseteq (g\circ f)(X)=g(f(X))$. Hence, if $(g\circ f)(X)=Z$...

$\endgroup$
  • $\begingroup$ @:G. Sassatelli ,here is my approach for part b)please correct me if i am wrong $\text{Assume that }\,\, x\epsilon X\,,y\epsilon Y\,,z\epsilon Z\,\,. \text{As}\, g \circ f\,is\,\,surjective\,\Rightarrow g\circ f\left ( x \right )=z. But\,\, g\circ f \left ( x \right )\subseteq g\left ( y \right )\Rightarrow g\left ( y \right )=z\Rightarrow g\,\,is\,\,surjective$ $\endgroup$ – virat Mar 26 '17 at 7:21
  • $\begingroup$ @sourav No, you are mixing the notations for equality of elements and set inclusion. Moreover, you are misusing quantifiers. You either prove that, since for any $z\in Z$ there is $x$ such that $g(f(x))=z$, then $f(x)$ is a valid preimage of $z$ under $g$, or you use my hint about the double inclusion $Y\supseteq g(Y)\supseteq g(f(X))=Y$. $\endgroup$ – user228113 Mar 26 '17 at 8:36
3
$\begingroup$

Suppose that $f$ is not injective, then there are $x,y$ such that $y\neq x$ and $f(x)=f(y)$, then we have $g\circ f(x)=g(f(x))=g(f(y))=g\circ f(y)$ which means that $g\circ f$ is also not injective. then by contrapositive we get $g\circ f$ injective $\implies f$ injective as well.

$\endgroup$
2
$\begingroup$

Hint: In each case the contrapositive is obvious.

$\endgroup$
  • 2
    $\begingroup$ OK, it's a hint. $\endgroup$ – Bernard May 10 '15 at 1:12
1
$\begingroup$

You're probably thinking too hard. For the first one, if $f$ weren't injective, then two elements of $X$ go to the same $y\in Y$. That can only go to one thing in $Z$ so now the composition $g\circ f$ can't be injective after all.

You can reason similarly for surjectivity of $g\circ f$ implying surjectivity of $g$

As an additional exercise, can you see why these statements don't work of you try to prove them for $g$ and $f$, respectively?


If you do it directly, think like this. If $f(x_1) = f(x_2),$ then $g(f(x_1))$ had better equal $g(f(x_2))$, so by injectivity of the composition ...

$\endgroup$
-1
$\begingroup$

(a) Proof:

Since the composite function $g\circ f$ is injective, we have $(g\circ f)(x_{1})=(g\circ f)(x_{2})\implies x_{1}=x_{2}.$ Thus, it follows that $f$ must be injective; otherwise, it would contradict the fact that $(g\circ f)$ is. $\square$

(b) Proof:

If $g \circ f$ is surjective, $\forall z\in Z,\exists x\in X : (g\circ f)(x)=z.$ Let $y=f(x)$, so $y\in Y$ (since $f:X\to Y$). Then, $g(y)=g(f(x))=(g\circ f)(x)=z$, thus, $g$ is surjective. $\square$

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