# If a composition of functions is injective, must its components be injective?

Assume that we have one on one function, that look like that:

$$f(g(x))$$

We need to proof or dis-proof that:

I.f is one on one.

II.g is one on one.

I know the answer on booth questions, but my question is how can I show the function g isn't one on one(not by showing an сounter example).

Any help will be appreciated!

-
Hint: A) If $g(1)=g(2)$, how can you choose $f$ such that $f(g(1))\neq f(g(2))$. B) What if the domain of $g$ consists of a single point only? – Jyrki Lahtonen Sep 18 '13 at 16:18

Assume $g(x)=g(y)$. Then $f(g(x))=f(g(y))$, hence $x=y$ because $f\circ g$ is injective. Thus $g$ is injective.

On the other hand, unless the function $g$ is onto, there is no reason for $f$ to behave nicely in places $g$ can't see. You'll easily find a counterexample using this intuition.

As a sidenote, I doubt there is a nice way of doing the part about $f$ without giveing a counterexample. After all, what has to be done is to show that $f$ is not necessarily injective (of course it is possible that $f$ is injective). In other words, we have to show that there exist functions $f$ and $g$ (with appropriate domains and codomains) such that $f\circ g$ is injective and $f$ is not injective). The simples existence proof is always a proof by example (though it may not be easy to find a counterexample).

The alternative would be a non-constructive existence proof, based ultimately on the Axiom of Choice. As the Axiom of Choice does not play a role for finite cases, it is hard to imagine that there is any nice proof along that path, given that a specific counterexample can be found in the realm of sets with two elements (the smallest cardinality where non-injective functions exist):

Let $B$ be a two element set, let $C$ be a singleton set, let $f$ be the only function $B\to C$. Then $f$ is not injective. Let $g$ be the only function $\emptyset\to B$. Then $f\circ g$ is vacuously injective.

-
+1, mainly for the statement there is no reason for $f$ to behave nicely in places, $g$ can't see. – Andreas Caranti Sep 18 '13 at 16:17