2
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ Are your domains and codomains finitely large, or can they be infinite? $\endgroup$
    – DHMO
    Apr 16 '17 at 21:48
  • 1
    $\begingroup$ Because if they can be infinite, then take $f:\Bbb N \to \Bbb N$ and $g:\Bbb N \to \Bbb N$, and $f(n) = n+1$, and $g(n) = n-1$ with $g(0)$ being arbitrary. $\endgroup$
    – DHMO
    Apr 16 '17 at 21:49
  • $\begingroup$ You mentioned a proof online. Can you reference the proof? $\endgroup$
    – DHMO
    Apr 16 '17 at 21:50
  • $\begingroup$ And if they need to be finite, take $f:\{0\} \to \{0,1\}$ and $g:\{0,1\} \to \{0\}$, with $f$ being 1 of the 2 allowed functions and $g$ being the only allowed function. $\endgroup$
    – DHMO
    Apr 16 '17 at 21:52
  • $\begingroup$ @DMHO, I added a link to the proof in the main body, but to save time it's math.dartmouth.edu/~jvoight/Fa2011-52/052-F11-HW26-solns.pdf $\endgroup$ Apr 16 '17 at 21:53
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

Neither diagram works properly. For the first, $g \circ f$ is not surjective as the middle element of $Z$ is not the image of any element of $X$. This can be patched up by deleting the middle element of $Z$ and sending the middle element of $Y$ to one of the other two elements of $Z$. For the second, $g \circ f$ is not injective as $x_1$ and $x_2$ map to the same element. It is true that if $g \circ f$ is injective then $f$ must be. If $f$ maps to elements to the same element of $Y$, $g \circ f$ must necessarily map them both to the same element of $Z$.

$\endgroup$
2
  • $\begingroup$ My teacher didn't explain how to draw any of this. I just assumed that the (g o f) part was the Y->Z part. But if it's the whole thing, X->Y->Z, then isn't X->Y implicitly also bijective? I understand that what I drew was wrong, but I don't understand what the right way is $\endgroup$ Apr 16 '17 at 22:16
  • $\begingroup$ Your drawings are fine representations of functions. $g$ is the $Y \to Z$ part. $g \circ f$ is a function $X \to Z$. It can't be surjective, as $X$ has only two elements, so the image of $X$ can have no more than two elements and $Z$ has three. Your $g$ is surjective, but that isn't the question we are asked. In essence, when studying $g \circ f$ what happens in $Y$ doesn't matter at all. $\endgroup$ Apr 17 '17 at 3:12
0
$\begingroup$

Your first diagram doesn't have $g\circ f$ surjective, so it's not bijective a fortiori. In the second diagram, $g\circ f$ is not injective.


Keep it simple, at least at first. If things don't work, you can always go for bigger examples.

Let $f\colon\{0\}\to\{1,2\}$ be defined by $f(0)=1$; let $g\colon\{1,2\}\to\{3\}$ be the unique map.

Then $g\circ f\colon\{0\}\to\{3\}$ is obviously bijective.

Thus there's no way you can prove that $g\circ f$ surjective implies $f$ surjective. (It is true that, if $g\circ f$ is surjective, then $g$ is surjective, though.)

The same maps prove that $g\circ f$ injective doesn't imply $g$ is injective.

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