1
$\begingroup$

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?

  • 0
    This is closely related to your older question: http://math.stackexchange.com/questions/75880/if-g-circ-f-is-the-identity-function-then-which-of-f-and-g-is-onto-and-w/2011-11-17

2 Answers 2

3

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.

2

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.

  • 0
    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$.2011-11-18