Bijection Proof

1. May 3, 2012

bananabate

1. The problem statement, all variables and given/known data
This was a problem on our final. I played with traits of a bijection to no avail and got a 0%. It's got me completely stumped. I really cannot even figure out a way to start.

Let X be a finite set. Let f : X → X be a bijection. For n ε Z>0, set
fn = {f°f...°f} n times

Prove that there exists m ε Z>0 such that fm = id.

2. Relevant equations
Not sure there are any?

3. The attempt at a solution
Tried playing with properties of bijections: fg=idy gf=idx and the fact that bijections are both injective and surjective. I'm fairly certain these fit into the proof somehow but I think I'm missing it.

2. May 3, 2012

gopher_p

How many different bijections of a finite set can there be? Does the set of bijections perhaps have a ... structure? What happens when you compose bijections?

3. May 3, 2012

Bacle2

There is a small kink in addition to gopher_p's good comment, but it can be done away easily: the iterations may loop without reaching the identity, i.e., you may get
f^n= f^(n+k) ; this almost gives you the answer.

4. May 3, 2012

bananabate

Sorry, I'm probably sounding terribly ignorant, but I'm completely lost with your explanations. I believe I am missing how bijections loop.

You said how many different bijections of a finite set can there be. Is it the number of elements in the set? Or is it just 2?

Maybe I'm not understanding bijections correctly. To my understanding, as f is bijective, there exists a map g such that fg(y) = idy and gf(x) = idx.

So as fg(x)=x then fg(fg(x))=x So is this a loop? Would this indicate 2 different bijections in a finite set?

If so, I don't understand how g comes into play as f^n = f°f...°f?

I'm really sorry I'm misunderstanding. I really appreciate the help.

5. May 3, 2012

gopher_p

Sorry if my reply was too vague. I was hoping the hints might get you going.

A bijection from a set $X$ to a set $Y$ is, in my experience, typically defined as a map with is both injective (1-1) and surjective (onto). One of the consequences of $f:X\rightarrow Y$ being bijective is that there is also a map $g:Y\rightarrow X$ which is also bijective. Additionally the map $g\circ f:X\rightarrow X$ is the identity map on $X$, and $f\circ g:Y\rightarrow Y$ is the identity map on $Y$. We commonly refer to $g$ as $f^{-1}$ and $f$ as $g^{-1}$, i.e. they are inverse functions.

Another property of bijections is that the (appropriate) composition of two bijections is also a bijection; i.e. if $f:X\rightarrow Y$ and $h:Y\rightarrow Z$ are both bijections, then $h\circ f:X\rightarrow Z$ is also a bijection.

Now to your problem. If we have a finite set $X$ with size $|X|=N$, then there are precisely $N!$ unique bijections from $X$ onto itself. This set of bijections forms a group (hopefully you've seen some abstract algebra/group theory) with composition as the operation. This group is commonly called the symmetric group on $X$. Since it is a finite group, every element has finite order. Hence, for all bijections $f:X\rightarrow X$ there is $n$ such that $f^n=Id$.

An alternate solution, suggested by Bacle, uses the pigeonhole principle to assert that it must be the case that for each $x\in X$, there exist $0\leq n<m$ such that $f^n(x)=f^m(x)$. Since $f$ has an inverse, we can apply it $n$ times to get $x=f^{m-n}(x)$. If we lable the elements of $X$ $x_1, x_2, ... , x_N$, then we can say that for all $i=1, 2, ... , N$ there is $k_i$ such that $f^{k_i}(x_i)=x_i$. You can check that, for $K=k_1k_2\cdot...\cdot k_N$, $f^K(x)=x$ for all $x\in X$.

Last edited: May 3, 2012
6. May 3, 2012

SteveL27

My wild-*** guess is that the OP has not seen any group theory; otherwise this problem's too easy. I'm wondering what is the simplest elementary (no group theory) solution to the OP's question.

7. May 5, 2012

bananabate

Again, I'm terribly sorry, I'm not understanding your explanations.

I think where I am stuck is that I'm not seeing how f composed of it self n times can equal the identity.

For example, take f(x) = x-3. This is a bijection as there exists g(x)=x+3 such that fg=id.

But then f°f(x) = x-3-3. Continuing, f°f°f(x)=x-3-3-3. So for fn(x)=x-3n.

I don't see how you can get fn=id without using the map g?

8. May 5, 2012

bananabate

Okay, so ignore my previous response. Here's what I've got. Does this work?

Let X be a finite set and f:X→X be a bijective map. As f is a bijection there exists a bijective map g:X→X such that fg=id. Now as g is a bijection, there exists a map g-1 such that g°g-1=id. So f=g°g-1.

Thus fm={(g°g-1)°(g°g-1)...°(g°g-1)} m times

Thus fm = id.

Thoughts?

9. May 5, 2012

Sajet

First of all, concerning your x-3 example: Yes, you can do this infinitely and get a different bijection every time. This works because the set of real numbers is infinite.

But in our case, we have a finite set.

What you said in your last post doesn't work. One problem is your conclusion f=g°g-1.

gopher_p gave you very good advice. Maybe you should just look at an example. Take the set {1, 2, 3}. Every bijection is a permutation of this set. Of course, there is only a finite number of ways we can permute the elements of this set, in this case 3! = 6 ways. This means, if we call one of those bijections/permutations f and look at f², f³, ..., at some point we'll get to a bijection that we've already seen before.

As a formula: fk = fk+n for some k, n. Why does this mean that fm = id for some m?

10. May 5, 2012

bananabate

Thanks for the help. So you basically have to find the number of permutations such that you get back to the original? Here's another go, I think I'm understanding gopher's explanation better.

Let X be a finite set and f:X→X be a bijective map. As X is a finite set, we have X={x1,x2...,xn}. As f is a bijection, there exists an inverse of f which can be applied n times to get x=fn/SUP]f-n(x). As X is a finite set, the set X has n! possible permutations. Therefore, fm=id where m=k!.

11. May 6, 2012

katie101

I was assigned this problem in an exam as well and got as far as figuring out that there are N! unique bijections, I am not sure however how you make the step from there that f^n= id, can someone please explain? Thankyou!

12. May 7, 2012

Sajet

While the knowledge of elementary group theory gives this result, I don't think I (or you yourself) can follow how you argue that the first sentence implies the second. It seems to me that you just throw together all keywords that appeared in this thread without following a clear line of reasoning.

Let me lift the confusion and show you a clear argument:

Let X = {x1, ..., xk} be a finite set. We have already established that there are exactly k! different bijections from this set to itself (i.e. permutations). We also know that the composition of two bijections is a bijection as well. Let f: X → X be a bijection.

Then f2, f3, ... are also bijections. Since there is only a limited number of different bijections (= k!), at some point of this sequence the same bijection* will come around again. Meaning:

fn = fn' for some n, n', n ≠ n'. We can assume that n' > n, that means we can write n' as n' = n + m. Therefore:

fn = fn+m.

Now since fn is a bijection, it is invertible. Thus, we can multiply both sides of the equation with its inverse f -n. This gives

id = fm.

*Note: At this point this does not necessarily mean that f itself will ever appear again. For example, we can form an infinite sequence containing only the numbers 1, 2 and 3 without using all of them twice, such as 1, 2, 3, 3, 3, 3, 3, ... . But we can't do that without using any number twice.

Last edited: May 7, 2012
13. May 7, 2012

HallsofIvy

Staff Emeritus
It's the "pigeon hole" principle. Since there are only n! possible bijections, in an infinite list of bijections, there must be at least two that are the same- for some m and n, $f^m= f^n$. Further, since these are bijections, they are invertible. We can, without loss of generality, assume m< n. What is (f^m)^{-1}(f^n(x))?

14. May 7, 2012

bananabate

Ahh that makes sense. Thank you so much for the help!

15. May 9, 2012

Bacle2

Alternatively, you have 2 main choices (sorry if I wasn't too clear on my previous):

1)You either hit the identity after a certain number of iterations,

(this will happen, but it's not obvious)

You're done

or,

2) you don't:

Then, as others have said, there are only finitely-many choices for bijections.

This means that at some point, say after the j-th composition, your bijections

start repeating, i.e., f^(n)=f^(k) Assume k>n , so that k=n+j ; then:

f^(n)=f^(k)=f^(n)of f^(j) ; so f^(j) composed with f^(n) equals f^(n)......

16. May 9, 2012

HallsofIvy

Staff Emeritus
That's because the set you are applying the function to is NOT finite.

If you have a finite set, you could list them in a specific order: $\{x_1, x_2, ..., x_n\}$. Any bijection of that set to itself just "permutes" those- changes its order. But if there are only n members of the set, there are only $2^n$ possible permutations.

If you have more than $2^n$ functions, some of them must be duplicates.

So for some i and j, $f^i(x)= f^j(x)$.