# Why do these functions have to be bijective?

If we have two functions, $f:X\rightarrow X$ and $g:X\rightarrow X$ where $X$ is a finite set, why, if $g(f(x))=x$ for all $x\in X$, is it true that $f$ and $g$ are bijective?

-
This is closely related to your older question: math.stackexchange.com/questions/75880/… –  Martin Sleziak Nov 17 '11 at 8:44

It follows right away that $f$ is injective and $g$ is surjective (use the definitions). It is also straight forward that any injective function between two finite sets of the same cardinality is also a surjection, and similarly any surjection between two finite sets of the same cardinality is also an injection. Therefore you have that $f$ and $g$ are bijective.

-

I'll do $f$ and leave $g$ to you - ok?

$f$ is one-to-one (injective): suppose that $f(a)=f(b)$. Then taking $g$ of both sides still yields the same thing: $g(f(a))=g(f(b))$. But we know that $g(f(a))=a$ and $g(f(b))=b$, so then $a=b$. We've shown that $f(a)=f(b)$ implies $a=b$ which is the very definition of "$f$ is injective".

Now $f$ must be onto (surjective) only because $X$ is finite. Indeed, when $X$ is finite, any function $z:X \to X$ is surjective if it's injective.

When $X$ is infinite, $f$ need not be surjective: take $X=\{1,2,3,\ldots\}$, $f(n)=n+1$, $g(n)=n-1$ (except $g(1)=1$, say). Here $f$ isn't surjective and $g$ isn't injective.

-
Doesn't your above explanation also show that $g$ is injective, because $g(f(a))=g(f(b))$ and $f(a)=f(b)$? –  johnnymath Nov 17 '11 at 22:53
That doesn't mean that $g$ is injective. To show that $g$ is injective, you need (by definition) to show that whenever $g(x)=g(y)$, $x=y$. It's not enough to say "$g(f(a))=g(f(b))$ and $f(a)=f(b)$". Specifically, if $f$ isn't surjective, you can't conclude anything about $g(z)$ for $z$ which isn't $f(a)$ for any $a$. –  Alon Amit Nov 18 '11 at 2:56