# Homework Help: Abstract Algebra: Permutations and Disjoint Cycles

1. Mar 20, 2014

### Halaaku

1. The problem statement, all variables and given/known data

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?

2. Relevant equations

Mentioned above.

3. The attempt at a solution
Trying to understand things...

2. Mar 20, 2014

### Dick

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?

3. Mar 20, 2014

### Halaaku

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

4. Mar 20, 2014

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

5. Mar 20, 2014

### Dick

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.

6. Mar 20, 2014

### Dick

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

7. Mar 20, 2014

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

8. Mar 20, 2014

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

9. Mar 20, 2014

### Dick

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

10. Mar 20, 2014

### Dick

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?

Last edited: Mar 20, 2014
11. Mar 20, 2014

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

12. Mar 20, 2014

### Ray Vickson

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.

13. Mar 22, 2014

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

14. Mar 22, 2014

### Ray Vickson

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.