0
$\begingroup$

Let $f : X \to Y$ and $g: Y \to Z$ be two functions, such that $(g \circ f) : X \to Z$ is bijective

Prove or refute that $f$ is surjective.

$\\$

For $f$ to be surjective, $\forall b \in Y, \exists a \in X : f(a) = b$

Because $(g \circ f)$ is bijective, the sets X and Z have to have the same number of elements, otherwise the function composition wouldn’t be bijective.

The set Y can have the same number of elements than X and Z or more. It can’t have less, because given that $g \circ f $ is bijective, in other words that X and Z have the same number of elements, the elements in X can map to a smaller number of elements in Y, but the elements in Y can’t map to more elements in Z than there are in Y.

So the function $f$ isn’t necessarily surjective. It could be, but it isn’s necessarily the case.

Are my thoughts correct or not ? If not, why ?? Also, if I am right, how could I write a mathematical proof ?

Thanks for your help !

(P.S. : English isn't my mother tongue, sorry if I made a grammar mistake)

$\endgroup$
  • 3
    $\begingroup$ It would be better to come up with a very specific and explicit counterexample. Hint: One such counterexample happens with $X=\{1\}, Y=\{1,2\}$ and something appropriate for $Z$ and an appropriate choice for $f$ and $g$. $\endgroup$ – JMoravitz Jul 6 '17 at 19:06
  • $\begingroup$ Can you make an example of sets $X,Y,Z $ and functions $f ,g $ where$f $ is not surjective? $\endgroup$ – Mark S. Jul 6 '17 at 19:07
  • $\begingroup$ If X={1}, Z = {1} but Y = {1,2}, and $f$ and $g$ both map to the same number as the input (so it maps from 1 to 1, 2 to 2, and so on), then $f$ isn't surjective. Is that correct ? $\endgroup$ – Poujh Jul 6 '17 at 19:19
  • $\begingroup$ Yes, that's right. $\endgroup$ – Mundron Schmidt Jul 6 '17 at 19:25
  • $\begingroup$ @Poujh it is almost correct, but the way you have written it (in particular saying it maps 2 to 2) is misleading since $2$ is not in the codomain of $g$. The only possible image in $g$ is the only element in $Z$, namely $1$. The example I was trying to lead you towards is where $f(x)=1$ for all $x$ and $g(x)=1$ for all $x$. $\endgroup$ – JMoravitz Jul 6 '17 at 22:15
1
$\begingroup$

Your thoughts are not bad at all, but it seems that you think of $X$, $Y$ and $Z$ as finite sets. This is enough to give a counterexample. You realized that $Y$ has to have at least the same "number" of elements as $X$. But what if $Y$ has more elements? Can $f$ be surjective?

In general, you have to be careful with

Because $(g\circ f)$ is bijective, the sets $X$ and $Z$ have to have the same number of elements, otherwise the function composition wouldn’t be bijective.

Define $A=[0,\infty)$ and $B=[1,\infty)$ and $$ h:A\to B,~h(a)=a+1. $$ Then $h$ is bijective although $B\subsetneq A$.

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