Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

Prove or disprove the following statement: Function $f: S \rightarrow S$, where $S$ is non-empty, is bijective if and only if there exist unique functions $g, h : S \rightarrow S$ such that $$ f \circ g = f ~~~~ \text{and} ~~~~ h \circ f = f$$

Since this is a logical equivalence I need to prove both implications.

$A$ is that $f$ is bijective. $B$ that $g$ and $h$ are unique.

If I assume that $g$ and $h$ aren't unique I can use the inverse of $f$ to easily show the contradiction. How to prove $B \implies A$?

share|cite|improve this question
up vote 1 down vote accepted

Suppose $f$ is not a surjection. Say, some $a \in S$ is never reached by $f$. Then if $h$ satisfies $h \circ f = f $, modifying $h(a)$ value doesn't violate this condition, contradicting the uniqueness of such $h$. So $f$ is a surjection.

Now, for any $a \in S$, consider $A = \{x \in S: f(x)=a\}$. Let $g$ satisfy $f \circ g =f$. Then for each $b \in A$, $g(b) \in A$. Suppose $|A| \neq 1$. Then we can change the value of $g(b)$ to any element in $A$ and it will still satisfy $f \circ g =g$, violating the uniqueness of such $g$. So, $|A|=1$, hence $f$ is an injection.

share|cite|improve this answer
I think you need to consider $|S|=1$ separately, at least regarding the surjection, because if $S$ has only one element, you can't "modify" $h(a)$. – Git Gud Jan 15 '13 at 17:58
@GitGud: I agree. But it is probably too trivial, if $|S|=1$, then $f$ is always a surjection. – polkjh Jan 15 '13 at 18:02

Your Answer


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