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.

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?

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

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer
    
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

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.