So... On Thursday, I had my Discrete midterm. Here's some ruminations on the exam:
1) There was a proof that looked like this: Use the binomial theorem to prove that the sum of all nCr(n,i)=2^n. Problem is, I couldn't recall until about halfway through the exam what the binomial theorem states. Here's what I put:
Pf: The Binomial Theorem states that (a+b)^n=nCr(n,n)*(a^n)*(b^n-n)+...+nCr(n,0)*(a^n-n)*(b^n). Then, let a,b=1. So, (1+1)^n=nCr(n,n)*(1^n)*(1^n-n)+...+nCr(n,0)*(1^n-n)*(1^n)=nCr(n,n)+...+nCr(n,0)=2^n. QED.
I know, pretty facile, right? But it's not wrong, just simple! Still, I'm not sure if I wrote it formally enough.
2) There was also this problem, which took me a LONG time: Let n1+n2+n3+n4=23, where n1>=2, n2>=3, n3>=4, n4>=5. How many solutions are there, where ni is an integer?
Solution: Due to the quantifiers, there are 2+3+4+5=14 numbers already accounted for. Also, there are 4 integers ni, so there are 3 dividers. So, the number of solutions is nCr(23-14+4-1,23-14)=(12,9).
3) Finally, there was this little stumper: How many (distinct) ways are there to rearrange the letters of TALLAHASSEE, such that the two L's are together and the two E's are NOT together?
Solution: First, let's find the number of ways to rearrange the letters with the two L's together. Consider the two L's to be a single letter. Then, there are 10!/3!2!2! arrangements. However, this includes the ways in which the two E's are together. So, let's find the ways in which the two L's are together AND the two E's are together, and subtract that number from the ways in which the two L's are together. This number is, then, 10!/3!2!2!-9!/3!2!.
I'm not sure I did that one right, but I feel pretty good about it.
And today I had my Group Theory midterm. I think I did pretty well on that one, too, but I did have a little trouble proving the onto-ness of the isomorphism P(x)=x^5. There were a few other isomorphism problems that I might have not done totally correctly, but only because they involved external direct products, and I'm still a little shaky on those. I'll post my exam results. Mostly to show off, of course, but, since no one actually reads this besides me, it's also a great way for me to... I don't know. Ok, ok, it's mostly for me to show off. Deal with it.
Saturday, February 27, 2010
Wednesday, February 24, 2010
Group Theory Midterm Study Guide 3
Here's some examples of different types of groups, properties, and other bits of information that I might need to know for the exam.
Abelian Groups: A group G is Abelian iff ab=ba for all a,b in G.
Examples:
Cyclic Groups: A group G is cyclic iff there exists an element a such that 'a'=G.
Examples:
Normal Groups: A subgroup H is normal to a group G iff xHx^-1=H, for all x in G.
Examples:
Isomorphisms: An isomorphism P is a mapping from a group G to a group P(G), where P is one-to-one, onto, and operation preserving.
Properties:
Properties:
Lagrange's Theorem: Let G be a group with a subgroup H. Then, |H| divides |G|; also the number of distinct cosets of H in G is |G|/|H|.
Corollary 2: |a| divides |G|.
Corollary 3: All groups of prime order are cyclic.
Corollary 4: a^|G|=e.
External Direct Products: Let G1,..., Gn be a finite collection of groups. The external direct product of G1,..., Gn, written as G1#...#Gn, is the set of all n-tuples for which the ith component is an element of Gi and the operation is componentwise.
What That Means: Think of the Cartesian product. For example, Z(2)#Z(3)={(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)}, where (1,1)(1,2)=(0,0), because 1+1mod2=0 and 1+2mod3=0.
Properties:
I need to go study for Discrete Math, now, but I might post some discrete stuff on here later.
Ciao, folks.
p.s.: I again apologize for the blatant lack of formality in the formatting, Deal with it.
Abelian Groups: A group G is Abelian iff ab=ba for all a,b in G.
Examples:
- Z(n) under regular addition
- U(n) under regular multiplication
- Aut(Z(n)) under function composition
- Iff G is Abelian, then P(G) is Abelian.
- If G is Abelian, then the subgroup H is necessarily Abelian.
Cyclic Groups: A group G is cyclic iff there exists an element a such that 'a'=G.
Examples:
- In Z(n) with element k, if gcd(n,k)=1 (n,k relatively prime), then k is a generator of Z(n).
- If |G| is prime, then G is cyclic.
- Every subgroup of a cyclic group is cyclic.
- For each positive divisor k of n, the set 'k/n' is the unique subgroup of Z(n) with order k; these are the ONLY subgroups of Z(n).
- S(n) is cyclic.
- G is cyclic iff P(G) is cyclic.
- Moreover, G='a' iff P(G)='P(a)'; that is to say, a generator maps to another generator.
Normal Groups: A subgroup H is normal to a group G iff xHx^-1=H, for all x in G.
Examples:
- Any subgroup H of an Abelian group G is normal to G.
- The centralizer Z(G) is always normal to G.
- A(n) is always normal to S(n).
- R(n) is always normal to D(n).
- SL(2,R) is always normal to GL(2,R).
Isomorphisms: An isomorphism P is a mapping from a group G to a group P(G), where P is one-to-one, onto, and operation preserving.
Properties:
- The identity always maps to the identity.
- G is cyclic iff P(G) is cyclic.
- G is Abelian IFF P(G) is Abelian.
- G and P(G) have the same number of elements of each order, if G is finite.
- G and P(G) have the same order.
- |a|=|P(a)|; that is, P preserves the order of an element.
- For a,b in G, a,b commute iff P(a),P(b) commute.
- For all a in G, P(a^n)=(P(a))^n.
- If K is a subgroup of G, then P(K) is a subgroup of P(G).
- Aut(Z(n)) is isomorphic to U(n).
Properties:
- a is in aH.
- aH=H iff a is in H.
- aH=bH iff a is in bH.
- aH=bH or aH&bH={0}.
- aH=bH iff (a^-1)b is in H.
- |aH|=|bH|.
- aH=Ha iff H=aH(a^-1).
- aH is a subgroup of G iff a is in H.
- The number of distinct cosets (left, right, OR whatever) of H in G is |G|/|H| (Lagrange's Theorem).
Lagrange's Theorem: Let G be a group with a subgroup H. Then, |H| divides |G|; also the number of distinct cosets of H in G is |G|/|H|.
Corollary 2: |a| divides |G|.
Corollary 3: All groups of prime order are cyclic.
Corollary 4: a^|G|=e.
External Direct Products: Let G1,..., Gn be a finite collection of groups. The external direct product of G1,..., Gn, written as G1#...#Gn, is the set of all n-tuples for which the ith component is an element of Gi and the operation is componentwise.
What That Means: Think of the Cartesian product. For example, Z(2)#Z(3)={(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)}, where (1,1)(1,2)=(0,0), because 1+1mod2=0 and 1+2mod3=0.
Properties:
- The order of an external direct product is the product of the orders of the individual groups.
- The order of an element of an external direct product is the least common multiple of the orders of the components of the element.
- G#H is cyclic iff |G| and |H| are relatively prime.
- Let m=n1*...*nk. Then, Z(m) is isomorphic to Z(n1)#...#Z(nk) iff ni and nj are relatively prime when i does not equal j. For example, Z(2)#Z(5)#Z(7)==Z(2)#Z(35)==Z(10)#Z(7)==Z(14)#Z(5)
I need to go study for Discrete Math, now, but I might post some discrete stuff on here later.
Ciao, folks.
p.s.: I again apologize for the blatant lack of formality in the formatting, Deal with it.
Tuesday, February 23, 2010
Group Theory Midterm Study Guide 2
Proofs today, folks. I'll be proving the following theorems: Commutativity of Disjoint Cycles, Lagrange's Theorem (and the requisite 4th Property of the Lemma of Cosets), and the Corollaries of Lagrange's Theorem. Oh, just so there's no confusion, I'm not copying this out of my text; this is coming from memory (as much as possible) as an exercise for cementing these proofs for the exam (where I will be asked to give at least one of them).
Commutativity of Disjoint Cycles
Claim: If cycles A and B are disjoint, then AB=BA.
Pf: Define a set S such that S={a1,..., an, b1,..., bn, c1,..., cn}, where a's are elements mapped by A, b's are elements mapped by B, and c's are elements mapped by neither A nor B. Then, I need to show that (AB)(x)=(BA)(x) for all x in S. Let x=ai. Then, (AB)(ai)=A(B(ai))=A(ai)=a(i+1) and (BA)(ai)=B(A(ai))=B(a(i+1))=a(i+1). Now, let x=bi. Then, (AB)(bi)=A(B(bi))=A(b(i+1))=b(i+1) (BA)(bi)=B(A(bi))=B(bi)=b(i+1). Now, let x=ci. (AB)(ci)=A(B(ci))=A(ci)=ci and (BA)(ci)=B(A(ci))=B(ci)=ci. Then, (AB)(x)=(BA)(x) for all x in S. QED.
Property 4 of the Lemma of Cosets
Claim: aH=bH or aH&bH={0}.
Pf: Assume that aH and bH are left cosets of H in G. Let c be an element of aH and an element of bH. Property 3 of the Lemma of Cosets states that xH=yH if and only if x is an element of yH. Then, because c is an element of both aH and bH, cH=aH and cH=bH. Therefore, aH=bH. QED.
Lagrange's Theorem
Claim: The order of the group G is divisible by the order of the subgroup H; the number of distinct left cosets of H in G is |G|/|H|.
Pf: Let G be a finite group and let H be subgroup of G. Let a1H,..., anH be the distinct left cosets of H in G. Then, G=a1H&...&anH. However, by Property 4 of the Lemma of Cosets, these are disjoint cosets. Then, |G|=|a1H|+...+|anH|. However, |aiH|=|H|. Then, |G|=|a1H|+...+|anH|=n|H|. So, the order of G is divisible by the order of H. QED.
Corollary 2 of Lagrange's Theorem
Claim: The order of an element a of a group G divides the order of group G.
Pf: Let there be a group G with an element a. Then, 'a' is a subgroup of G. By Lagrange's Theorem, |'a'| divides |G|, but |'a'|=|a|. Then, |a| divides |G|. QED.
Corollary 3 of Lagrange's Theorem
Claim: Groups of prime order are cyclic.
Pf: Let G be a group of prime order with an element a such that a does not equal e. Then, n|'a'|=|G| by Lagrange's Theorem. However, because a does not equal e, |'a'| must not be 1. Because |G| is prime, the only other possibility for |'a'| is |G|. So, |'a'|=|G|. QED.
Corollary 4 of Lagrange's Theorem
Claim: a^|G|=e.
Pf: Let a be an element of a group G. Then, by Corollary 2 of Lagrange's Theorem, |a|k=|G|. So, a^|G|=a^(|a|k)=(a^|a|)^k=e^k=e. QED.
Ok, there are some other properties that MAY be on the exam. But I don't think I want to prove those ones. They're a pain. I almost guarantee that he'll ask for the proof of Lagrange's Theorem (and the requisite Property 4 of the Lemma of Cosets), and then he'll ask for one of the following: the Corollaries of Lagrange's Theorem, Commutativity of Disjoint Cycles, or some isomorphism properties. I've got it in the bag, kids. Ok, time to go review the definitions, then start making a reference sheet of groups -- that's going to be clutch.
Commutativity of Disjoint Cycles
Claim: If cycles A and B are disjoint, then AB=BA.
Pf: Define a set S such that S={a1,..., an, b1,..., bn, c1,..., cn}, where a's are elements mapped by A, b's are elements mapped by B, and c's are elements mapped by neither A nor B. Then, I need to show that (AB)(x)=(BA)(x) for all x in S. Let x=ai. Then, (AB)(ai)=A(B(ai))=A(ai)=a(i+1) and (BA)(ai)=B(A(ai))=B(a(i+1))=a(i+1). Now, let x=bi. Then, (AB)(bi)=A(B(bi))=A(b(i+1))=b(i+1) (BA)(bi)=B(A(bi))=B(bi)=b(i+1). Now, let x=ci. (AB)(ci)=A(B(ci))=A(ci)=ci and (BA)(ci)=B(A(ci))=B(ci)=ci. Then, (AB)(x)=(BA)(x) for all x in S. QED.
Property 4 of the Lemma of Cosets
Claim: aH=bH or aH&bH={0}.
Pf: Assume that aH and bH are left cosets of H in G. Let c be an element of aH and an element of bH. Property 3 of the Lemma of Cosets states that xH=yH if and only if x is an element of yH. Then, because c is an element of both aH and bH, cH=aH and cH=bH. Therefore, aH=bH. QED.
Lagrange's Theorem
Claim: The order of the group G is divisible by the order of the subgroup H; the number of distinct left cosets of H in G is |G|/|H|.
Pf: Let G be a finite group and let H be subgroup of G. Let a1H,..., anH be the distinct left cosets of H in G. Then, G=a1H&...&anH. However, by Property 4 of the Lemma of Cosets, these are disjoint cosets. Then, |G|=|a1H|+...+|anH|. However, |aiH|=|H|. Then, |G|=|a1H|+...+|anH|=n|H|. So, the order of G is divisible by the order of H. QED.
Corollary 2 of Lagrange's Theorem
Claim: The order of an element a of a group G divides the order of group G.
Pf: Let there be a group G with an element a. Then, 'a' is a subgroup of G. By Lagrange's Theorem, |'a'| divides |G|, but |'a'|=|a|. Then, |a| divides |G|. QED.
Corollary 3 of Lagrange's Theorem
Claim: Groups of prime order are cyclic.
Pf: Let G be a group of prime order with an element a such that a does not equal e. Then, n|'a'|=|G| by Lagrange's Theorem. However, because a does not equal e, |'a'| must not be 1. Because |G| is prime, the only other possibility for |'a'| is |G|. So, |'a'|=|G|. QED.
Corollary 4 of Lagrange's Theorem
Claim: a^|G|=e.
Pf: Let a be an element of a group G. Then, by Corollary 2 of Lagrange's Theorem, |a|k=|G|. So, a^|G|=a^(|a|k)=(a^|a|)^k=e^k=e. QED.
Ok, there are some other properties that MAY be on the exam. But I don't think I want to prove those ones. They're a pain. I almost guarantee that he'll ask for the proof of Lagrange's Theorem (and the requisite Property 4 of the Lemma of Cosets), and then he'll ask for one of the following: the Corollaries of Lagrange's Theorem, Commutativity of Disjoint Cycles, or some isomorphism properties. I've got it in the bag, kids. Ok, time to go review the definitions, then start making a reference sheet of groups -- that's going to be clutch.
Friday, February 19, 2010
Study Guide for Group Theory Midterm 1
This is my attempt to make a sexy study guide for my upcoming Group Theory Midterm. There'll be 3 parts: 1) Definitions, 2) Proofs, and 3) Properties of Groups Z(n), U(n), S(n), A(n), and D(n), with special focus on whether a given group is Abelian, cyclic, normal, etc.
This is the first section, Definitions.
I am expected to know the definitions of the following terms:
1: Even and odd permutations
2: Group isomorphism
3: Coset of H in G
4: External direct product
5: Normal subgroup.
So, here goes.
1: Even and odd permutations
A permutation is even if it is the product of an even number of 2-cycles and odd if it is the product of an odd number of 2-cycles. Specifically, if a permutation has an even number of elements, then it is an odd permutation, and if it has an odd number of elements, it is an even permutation.
2: Group isomorphism
An isomorphism P from a group G to a group G* is a one-to-one mapping from G onto G* that preserves the group operation. That is to say, an isomorphism is a function from one group to another and has three properties:
a. P is one-to-one; that is, every element g in G maps to a distinct element g* in G*.
b. P is onto; that is, every element g* G* is mapped to by a distinct element g in G*.
c. P is operation preserving (O.P.); that is, for all a,b in G, P(ab)=P(a)P(b).
Here are some notable properties of isomorphisms acting on elements and groups:
a. P maps the identity e in G to e in G*.
b. For every integer n and for every element a in G, P(a^n)=P(a)^n.
c. G is Abelian iff G* is Abelian.
d. G is cyclic iff G* is cyclic.
e. |a|=|P(a)|. Then, if G is finite, then G and G* have exactly the same number of elements of each order.
f. If K is a subgroup of G, then P(K) is a subgroup of G*.
3: Coset of H in G
Let G be a group and H be a subgroup of G. Then, for any a in G, the set {ah| h is in H} is denoted aH and is called the left coset of H in G containing a. A similar definition exists for the right coset.
Here are some properties of cosets:
a. a is in aH. Always, kids. Always.
b. aH=H iff a is in H (note that this makes aH a subgroup G, since H is a subgroup of G; this is the ONLY time that aH is a subgroup of G).
c. aH=bH iff a is in bH (or, similarly, iff (a^-1)b is in H).
d. EITHER aH=bH OR aH&bH={0}. Super important to know this. Super crucial.
e. aH=Ha iff H=aH(a^-1).
4: External direct product
Let G1, G2,..., Gn be a finite collection of groups. The external direct product of
G1, G2,..., Gn is denoted for this blog as G1#G2#...#Gn is the set of all n-tuples for which the ith component is an element of Gi and the operation is componentwise.
What does all that mean? It means that the external direct product is the set of n-tuples (like an ordered pair, but an ordered... n-tuple) where the first element is produced by using the operation of G1 on all of the "first" elements, the second element is produced by using the operation of G2 on all of the "second" elements, etc. This is weird. I don't quite get it. I'll return to this.
A few things to know about external direct products:
a. The order of an element in a direct product of a finate number of finite groups is the lcm of the orders of the components of the elements.
b. If G, H are cyclic, then G#H is cyclic iff |G| and |H| are relatively prime.
5. Normal subgroups
A subgroup H of a group G is called a normal subgroup of G if aH=Ha for all a in G. This is denoted by H|>G, for this blog.
The normal subgroup test:
A subgroup H of G is normal in G iff xH(x^-1) <= H for all x in G.
Ok, I'm tired, so I'm going to read myself to sleep now. A couple of proofs tomorrow, probably. Probably Disjoint Cycles Commute and the Four Corollaries to Lagrange's Theorem. Fun stuff.
This is the first section, Definitions.
I am expected to know the definitions of the following terms:
1: Even and odd permutations
2: Group isomorphism
3: Coset of H in G
4: External direct product
5: Normal subgroup.
So, here goes.
1: Even and odd permutations
A permutation is even if it is the product of an even number of 2-cycles and odd if it is the product of an odd number of 2-cycles. Specifically, if a permutation has an even number of elements, then it is an odd permutation, and if it has an odd number of elements, it is an even permutation.
2: Group isomorphism
An isomorphism P from a group G to a group G* is a one-to-one mapping from G onto G* that preserves the group operation. That is to say, an isomorphism is a function from one group to another and has three properties:
a. P is one-to-one; that is, every element g in G maps to a distinct element g* in G*.
b. P is onto; that is, every element g* G* is mapped to by a distinct element g in G*.
c. P is operation preserving (O.P.); that is, for all a,b in G, P(ab)=P(a)P(b).
Here are some notable properties of isomorphisms acting on elements and groups:
a. P maps the identity e in G to e in G*.
b. For every integer n and for every element a in G, P(a^n)=P(a)^n.
c. G is Abelian iff G* is Abelian.
d. G is cyclic iff G* is cyclic.
e. |a|=|P(a)|. Then, if G is finite, then G and G* have exactly the same number of elements of each order.
f. If K is a subgroup of G, then P(K) is a subgroup of G*.
3: Coset of H in G
Let G be a group and H be a subgroup of G. Then, for any a in G, the set {ah| h is in H} is denoted aH and is called the left coset of H in G containing a. A similar definition exists for the right coset.
Here are some properties of cosets:
a. a is in aH. Always, kids. Always.
b. aH=H iff a is in H (note that this makes aH a subgroup G, since H is a subgroup of G; this is the ONLY time that aH is a subgroup of G).
c. aH=bH iff a is in bH (or, similarly, iff (a^-1)b is in H).
d. EITHER aH=bH OR aH&bH={0}. Super important to know this. Super crucial.
e. aH=Ha iff H=aH(a^-1).
4: External direct product
Let G1, G2,..., Gn be a finite collection of groups. The external direct product of
G1, G2,..., Gn is denoted for this blog as G1#G2#...#Gn is the set of all n-tuples for which the ith component is an element of Gi and the operation is componentwise.
What does all that mean? It means that the external direct product is the set of n-tuples (like an ordered pair, but an ordered... n-tuple) where the first element is produced by using the operation of G1 on all of the "first" elements, the second element is produced by using the operation of G2 on all of the "second" elements, etc. This is weird. I don't quite get it. I'll return to this.
A few things to know about external direct products:
a. The order of an element in a direct product of a finate number of finite groups is the lcm of the orders of the components of the elements.
b. If G, H are cyclic, then G#H is cyclic iff |G| and |H| are relatively prime.
5. Normal subgroups
A subgroup H of a group G is called a normal subgroup of G if aH=Ha for all a in G. This is denoted by H|>G, for this blog.
The normal subgroup test:
A subgroup H of G is normal in G iff xH(x^-1) <= H for all x in G.
Ok, I'm tired, so I'm going to read myself to sleep now. A couple of proofs tomorrow, probably. Probably Disjoint Cycles Commute and the Four Corollaries to Lagrange's Theorem. Fun stuff.
Monday, February 15, 2010
And now, a stumper
Ok, this one's stumping me. Here goes:
Let G be a nontrivial group with no nontrivial proper subgroups.
Claim: |G| is prime.
Sidebar: Here's the problem. Well, the first one. It's easy to say that, if G is of prime order p, then the possible orders of its subgroups are either 1 or p. However, what's there to stop a group G of non-prime order n from not having any nontrivial proper subgroups? This relates back to what I was saying in my last post about how the converse of Lagrange's Theorem is not true. So, I really need to show that, if a group G is of non-prime order n, then it MUST have a nontrivial proper subgroup. Oh, wait. Let H be a subgroup of G, whose order is n and non-prime, and let a belong to G, where |a|=m and m does not equal n; by a corollary of Lagrange's Theorem, m|n. Then, 'a' is a nontrivial proper subgroup of G. So, G MUST have a nontrivial proper subgroup. However, if G is of prime order p, then all of its elements must be of order 1 or of order p, by the same corollary, so 'a'=G or 'a'=e, for all a in G. Great. Excellent. Half down. Now, the second problem. What if G is infinite? Obviously, I need to prove that G CANNOT BE infinite. Then, if it can't be infinite, it must be finite, and, as I've already showed, if it's finite, it's of prime order. So. How do I prove that it can't be infinite? Same way I showed that if its finite, its of prime order. That is to say, I need to show that any infinite group must have a nontrivial proper subgroup. How do I do this? Let's assume that G is an infinite group and that a belongs to G. Then, 'a' must be infinite as well. No help there, right? How about this; it's a little edgy, but I'll give it a go. Let G be an infinite group, and let a belong to G. Then, a possible subgroup of G is {e, a, a^-1}; this is a subgroup because it includes the identity and the inverse of each element, and it's closed. Note that, if G is of prime order, this subgroup doesn't fly: the subgroup has order 3, and, by Lagrange's Theorem, the order of the group is a multiple of the order of the subgroup, so the order of G cannot be prime, which contradicts our assumption. Ok. This feels a little sketch. But I'll go ahead and write it up formally now:
Claim: If G is a nontrivial group with no nontrivial proper subgroups, |G| is prime. \
Pf: Assume that G is a nontrivial group with no nontrivial proper subgroups. First, I need to show that G cannot be infinite. I will do this by contradiction. Assume that G is infinite, that a belongs to G, and |a}=2. Then, define a subgroup H, where H={e, a}. Then, H is a nontrivial proper subgroup of G, which contradicts our assumption that G has no nontrivial proper subgroups. So, G cannot be infinite.
Now, I need to show that |G| is prime. I will do this by contradiction again. Assume that |G| is non-prime. Let a be a non-identity element of G, let |G|=n, let |a|=m, and let m and n be distinct. Then, 'a' is a subgroup of G (I won't prove this; it's in my text as Thm 3.4, so I feel free to call upon it at will). However, because m and n are distinct, 'a' does not equal G (note that, if the orders of G and a are equal, 'a'=G). Then, 'a' is a nontrivial proper subgroup of G, contradicting our assumption that G has no nontrivial proper subgroups. Therefore, |G| must be prime. QED.
Ok, here's the problem I see with this proof: In a finite group G with non-prime order n, what if there are no elements that are of orders other than 1 and n? That is to say, what's stopping a group of order n having 1 identity and then n-1 elements of order n? That's a problem. I kinda just ran myself in a circle, maybe. The first half is solid, though. I'll keep thinking on it.
Let G be a nontrivial group with no nontrivial proper subgroups.
Claim: |G| is prime.
Sidebar: Here's the problem. Well, the first one. It's easy to say that, if G is of prime order p, then the possible orders of its subgroups are either 1 or p. However, what's there to stop a group G of non-prime order n from not having any nontrivial proper subgroups? This relates back to what I was saying in my last post about how the converse of Lagrange's Theorem is not true. So, I really need to show that, if a group G is of non-prime order n, then it MUST have a nontrivial proper subgroup. Oh, wait. Let H be a subgroup of G, whose order is n and non-prime, and let a belong to G, where |a|=m and m does not equal n; by a corollary of Lagrange's Theorem, m|n. Then, 'a' is a nontrivial proper subgroup of G. So, G MUST have a nontrivial proper subgroup. However, if G is of prime order p, then all of its elements must be of order 1 or of order p, by the same corollary, so 'a'=G or 'a'=e, for all a in G. Great. Excellent. Half down. Now, the second problem. What if G is infinite? Obviously, I need to prove that G CANNOT BE infinite. Then, if it can't be infinite, it must be finite, and, as I've already showed, if it's finite, it's of prime order. So. How do I prove that it can't be infinite? Same way I showed that if its finite, its of prime order. That is to say, I need to show that any infinite group must have a nontrivial proper subgroup. How do I do this? Let's assume that G is an infinite group and that a belongs to G. Then, 'a' must be infinite as well. No help there, right? How about this; it's a little edgy, but I'll give it a go. Let G be an infinite group, and let a belong to G. Then, a possible subgroup of G is {e, a, a^-1}; this is a subgroup because it includes the identity and the inverse of each element, and it's closed. Note that, if G is of prime order, this subgroup doesn't fly: the subgroup has order 3, and, by Lagrange's Theorem, the order of the group is a multiple of the order of the subgroup, so the order of G cannot be prime, which contradicts our assumption. Ok. This feels a little sketch. But I'll go ahead and write it up formally now:
Claim: If G is a nontrivial group with no nontrivial proper subgroups, |G| is prime. \
Pf: Assume that G is a nontrivial group with no nontrivial proper subgroups. First, I need to show that G cannot be infinite. I will do this by contradiction. Assume that G is infinite, that a belongs to G, and |a}=2. Then, define a subgroup H, where H={e, a}. Then, H is a nontrivial proper subgroup of G, which contradicts our assumption that G has no nontrivial proper subgroups. So, G cannot be infinite.
Now, I need to show that |G| is prime. I will do this by contradiction again. Assume that |G| is non-prime. Let a be a non-identity element of G, let |G|=n, let |a|=m, and let m and n be distinct. Then, 'a' is a subgroup of G (I won't prove this; it's in my text as Thm 3.4, so I feel free to call upon it at will). However, because m and n are distinct, 'a' does not equal G (note that, if the orders of G and a are equal, 'a'=G). Then, 'a' is a nontrivial proper subgroup of G, contradicting our assumption that G has no nontrivial proper subgroups. Therefore, |G| must be prime. QED.
Ok, here's the problem I see with this proof: In a finite group G with non-prime order n, what if there are no elements that are of orders other than 1 and n? That is to say, what's stopping a group of order n having 1 identity and then n-1 elements of order n? That's a problem. I kinda just ran myself in a circle, maybe. The first half is solid, though. I'll keep thinking on it.
I need a break from actually doing homework, so here's a proof.
Claim: If |G|=8, then G has an element a of order 2.
Pf: A corollary of Lagrange's Theorem states that a^|G|=e for all a in G. Then, a^8=e, implying that the possible orders of a are 1, 2, 4, or 8. By the property of closure, if a is in G, then a^k is in G, where k in any integer. Then, let |a|=8; this implies a^8=e. Then, a^4 is distinct from a^8 and is in G; so, (a^4)^2=e and thus G has an element of order 2. Similarly, let |a|=4; this implies a^4=e. Then, a^2 is distinct from a^2 and is in G; so, (a^2)^2=e and thus G has an element of order 2. If a is of order 2, then, obviously, G has an element of order 2. Finally, if a is of first order, then a=e; however, e can be the only first-order element in any group, so not all 8 elements of G can be e, meaning that there is at least one element of order 2. QED.
That was fun, if a little facile. The interesting thing here is that Lagrange's Theorem states that the order of a subgroup H divides the order of the group G, and, consequentially, the order of any element a in G divides the order of G. This does not imply that G MUST contain elements and subgroups of each divisor of its own order, just that its possible. This problem is oriented towards overcoming the temptation to assume the truth of the converse of Lagrange's Theorem.
Ok. Back to homework. Another proof later, perhaps.
Claim: If |G|=8, then G has an element a of order 2.
Pf: A corollary of Lagrange's Theorem states that a^|G|=e for all a in G. Then, a^8=e, implying that the possible orders of a are 1, 2, 4, or 8. By the property of closure, if a is in G, then a^k is in G, where k in any integer. Then, let |a|=8; this implies a^8=e. Then, a^4 is distinct from a^8 and is in G; so, (a^4)^2=e and thus G has an element of order 2. Similarly, let |a|=4; this implies a^4=e. Then, a^2 is distinct from a^2 and is in G; so, (a^2)^2=e and thus G has an element of order 2. If a is of order 2, then, obviously, G has an element of order 2. Finally, if a is of first order, then a=e; however, e can be the only first-order element in any group, so not all 8 elements of G can be e, meaning that there is at least one element of order 2. QED.
That was fun, if a little facile. The interesting thing here is that Lagrange's Theorem states that the order of a subgroup H divides the order of the group G, and, consequentially, the order of any element a in G divides the order of G. This does not imply that G MUST contain elements and subgroups of each divisor of its own order, just that its possible. This problem is oriented towards overcoming the temptation to assume the truth of the converse of Lagrange's Theorem.
Ok. Back to homework. Another proof later, perhaps.
Sunday, February 14, 2010
A proof
This is a proof of which I'm rather proud.
Claim: |U(n)| is even when n>2.
Pf: It is known that Aut(Z(n)) is isomorphic to U(n). Let a,b be elements if Z(n). Then, a+b=b+a, so Z(n) is Abelian. If a group G is Abelian, then there exists an automorphism P(g)=g^-1. As proof, note that inverses of elements are unique, so P is one-to-one and onto. Further, letting x,y be elements of G, P(ab)=(ab)^-1=(b^-1)(a^-1)=(a^-1)(b^-1)=P(a)P(b), showing that P preserves the operation. This suffices to show that P(g)=g^-1 is an automorphism on a group G. Then, P is an element of Aut(Z(n)). Finally, observe that P(P(g))=g; that is to say, the inverse of the inverse of g is g. This shows that the inverse of P is P, or, more precisely, that P is of order 2. Then, Aut(Z(n)) has at lease one element of order 2. By the properties of isomorphisms acting on elements, if G is a finite group, then G and P(G) have exactly the same number of elements of every order. Then, since U(n) is isomorphic to Aut(Z(n)) and Aut(Z(n)) has an element of order 2, U(n) has an element of order 2. Then, by a corollary of Lagrange's Theorem (specifically, the corollary states |a| divides |G|, or, the order of a group's element a divides the order of the group G), because U(n) contains an element of order 2, the order of U(n) must be a multiple of 2; that is, |U(n)| must be even. QED.
I bet there is an easier way to do this, but the problem specifically required the use of the noted corollary. And, really, this proof is pretty sexy -- it basically just compiles a bunch of other proofs and says, look, the claim's true. That's the definition of a sexy proof right?
Claim: |U(n)| is even when n>2.
Pf: It is known that Aut(Z(n)) is isomorphic to U(n). Let a,b be elements if Z(n). Then, a+b=b+a, so Z(n) is Abelian. If a group G is Abelian, then there exists an automorphism P(g)=g^-1. As proof, note that inverses of elements are unique, so P is one-to-one and onto. Further, letting x,y be elements of G, P(ab)=(ab)^-1=(b^-1)(a^-1)=(a^-1)(b^-1)=P(a)P(b), showing that P preserves the operation. This suffices to show that P(g)=g^-1 is an automorphism on a group G. Then, P is an element of Aut(Z(n)). Finally, observe that P(P(g))=g; that is to say, the inverse of the inverse of g is g. This shows that the inverse of P is P, or, more precisely, that P is of order 2. Then, Aut(Z(n)) has at lease one element of order 2. By the properties of isomorphisms acting on elements, if G is a finite group, then G and P(G) have exactly the same number of elements of every order. Then, since U(n) is isomorphic to Aut(Z(n)) and Aut(Z(n)) has an element of order 2, U(n) has an element of order 2. Then, by a corollary of Lagrange's Theorem (specifically, the corollary states |a| divides |G|, or, the order of a group's element a divides the order of the group G), because U(n) contains an element of order 2, the order of U(n) must be a multiple of 2; that is, |U(n)| must be even. QED.
I bet there is an easier way to do this, but the problem specifically required the use of the noted corollary. And, really, this proof is pretty sexy -- it basically just compiles a bunch of other proofs and says, look, the claim's true. That's the definition of a sexy proof right?
A welcome
Greetings. This blog is in response to my recent Facebook postings of certain mathematical and logical proofs and the solutions to problems in my math classes. This will be my space to brainstorm for stumpers; display proofs and solutions that I've finished; ruminate about math, logic, and anything else I want to ruminate about; and generally work through the academic clutter that fills my brain. Enjoy or not.
Subscribe to:
Posts (Atom)