Proving fn: A Bijection's Identity

[bananabate]

Homework Statement

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
fⁿ = {f°f...°f} n times

Prove that there exists m ε Z_>0 such that f^m = id.

Homework Equations

Not sure there are any?

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.

 

[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?

 

[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.

 

[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.

 

[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$.

 

[SteveL27]

This set of bijections forms a group (hopefully you've seen some abstract algebra/group theory)

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.

 

[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 fⁿ(x)=x-3n.

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

 

[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 f^m={(g°g^-1)°(g°g^-1)...°(g°g^-1)} m times

Thus f^m = id.

Thoughts?

 

[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: f^k = f^k+n for some k, n. Why does this mean that f^m = id for some m?

 

[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={x₁,x₂...,x_n}. As f is a bijection, there exists an inverse of f which can be applied n times to get x=f^{n/SUP]f-n(x). As X is a finite set, the set X has n! possible permutations. Therefore, fm=id where m=k!.}

 

[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!

 

[Sajet]

[...]As X is a finite set, the set X has n! possible permutations. Therefore, f^m=id where m=k!.

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 = {x₁, ..., x_k} 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 f², f³, ... 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:

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

fⁿ = f^n+m.

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

id = f^m.

*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.

 

[HallsofIvy]

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!

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))?

 

[bananabate]

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

 

[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)...

 

[HallsofIvy]

≈

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 fⁿ(x)=x-3n.

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

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)$.