Set Theory – Prove: If $(g \circ f)$ is Bijective, is $f$ Bijective?

elementary-set-theoryfunctionsproof-writing

I need to prove or disprove for a discrete mathematics assignment the following statement:

$(g \circ f)$ is bijective $\rightarrow$ $f$ is bijective, $f: X \rightarrow Y$ $\hspace{.5cm} g:Y\rightarrow Z$

All of the domains and codomains here are supposed to be the real numbers.

I'm having a hard time understanding how to prove things about functions, which we just got into.

I assume that I need to break this into two cases, those cases being to prove or disprove:

  1. $(g \circ f)$ is injective $\rightarrow$ $f$ is injective

  2. $(g \circ f)$ is surjective $\rightarrow$ $f$ is surjective

I've been playing around with drawing different circle diagrams for $X$, $Y$ and $Z$. For $f(x)$, I drew diagrams where $|X|$ < $|Y|$, where $|X|$ = $|Y|$, and where $|X|$ > $|Y|$, and for $g(f(x))$, I did the same for $Y$ and $Z$.

It appears to me that when $(g \circ f)$ is surjective, $f$ is not necessarily surjective, because you could draw the functions out like this:

onto

This makes sense to me as a counterexample, but I'm not sure if that's right.

Next, as for $f$ being injective when $(g \circ f)$ is injective, I found a proof (see problem 3.3.7 part a at the top of the first page) that explained that this is true, but I didn't really understand the explanation. Also, when I drew it out myself trying to find an example for which it would be false, I found this:

OnetoOne

And it seems to me to show that when $(g \circ f)$ is injective, $f$ is not necessarily injective, but that contradicts the proof that I found online.

The only two possibilities are that the proof I found was wrong, or that I'm drawing these functions and sets incorrectly and breaking some rule(s) that I'm unaware of.

Any insight into what I'm doing wrong with my drawings, my logic, or into how to go about correctly solving this problem would be hugely appreciated. Thank you all.

Best Answer

Suppose $f:X \rightarrow Y$, $g: Y \rightarrow Z$.

If $(g \circ f)$ is bijective the only things we can conclude are

  1. $g$ is surjective. For suppose $z \in Z$ is arbitrary. Then as $(g \circ f)$ is bijective, so surjective, there exists an $x \in X$ with $(g \circ f)(x) =z$. But the latter means by definition that $g(f(x)) = z$, so take $y=f(x) \in Y$, then $g(y) = z$. So any $z \in Z$ is an image of $g$, so $g$ is surjective.

  2. $f$ is injective. Suppose that $f$ is not injective. This means that there are different $x_1, x_2 \in X$ with $f(x_1) = f(x_2)$. But then

$$(g\circ f)(x_1) = g(f(x_1)) =g(f(x_2)) = (g \circ f)(x_2)$$

Which shows that $g\circ f$ is not injective ,so not bijective, contradiction. So $f$ is injective.

The conditions 1,2 are necessary for $g \circ f$ to be bijective but not sufficient: If $f$ is the identity on $X= Y = \{1,2,3\}$ and $g$ is the constant map to $Z = \{0\}$, then $g$ is surjective, $f$ is injective but $g \circ f$ is not bijective.

And if we take $X =Z = \{0,1\}, Y = \{0,1,2\}$, $f$ the identity ($f(0) = 0, f(1) =1$, and $g(0) = 0, g(1) = 1, g(2) = 1$,then $f$ is no bijection while $g \circ f$ is.

Related Question