Take the 2-minute tour ×
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.

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|improve this question
add comment

1 Answer 1

up vote 2 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|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
add comment

Your Answer

 
discard

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.