Example where $f\circ g$ is bijective, but neither $f$ nor $g$ is bijective

Can anyone come up with an explicit example of two functions $f$ and $g$ such that: $f\circ g$ is bijective, but neither $f$ nor $g$ is bijective?

I tried the following: $$f:\mathbb{R}\rightarrow \mathbb{R^{+}}$$ $$f(x)=x^{2}$$

and $$g:\mathbb{R^{+}}\rightarrow \mathbb{R}$$ $$g(x)=\sqrt{x}$$

$f$ is not injective, and $g$ is not surjective, but $f\circ g$ is bijective

Any other examples?

• $f:\mathbb R\to\mathbb R^+$, $x\mapsto|x|$, $g:\mathbb R^+\to\mathbb R$, $x\mapsto x$. – Did Sep 18 '12 at 5:05

The simplest example:

• $X=\{0\},Y=\{0,1\}$, $f(0)=0$, $g(0)=g(1)=0$.

(Here $g\circ f$ is the bijection, since I inadvertently reversed the names of the functions.)

Everything else is an elaboration of one of this idea.

• In example (1), if I am reading it correctly, $f \circ g$ is not a bijection; it is the function $\{0,1\} \to \{0,1\}$ that is always zero. The reverse composition $g \circ f$ is a bijection, but that's just the same as example (2), isn't it? – Trevor Wilson Sep 18 '12 at 5:33
• @Trevor: Thanks. I inadvertently had examples for both compositions, having temporarily forgotten which way round the OP had chosen, and when I got back from answering the bloomin’ phone I’d forgotten that one of them needed to be scrubbed. – Brian M. Scott Sep 18 '12 at 5:47

If we define $f:\mathbb{R}^2 \to \mathbb{R}$ by $f(x,y) = x$ and $g:\mathbb{R} \to \mathbb{R}^2$ by $g(x) = (x,0)$ then $f \circ g : \mathbb{R} \to \mathbb{R}$ is bijective (it is the identity) but $f$ is not injective and $g$ is not surjective.

If $X$ is any set at all with $\left| X \right| > 1$ then the diagonal map

\begin{align}\Delta : X &\to X \times X \\ x &\mapsto (x,x)\end{align}

and the projection map

\begin{align}\pi : X \times X &\to X\\ (x,y) &\mapsto x \end{align}

satisfy $\pi \circ \Delta = \text{id}_X$, which is bijective, and yet neither $\Delta$ nor $\pi$ is bijective.

In a similar vein, if $f : X \to Y$ is any function and $\left|Y\right| > 1$ then we can take the graph $\Gamma_f : X \to X \times Y$ given by $\Gamma_f(x) = (x,f(x))$ and the same projection. The above example is the special case where $f(x)=x$.

An example with the aditional restriction that there is only one set involved, i.e. we have $f\colon X\to X$ and $g\colon X\to X$ is given by $$f\colon\mathbb N_0\to\mathbb N_0, n\mapsto \max\{n-1,0\}$$ $$g\colon\mathbb N_0\to\mathbb N_0, n\mapsto n+1$$ (Clearly, $X$ cannot be finite, so this example is sort minimal with my additional restriction)

$f(x)=2x$ and $g(x)=x/2$ will do for integers (round in some way for odd numbers).

• Interestingly, your functions are bijections, but on different domains and codomains. – akkkk Sep 18 '12 at 13:00
• You've mixed up $f$ and $g$: $g\circ f$ is the bijection. For maximum clarity, you should say which is not injective ($g$) and which is not surjective ($f$) or at least what the bijection is. – robjohn Sep 19 '12 at 15:46