Proving That a Symmetric Group on a Finite Set Is Not Cyclic If the Set Has More Than Two ElementsDate: 01/11/2010 at 17:35:20 From: Tom Subject: Abstract Algebra (college math) A group is cyclic if an element, g, of the group generates the entire group in the sense that if h is any other element of the group, then, for some k, h = g^k = g * g * g * ... * g Show that the symmetric group on a finite set, S, is not cyclic if the set has more than 2 elements. Would this be correct? For 2 elements, h and b, of a cyclic group, let h = g^x and b = g^y. Then h*b = (g^x)*(g^y) = g^(x + y) = g^(y + x) = b*h. So the cyclic group is Abelian. Let a symmetric set S = {1, 2, 3, 4, 5, ....., n}. Let A = {2, 1, 3, 4, 5, ....., n}. Let B = {1, 3, 2, 4, 5, ....., n}. Then A*B is not equal to B*A. Therefore, the set is not commutative, and consequently it is not cyclic. Right? I've no idea if I answered the question. I'm also not sure if I used the proper terms (I'm new to abstract algebra). Were enough steps and information shown to answer the question? Date: 01/12/2010 at 14:56:57 From: Doctor Carter Subject: Re: Abstract Algebra (college math) Hi Tom - What you've written is very good -- excellent, in fact, for a person new to algebra. Let me quickly summarize your main ideas: (A) All cyclic groups are abelian (B) The symmetric group on n letters is not abelian if n > 2 Both these statements are true, and this is a very nice proof. But there's a detail in your work which is incorrect. Let me give some comments on your proof of (B): 1) When you refer to S, call it "the symmetric group on the set {1, 2, ..., n}" rather than "the symmetric set...." The set {1, 2, ..., n} has n elements. S has n! (n factorial) elements and S is a group, not just a set. These are not the main problem, just nits. But I mention them. 2) When you say "let A = {2, 1, 3, 4, 5, ....., n}" I'm assuming you want A to be a certain n-cycle. Use parentheses rather than set braces in your notation for cycles. Reserve set braces for sets. Again, this is just a nit. 3) Your idea, if I understand correctly, is to show that the n- cycles (2, 1, 3, 4, ..., n) and (1, 3, 2, 4, ..., n) do not commute. Finding a pair of elements in S which do not commute is exactly what you want to do, but these two don't quite do it for you, and this is the real mistake in your work. Notice that when n = 3, your two cycles are (2, 1, 3) and (1, 3, 2). These notations actually represent exactly the same cycle; it's the function f:{1, 2, 3}-->{1, 2, 3} given by f(1) = 3, f(2) = 1, and f(3) = 2. Since the element f of S commutes with itself (or any power of itself), the elements you give *do* commute when n = 3. So there's an important detail which you need to fix. Can you show instead that the 2-cycles (1, 2) and (1, 3) fail to commute? Cheers and best wishes, - Doctor Carter, The Math Forum http://mathforum.org/dr.math/ Date: 01/12/2010 at 16:06:18 From: Tom Subject: Abstract Algebra (college math) Hi Doctor Carter, In the second part, I'm not sure what you mean by "n-cycles"; there's so many definitions out there, it is sometimes confusing to know which one to use. I see the problem you pointed out in my set; would it make more sense if I said Sn = group of permutations of (1, 2, 3, 4, 5, ..., n) and then let A = (1, 2, 3, 4, 5, ..., n) and B = (1, 3, 2, 4, 5, ..., n) ? I'm trying to show that A*B is not the same as B*A by using what I showed earlier in the first part in a general way (I don't want them to commute). Does this show that the finite set, S, is not cyclic? Thanks for replying :) Tom Date: 01/12/2010 at 20:10:03 From: Doctor Carter Subject: Re: Abstract Algebra (college math) Hi Tom - 1) It's fine to call Sn the "group of permutations of the set {1, 2, ...,n }. Use curly brackets here, because you're talking about a SET of elements, and we use curly brackets to denote sets in mathematics. 2) When you define A, I assume you mean it to be the function in Sn which sends 1 to 2, 2 to 3, 3 to 4, ..., (n - 1) to n, and n back to 1. This function A permutes the n elements of the set {1, 2, ..., n} cyclically and is an example of what's called an n-cycle. If n happens to be 3, A will be the 3-cycle (1, 2, 3) which sends 1 to 2, 2 to 3, and 3 to 1. So far, so good. 3) The function B you define next appears to be different from A, so that's an improvement over your original choices. I understand what B is when n is at least 4, but what value does B have if n = 3? The notation doesn't make it clear. Perhaps in the case n = 3, you want B to be (1, 3, 2)? This would be logical, but something unfortunate happens: If A = (1, 2, 3) and B = (1, 3, 2), then A and B commute! In fact, in this case, B = A^2. You should try to show this; it will help you understand more about how permutations work. So you've still got some trouble. You'd like to find functions A and B in Sn which don't commute, and you'd like to do this whenever n is at least 3. If you succeed, you will have shown that Sn is not an abelian group, so not cyclic. But the candidates you have given so far for A and B do not do the job. You need new candidates, and I suggested possible candidates in my first response. When I suggest that you let A = (1, 2), the function in Sn that I'm talking about is the function A for which A(1) = 2, A(2) = 1, and A(k) = k for all k between 3 and n. The function B = (1, 3) takes these values: B(1) = 3, B(2) = 2, B(3) = 1, and B(k) = k for k between 4 and n. It is possible (by computing tables of values) to show that functions A and B do not commute. Try hard to show this. I'll give you a hint: AB = (1, 3, 2). Can you compute BA? Keep at it; you'll definitely get it. Write back if you still need help. - Doctor Carter, The Math Forum http://mathforum.org/dr.math/ Date: 01/12/2010 at 20:59:17 From: Tom Subject: Abstract Algebra (college math) Hello again, Doctor Carter, Earlier you said: If A = (1, 2, 3) and B = (1, 3, 2), then A and B commute! In fact, in this case, B = A^2. I don't see how you arrived at B = A^2 in that case. Also, when I'm trying to find finite sets, aren't those A and B, which you keep calling as "functions"? Is it enough to show when n = 2 (2-cycle), A = {1, 2} and B = {1, 3}, where A*B is not B*A? Isn't that still solving for only 2 elements in the symmetric group on the finite set S? Actually, this brings me back to the same problem above: how can I actually multiply sets like this and still get a product? Hopefully I'm not losing sight of solving the original problem. And thanks again for taking the time to help me, - Tom Date: 01/12/2010 at 23:19:35 From: Tom Subject: Abstract Algebra (college math) Hi, Doctor Carter. I'm not sure if giving values like that would solve the original problem. It looks confusing, and the notation is completely new to me (they haven't been covered yet in my class). Would it be enough to solve the problem if I said this? Sn = set of permutation of {1, 2, 3, ... , n} and A is the permutation that swaps 1 and 2. Let B be the permutation that swaps 2 and 3. Then A*B is not equal to B*A. Symmetric groups are not commutative, thus not cyclic. Would I really need to explicitly use that example you suggested? A = (1, 2) and B = (1, 2, 3) A*B = (1, 3, 2) B*A = (1, 2, 1, 2, 3) (2, 5, 2, 1, 1) - Tom Date: 01/13/2010 at 01:26:25 From: Tom Subject: Abstract Algebra (college math) Doctor Carter -- This is my third spontaneous follow-up without reply. Sorry; I got excited! I couldn't solve the A and B defined in your second reply; it was too hard for me to do with 3 numbers, so I used an easier example: For the symmetric group Sn, let n = 3, A = (1, 2) and B = (2, 3). Then AB = (3, 2, 1) and BA = (1, 2, 3). Thus AB and BA are not commutative! Is this correct for the second part of the solution? Is the symmetric group on the finite set S now shown to be not cyclic if there's more than 2 elements? I have a good feeling about this one! Sorry for the excessive replies. Tom Date: 01/13/2010 at 09:03:01 From: Doctor Carter Subject: Re: Abstract Algebra (college math) Hi Tom - It looks like you've been making good progress while I've been sleeping! You're right to feel good about things now. Many mathematicians, and your teacher may be one of them, will agree exactly with everything you've said just now. In fact, I agree with it too, but I need to point out that you are getting different answers for AB and BA than I would. The reason for this, though you may not realize it, has to do with how we represent functions. If A and B are functions from the set {1, 2, 3} to itself, I write the value of A on the element x as A(x). And when I talk about AB, I mean the function whose values are computed using function composition in this way: (AB)(x) = A(B(x)) For me, the function on the right acts first. But this is only a convention, and there have been famous mathematicians (among them, Samuel Eilenberg, an influential 20th century algebraic topologist) who advocate letting functions operate from the right. Using this convention, the value of a function A on the element x is written (x)A and function composition now happens in the opposite order: (x)(AB) = ((x)A)B The function A, which is on the left, acts first. You are using this convention in the argument you give. It's completely valid, so what you've written is CORRECT! But I want you to be aware of the convention you're using, since the majority of mathematicians use the other convention, where functions are written to the left of their argument and where the rightmost of two functions being composed is the once which acts first. Let me try to consolidate things now, using the more common convention. 1) The group Sn consists of all the bijective functions from the set {1, 2, ..., n} to itself. The group operation in Sn is composition of functions. "Bijective" means one-to-one and onto. In particular, if F is an element of Sn and x and y are different elements of {1, 2, ..., n}, then F(x) and F(y) are not equal. 2) If n is at least 3, then Sn contains the following two functions (and more): The function A whose values are given by A(1) = 2, A(2) = 1, and A(x) = x when x is not 1 or 2. The function B whose values are given by B(1) = 1, B(2) = 3, B(3) = 2, and B(x) = x for x not equal to 2 or 3. 3) We can compose these functions. AB is the function whose values are given as follows: (AB)(1) = A(B(1)) = A(1) = 2 (AB)(2) = A(B(2)) = A(3) = 3 (AB)(3) = A(B(3)) = A(2) = 1 (AB)(x) = A(B(x)) = A(x) = x if x is not 1, 2, or 3 BA is the function whose values are given as (BA)(1) = B(A(1)) = B(2) = 3 (BA)(2) = B(A(2)) = B(1) = 1 (BA)(3) = B(A(3)) = B(3) = 2 (BA)(x) = B(A(x)) = B(x) = x if x is not 1, 2, or 3 4) The functions AB and BA are not equal! So the group Sn is not abelian when n is 3 or greater. And if it's not abelian, it cannot be cyclic. 5) [CONVENTION] I and many others use the cycle notation (1, 2, 3) to represent the function (AB) given above, which sends 1 to 2, 2 to 3, and 3 to 1. Likewise, I use (1, 3, 2) to represent the function (BA) which, sends 1 to 3, 3 to 2, and 2 to 1. This has been a very long reply. Let me finish with just one more calculation, relating to a question in one of your earlier replies: the meaning of (1, 2, 3)^2. 6) Let C be the function from {1, 2, 3, ..., n} to {1, 2, 3, .., n} whose values are given by C(1) = 2, C(2) = 3, C(3) = 1, and C(x) = x when x is not 1, 2, or 3. Then C^2 has the following values: (C^2)(1) = C(C(1)) = C(2) = 3 (C^2)(2) = C(C(2)) = C(3) = 1 (C^2)(3) = C(C(3)) = C(1) = 2 (C^2)(x) = C(C(x)) = C(x) = x when x is not 1, 2, or 3 C^2 sends 1 to 3, 3 to 2, and 2 to 1. I and many others use the cycle notation (1, 2, 3) to represent C and (1, 3, 2) to represent C^2. I hope this has been helpful! Congratulations if you're still reading! And let me say again that you are right to feel good about this problem -- the last things you had to say were exactly right; they just assumed a different notational convention. - Doctor Carter, The Math Forum http://mathforum.org/dr.math/ Date: 01/13/2010 at 15:43:04 From: Tom Subject: Abstract Algebra (college math) Hello again Doctor Carter, Thanks for letting me know about that convention, that should clear up future confusion. Thank you again for all your help!!! Cheers, Tom Date: 01/13/2010 at 15:47:51 From: Tom Subject: Thank you (Abstract Algebra (college math)) My thanks goes to Doctor Carter who spent lots of time to give very thorough explanations on the thought process, notations and conventions used for abstract algebra, which is an intensely hard subject of math! Thanks so much! |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/