Abstract Algebra: Permutations and Disjoint Cycles

In summary, Theorem 8.1 of Dan Saracino states that for any function f in the finite group S_n, there exist disjoint cycles f_1, f_2, ... in S such that f = f_1°f_2°..., which is proven by choosing a finite group S_n={1,2,...,n} and an element x_1 in S_n, and defining x_2 = f(x_1), x_3 = f(x_2) and so on. This is because the finite nature of S_n guarantees that the sequence x_1, x_2, x_3, ... must have a repetition, and by choosing the first element of this repetition we can construct
  • #1
Halaaku
23
0

Homework Statement



Theorem 8.1 of Dan Saracino:
Let f ε S[itex]_{n}[/itex]. Then there exist disjoint cycles f[itex]_{1}[/itex],f[itex]_{2}[/itex]
.. in S such that f= f[itex]_{1}[/itex]°f[itex]_{2}[/itex]...

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...
 
Physics news on Phys.org
  • #2
Halaaku said:

Homework Statement



Theorem 8.1 of Dan Saracino:
Let f ε S[itex]_{n}[/itex]. Then there exist disjoint cycles f[itex]_{1}[/itex],f[itex]_{2}[/itex]
.. in S such that f= f[itex]_{1}[/itex]°f[itex]_{2}[/itex]...

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?
 
  • #3
x_l = x_k simply imply that f is 1-1.
 
  • #4
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
Halaaku said:
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.
 
  • #6
Halaaku said:
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}##?
 
  • #7
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
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
Halaaku said:
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.
 
  • Like
Likes 1 person
  • #10
Halaaku said:
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?
 
Last edited:
  • #11
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
Halaaku said:
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.
 
  • #13
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 :smile:
Thank you!
 
  • #14
Halaaku said:
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 :smile:
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.
 

What is abstract algebra?

Abstract algebra is a branch of mathematics that studies algebraic structures such as groups, rings, and fields. It focuses on the abstract properties and relationships between these structures rather than specific numerical values.

What are permutations in abstract algebra?

In abstract algebra, permutations refer to rearrangements of a set of objects. They are represented by a group of elements that can be applied to the objects to change their positions or order. Permutations are often represented as functions or cycles.

What are disjoint cycles in abstract algebra?

Disjoint cycles refer to permutations in which the cycles do not have any common elements. In other words, the cycles do not share any objects that are moved by the permutation. Disjoint cycles are important in abstract algebra as they can be used to represent any permutation as a product of smaller cycles.

What are some applications of abstract algebra?

Abstract algebra has numerous applications in various fields such as physics, computer science, cryptography, and coding theory. It is used to study symmetry, patterns, and relationships between objects. In cryptography, abstract algebra is used to design and analyze secure encryption algorithms.

What is the difference between abstract algebra and elementary algebra?

Elementary algebra deals with the manipulation of numbers and variables using basic operations such as addition, subtraction, multiplication, and division. It is concerned with solving equations and inequalities. On the other hand, abstract algebra deals with the study of algebraic structures and their properties, without focusing on specific numerical values. It is more abstract and general compared to elementary algebra.

Similar threads

  • Calculus and Beyond Homework Help
Replies
4
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
8
Views
1K
Replies
1
Views
1K
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
15
Views
4K
  • Calculus and Beyond Homework Help
Replies
1
Views
794
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
Replies
14
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
Back
Top