Abstract Algebra: Permutations and Disjoint Cycles

[Halaaku]

Homework Statement

Theorem 8.1 of Dan Saracino:
Let f ε S_{n}. Then there exist disjoint cycles f_{1},f_{2}
.. in S such that f= f_{1}°f_{2}...

In proving this theorem, it considers a finite group S_n={1,2,..,n} and chooses x_1 ε S_n. Then it defines x_2= f(x_1), x_3=f(x_2) and so on. The part I do not understand is "because S_n is a finite set, the sequence x_1, x_2 , x_3... must have a repetition. So there must be a first element in the sequence which is the same as the previous element. "

Q: Does a finite set imply that for any sequence of its elements, there HAS to be a repetition?
Q: If so, why should the FIRST element get repeated?

Homework Equations

Mentioned above.

The Attempt at a Solution

Trying to understand things...

 

[Dick]

Homework Statement

Theorem 8.1 of Dan Saracino:
Let f ε S_{n}. Then there exist disjoint cycles f_{1},f_{2}
.. in S such that f= f_{1}°f_{2}...

In proving this theorem, it considers a finite group S_n={1,2,..,n} and chooses x_1 ε S_n. Then it defines x_2= f(x_1), x_3=f(x_2) and so on. The part I do not understand is "because S_n is a finite set, the sequence x_1, x_2 , x_3... must have a repetition. So there must be a first element in the sequence which is the same as the previous element. "

Q: Does a finite set imply that for any sequence of its elements, there HAS to be a repetition?
Q: If so, why should the FIRST element get repeated?

Homework Equations

Mentioned above.

The Attempt at a Solution

Trying to understand things...

Saying that $f \in S_n$ means f is a 1-1 and onto function from {1,2,...,n} to {1,2,...,n}. So your sequence has to have a repeated element just because the number of choices is finite. Suppose it repeats, so $x_k=x_l$ with k>1. That would mean $f(x_{k-1})=x_k$ and $f(x_{l-1})=x_l=x_k$. What do you conclude from that?

 

[Halaaku]

x_l = x_k simply imply that f is 1-1.

 

[Halaaku]

When you say "... your sequence has to have a repeated element just because the number of choices is finite", could you please give an example of it? Isn't the sequence {1,2,3} finite despite there being no repetition?

 

[Dick]

When you say "... your sequence has to have a repeated element just because the number of choices is finite", could you please give an example of it? Isn't the sequence {1,2,3} finite despite there being no repetition?

You have to keep going. That sequence says f(1)=2, f(2)=3 then next element would be f(3). You have to make a choice for that too.

 

[Dick]

x_l = x_k simply imply that f is 1-1.

Not quite. What would that tell you about $x_{l-1}$ and $x_{k-1}$?

 

[Halaaku]

If you are taking x_k to be the first index then x_{k-1} is suggesting an element of zero index, but we started off with index 1.

 

[Halaaku]

But why should x_k be the first element? when there can be different representations for the same cycle eg {1,5,7}={7,1,5}, we can't really fix the first element, or can we?

 

[Dick]

But why should x_k be the first element? when there can be different representations for the same cycle eg {1,5,7}={7,1,5}, we can't really fix the first element, or can we?

You PICK the first element of the cycle. It can be anything. No, this procedure doesn't fix the first element.

 

[Dick]

If you are taking x_k to be the first index then x_{k-1} is suggesting an element of zero index, but we started off with index 1.

That's part of it. If the first element is the repeating one, then there is no problem because there is no zero index element to worry about. If the first repetition isn't the first, then what kind of problem do you have?

 

[Halaaku]

You answered that in your last to last reply. The proof is constructed this way that i pick first element.
What I was thinking was what if some other element, lying in the middle somewhere, got repeated, but then we can write a representation such that this element becomes the first element.
So, thank you!

 

[Ray Vickson]

You answered that in your last to last reply. The proof is constructed this way that i pick first element.
What I was thinking was what if some other element, lying in the middle somewhere, got repeated, but then we can write a representation such that this element becomes the first element.
So, thank you!

Part of your original question was a good one. You want to know why some string like, say, S = x1,x2,x3,x4,x5,x3 could not occur; it has a repetitition, but the cycle does not come back to x1. Well, remember that f(.) is 1:1 onto, so look at g = f^(-1), the inverse of f. Using g and starting at the end of the string above we would get x3,x5,x4,x3,x2,x1, and that is where we now have a serious problem: when we get to x3 (from x4) we suddenly have two choices for g(x3); namely x5 and x2. But, g must also be 1:1 and onto, so that could not happen. Therefore, the original string S cannot occur.

 

[Halaaku]

The string S cannot be called a cycle. Its not 1-1, hence it can't have an inverse. Although I understand what you have stated but I think giving the example i.e the string S, would have been enough
Thank you!

 

[Ray Vickson]

The string S cannot be called a cycle. Its not 1-1, hence it can't have an inverse. Although I understand what you have stated but I think giving the example i.e the string S, would have been enough
Thank you!

The function f is 1:1 onto, not the string S. The point is that in the example I gave you the element x3 has two pre-images under f, namely x2 and x5, and that cannot happen for a 1:1 onto map f. Therefore, the given string x2 = f(x1), x3 = f(x2), x4 = f(x3), x5 = f(x4), x3 = f(x5)cannot occur: it yields a contradiction. It would be perfectly OK for a cycle such as x2 = f(x1), x3 = f(x2), x1 = f(x3); there would be no contradiction there.