Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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!

share|cite|improve this question
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.

share|cite|improve this answer
+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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.