Prove that a function $f:S\to S$ is bijective iff there exist unique functions $g,h:S\to S$ s. t.
$$g\circ f=f\quad\&\quad f\circ h=f.$$
My attempt:
Direction $\boxed{\Leftarrow}$
If the functions $f,g:S\to S$ are unique, then $f$ is bijective. I tried to use the contraposition:
If $f$ isn't bijective, then $f$ or $g$ isn't unique.
If $f$ isn't bijective, then it isn't injective or surjective.
If $f$ isn't injective, then there are some $x_1,x_2\in S,x_1\ne x_2$ and $f(x_1)=f(x_2)$.
Let $S_i:=\{x\in S\mid f(x)=y_i,\},\space i\in\mathcal I$ and let $\space T=S\setminus\bigcup\limits_{i\in\mathcal I} S_i$ where $f$ is injective. We can define $h$ in the following way:
$$h(x):=\begin{cases} x'_i\in S_i,&\color{red}{x\in S_i, x\ne x_i'}\\ x,& x\in T\end{cases}$$
So, my idea is to permute the $x$' es which give the same output. I first thought we can start with $h(x_1)=x_2\space\&\space h(x_2)=x_1$ whenever $f(x_1)=f(x_2)$, but I tried to inductively generalize it. As we can construct $h$ different from identity, which also satisfies the condition, $h$ isn't unique.
If $f$ isn't surjective, then $\operatorname{Ran}(f)\subset S$. We can define $g$ in the following way:
$$g(x)=\begin{cases}x,&x\in\operatorname{Ran}(f)\\k(x), &x\notin\operatorname{Ran}(f)\end{cases}$$
where $k:S\to S$ is an arbitrary function. Therefore, $g$ isn't unique either.
Direction $\boxed{\Rightarrow}$
If $f$ is bijective, then $g$ and $h$ are unique.
As $f$ is bijective and $g\circ f=f,\space g\circ f$ has to be bijective as well. If so, $g$ has to be surjective, but, since $f$ is surjective, $g$ also has to be injective. Then, I concluded that $g$ is the identity on $S$.
On the other hand, since $f$ is injective, $f(h(x))=f(x)\implies h(x)=x=g(x)$, which is unique.
May I ask if my arguments are valid and how I could improve what I've done so far?
Thank you in advance!
Best Answer
The first part looks good. The only thing I would point out is this:
This statement is only true when $S$ is finite (I suggest thinking of counterexamples for functions on $\mathbb R$). The correct way to approach it is like this: first, existence is clear as the identity function on $S$ is a function satisfying $\operatorname{id_S}\circ f = f$ and $f \circ \operatorname{id_S} = f$. Now, let $g : S \to S$ be some other function such that $g \circ f = f$. Then $$g \circ f = f = \operatorname{id_S} \circ f$$ and since $f$ is surjective, we can conclude that $g = \operatorname{id_S}$. Similarly, if there is a function $h : S \to S$ such that $f \circ h = f$, then $$f \circ h = f = f \circ \operatorname{id_S} $$ and since $f$ is injective, we conclude that $h = \operatorname{id_S}$. This completes the proof of uniqueness.
Alternatively, if we have $g \circ f = \operatorname{id_S} \circ f$ (resp. $f \circ h = f \circ \operatorname{id_S}$), we can arrive at the same result by composing on the right (resp. left) with the inverse of $f$ which exists if and only if $f$ is bijective. However, you only need injectivity for left cancellation, and surjectivity for right cancellation.