4
$\begingroup$

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$?

$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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)$. $\endgroup$
    – Git Gud
    Jan 15, 2013 at 17:58
  • $\begingroup$ @GitGud: I agree. But it is probably too trivial, if $|S|=1$, then $f$ is always a surjection. $\endgroup$
    – polkjh
    Jan 15, 2013 at 18:02

You must log in to answer this question.