A Proof Concerning Zorn's Lemma

I sat on this proof for a week and a half before I finally cracked it.

Claim: Every chain in a partially ordered set is included in some maximal chain if Zorn's Lemma holds.

Proof: Let X be a poset, let P(X) be ordered by inclusion, and let S be the set of all chains in X. Since the empty set is in S, S is not empty. So, consider the chain C in S. Now, consider the set of chains C*={D in S: D[union]C is in S}; that is, C* is the set of all chains D included in X such that D[union]C is a chain included in X. Then, C* is a subset of P(P(X)), which, ordered by inclusion, has the maximum element, P(X). So, for all chains in C*, there is an upper bound, namely, P(X). So, by Zorn's Lemma, there is a maximal element in C*, call it M; that is, if there is a chain N in S such that M is a subset of N, then N=M. Since C is in C*, then, C is included in some maximal chain included X. qed.

Pretty sweet little proof, a lot simpler than my early trials, which involved, first, recursion and, second, a recursion-like action on the empty. Hope you enjoyed this as much as I enjoyed working on it. Truly the joy of why I do these things.

Some Proofs on Limits and Continuity

Here are a couple of proofs that I think are nice. By nice, I mean, I like how I proved the claim because the proof is concise, clear, and rigorous.

1. Let f:R->R be a continuous function. For all r in Q, let f(r)=0.
   Claim: f(x)=0 for all x in R.
   Pf: Because f is continuous, for all c in R, for all V=N(f(c);ß), there exists U=N(c;∂) such that f(U) is a subset of V. So, V=(f(c)-ß, f(c)+ß); U=(c-∂, c+∂); and f(U) is contained in V. By the density of the rationals, there is at least one rational number in U, so f(U)=0&f(U\Q). Now, if c is rational, then V=(-ß, ß), which obviously contains 0, but must also contain f(U\Q) for all ß>0. That is, f(U\Q) is between 0 and ß, for all ß, so f(U\Q)=0. If c is irrational, then V=(f(c)-ß, f(c)+ß), which must contain 0. But if f(c)≠0, then, if ß≤f(c), 0 is not in V. So, f(c)=0. qed.
2. This one is pretty facile, but I still liked how I proved it.
   Let f:D->R, with c in D', and lim(x->c)f(x)=L>0.
   Claim: There is V=N*(c, ß): f(x)>0, for all x in R.
   Pf: Pick ß such that ß0. Then, ß>|f(x)-L| implies that f(x)-L>-ß, so f(x)>L-ß. But, by choice, L>ß>0, so L-ß>0, so f(x)>0. That is, let V be the deleted neighborhood of c, N*(c;ß), were L>ß>0. Thus, for all x in V&D, ß>|f(x)-L| implies that f(x)>L-ß<, so f(x)>0. qed.

Proof of Mathematical Principle of Induction and Other Things

Here is a proof of the Mathematical Principle of Induction.

Claim: Let P(n) be a statement for each n in N. P(n) is true for all n in N if: (a) P(1) is true, and (b) for each k in N, if P(k) is true, then P(k+1) is true.

Pf: Assume that the above conditions hold, but that there exists a number n in N such that P(n) is false. Let S be the set S={n: P(n) is false}. S is not empty by assumption, so, by the well-ordering property, there exists a least element of S, say, m. Then P(m) is false. P(1) is true by assumption, so m<1.>

This is a proof of the Archimedean Property of R.

Claim: The natural numbers N are unbounded above in the real numbers R.

Pf: By the completeness axiom, if N is bounded above, then there exists m in N such that supN=m, that is, there is a least upper bound of N. Then, m-1 is not an upper bound of N, so there exists n in N such that n>m-1. Then, n+1>m. But n+1 is in N, which contradicts m being an upper bound of N. qed.

And here's a fun little about supremums.

Claim: Given nonempty subsets A and B or R, let C denote the set C={x+y: x in A, y in B}. If A and B have supremums a and b, respectively, then supC=c=a+b.

Pf: If z is in C, then z=x+y for some x and y in A and B, respectively. Then, z=x+y≤a+b, by the definition of the supremum, so a+b is an upper bound for C. Now, choose any ∂>0. Since a is the least upper bound of A, a-∂ is not an upper bound, so there exists x in A such that a-∂

Here's one about maximums and minimums...

Claim: If S is a closed, bounded subset of R, then S has a maximum and minimum.

Pf: Let S be a closed, bounded subset of R. Then, there exists m in S such that supS=m. Because m is the least upper bound, m-∂ is in S, for all ∂>0, but m+∂ is in R\S; that is, for all ∂>0, N(m,∂)&S and N(m,∂)&R\S are nonempty, so m is a boundary point of S. S is closed, so m is in S. Similarly for a minimum. qed.

And, finally, one about convergent sequences. Enjoy.

Claim: Every convergent sequence is bounded.

Pf: Let the sequence (Sn) converge to s. and let (Sn) be unbounded. Then, letting ∂=1, we get N in R such that n>N and 1>|sn-s|. Then, the triangle inequality implies that |sn|<|s|+1. Letting M=max{|s1|,|s2|,...,|sN|, |s|+1}, then |sn|<=M for all n in N, so (Sn) is bounded.

Ok, that's all for now.

Study Guide 1 for Ring and Field Theory, Midterm 2

So it's midterm time again. Here are some definitions I'll need to iterate on the exam. Later, I might put up some proofs. Honestly, I've found the material this term much easier than last term, so I haven't felt the need to blog as much. Sorry.

• Principal Ideal Domain (PID): An integral domain D is a PID if every ideal is of the form 'a'={ar| r in D}.
• Ring of Polynomials: Let R be a commutative ring. The set of formal symbols R[x]={a(n)x^n+a(n-1)x^(n-1)+...+a(1)x+a(0)| a(i) in R, n is a nonnegative integer} is called the ring of polynomials over R in the indeterminate x. Two elements, a(n)x^n+a(n-1)x^(n-1)+...+a(1)x+a(0) and b(m)x^m+b(m-1)x^(m-1)+...+b(1)x+b(0), are said to be equal iff a(i)=b(i) for all nonnegative integers i. Further, define a(i)=0 when i>n and b(i)=0 when i>m.
• Content of a Polynomial, Primitive Polynomial: In a polynomial ring R[x], the content of the element a(n)x^n+a(n-1)x^(n-1)+...+a(1)x+a(0) is the greatest common divisor of the coefficients, a(i). The element a(n)x^n+a(n-1)x^(n-1)+...+a(1)x+a(0) is said to be primitive if the content is 1 (that is, if at least one coefficient is relatively prime to all the others).
  
• Irreducible Polynomial: Let D be an integral domain. A polynomial f(x) from D[x] that is neither the zero polynomial nor a unit is said to be irreducible if, when f(x)=g(x)h(x), where g(x) and h(x) are in D[x], g(x) or h(x) is a unit in D[x].
  
• Prime Element: Let D be an integral domain, and let a, b, c be in D. The nonzero, non-unit element a is prime if, if a|bc then a|b or a|c.
  
• Vector Space: A set V is said to be a vector space over a field F is V is an Abelian group under addition, and, if for each a in F and v in V, there is an element av in V such that the following conditions hold for all a,b in F and all u,v in V: 1) a(v+u)=av+au; 2) (a+b)v=av+bv; 3) a(bv)=(ab)v; 4) 1v=v.
  
• Linear Independence: A set of vectors S is said to be linearly independent over a field F if there are vectors v1, v2,..., vn from S and elements a1, a2,...,an from F, not all zero, such that a1v1+a2v2+...+anvn=0.
  

Ok, those are the definitions I need to know. Pretty straightforward. The vector space definition is a little long winded, as is the polynomial ring definition, but I'll have to make do... Until proof time, folks.

proofs to come soon...

My internet has been down at my house for a bit now, but you can expect some cool proofs to come soon. Look for a proof to Gauss's Lemma -- it's pretty sexy.
Carry on.

Proofs and Theorems for Exam

Here are some proofs that I may need iterate on the exam. Following that are some theorems that I'll probably need to know.

• Claim: A finite integral domain is a field.
  Pf: Let D be a finite integral domain with unity 1. Let a be any nonzero element in D. I will show that a is a unit. If a=1, it is its own inverse, so I am done. So, assume that a =! 1. Then, let D contain a, a^2, a^3, a^4.... D is finite by assumption, so there must be two positive integers i and j such that i>j and a^i=a^j. Then, a^(i-j)*a^(j)=1*a^j. By cancellation, a^(i-j)=1. Since a=!1, i-j>1. Then, a*a^(i-j-1)=1. So, a^(i-j-1) is the inverse of a. qed.
  
• Claim: The characteristic of an integral domain is 0 or prime.
  Pf: It suffices to show that if the additive order of 1 is finite, it must be prime, because, in a ring with unity, the additive order of 1 is characteristic of the ring. Suppose that 1 has order n and that n=st, where 1<=s, t<=n. Then, 0=n*1=(st)*1=(s*1)*(t*1). There are no zero-divisors in an integral domain, so either s*1=0 or t*1=0. Since n is the least positive integer with the property that n*1=0, we must have s=n or t=n. Thus, n is prime. qed.
  
• Let R be a commutative ring with unity and let A be an ideal of R.
  Claim: R/A is an integral domain iff A is prime.
  Pf: Suppose that R/A is an integral domain and ab in A. Then, (a+A)(b+A)=ab+A=A. So, either a+A=A or b+A=A; that is, either a in A or b in A. Then, A is prime. To prove the converse, observe that R/A is a commutative ring with unity for any proper ideal A. Suppose that A is prime and that (a+A)(b+A)=0+A=A. Then, ab in A. Then, since A is prime, a in A or b in A. Then, a+A=A or b+A=A. That is, there can be no zero-divisors. qed.
  

There are two more that I am encouraged to know, but I don't think I'll need to know proofs. He generally only asks for proof of a theorem found in the book, but gives us three or four different options and lists five different theorems on the study guide. So, I'll be fine if I know these three.
Here are some theorems that I'll probably need to know:

• Cancellation: Let a, b, c be in an integral domain. If a=!0 and ab=ac, then b=c. NOTE: THIS IS NOT DIVISION.
  
• A finite integral domain is a field.
  
• For every prime p, Z(p) is a field.
  
• Let R be a ring with unity 1. If 1 has infinite additive order, then the characteristic of R is 0. Else, if 1 has order n, then the characteristic of R is n.
  
• The characteristic of an integral domain is 0 or prime.
  
• R/A is an integral domain iff A is prime.
  
• R/A is a field iff A is maximal.
  
• The kernel of any homomorphism is an ideal the ring.
  
• Every ideal A of a ring R is the kernel of a ring homomorphism r-->r+A from R to R/A.
  
• A ring with unity contains Z(n) or Z.
  
• A field contains Z(p) (if char=n) or Q (if char=0).
  

Ok, that's about all I need to know. Not bad, really. Its just the first midterm. Not bad at all.

Study Guide for Ring and Field Theory

Here are some definitions for the upcoming Ring and Field Theory midterm.

• Ring: A ring R is a set with two binary operations -- generally called addition and multiplication -- such that, for all a, b, c in R, the following properties hold:
  

1. a+b=b+a (the ring is commutative under addition)
2. there exists an additive identity element called 0 such that 0+a=a+0=a
3. there exists an additive inverse of each element such that a+(-a)=0
4. a+(b+c)=(a+b)+c (the ring is associative under addition)
5. (ab)c=a(bc) (the ring is associative under multiplication)
6. a(b+c)=ab+ac and (b+c)a=ba+ca (multiplication distributes over addition.
   Examples: Z; nZ; M2(Z), or the ring of 2x2 matrices with integer entries; Z[x], ring of polynomials with integer coefficients

• Zero-divisor: In a ring R, an element a is a zero-divisor if there exists an element b such that ab=0.
  Examples: in Z(4), 2 is a zero-divisor.
  
• Integral domain: An integral domain is a ring R such that R has unity (a multiplicative inverse), R is commutative, and there are no zero-divisors.
  Examples: Z; M(2)Z; Z(p), where p is prime; NOT Z(n), where n is NOT prime.
  
• Field: A field F is a ring such that F has unity, F is commutative, and every nonzero element in F has a multiplicative inverse.
  Examples: R; Q; any finite integral domain; Z3(i).
  
• Characteristic of a ring: The characteristic of a ring R is the smallest positive integer n such that, for all a in R, na=0. If no such positive integer exists, then the characteristic is 0.
  Examples: In Z(n), the characteristic is n; in Z, the characteristic is 0; in Z[x], the characteristic ic 0.
  
• Ideal: An ideal I is a subring of a ring R such that, for all a in I and for all r in R, ar and ra are in I.
  Examples: In Z, nZ is an ideal; in Z[x], nZ[x] is an idea; in a commutative ring R with 1 and a, the set , where 'a'={ra| r in R} is called the principle ideal generated by a; similarly, the set 'a,b'=(r1a+r2b| r1, r2 in R}, and so on.
  
• Prime ideal: An ideal I is prime if it is a proper ideal and if ab in I implies that a is in I or b is in I.
  Examples: In Z, nZ is a prime ideal iff n is prime.
  
• Maximal idea: A proper ideal I is maximal to R if, given an ideal I', I subsets I' implies that I=I' or that I'=R.
  Examples: In Z, nZ is maximal iff n is prime; is maximal in Z[x].
  
• Ring Homomorphism: A ring homomorphism P is a mapping from a ring R to a ring S such that, for all a,b in R, P(a+b)=P(a)+P(b) and P(ab)=P(a)P(b), that is, if P preserves both operations.
  Examples: if P maps all elements in R to 0, then P is a homomorphism; there is no homomorphism from 2Z to 3Z (or to 4Z); for any pos int n, the mapping from k to kmodn is a ring homomorphism.
  

Proofs to come soon.
Bubye.

Nasty little problem,,,

This is a problem that's been stumping me for a few hours now.
Let R be a commutative ring with unity. Let x and y be in R, such that x is a unit and y is nilpotent.
Claim: (x+y) is a unit.
Side Bar: Ok, here's what that means: x is unit implies that there exists b in R such that xb=1, or, that x has a multiplicative inverse. y is nilpotent implies that there is a positive integer n such that y^n=0. I want to show that there exists c in R such that (x+y)c=1, or that (x+y) has a multiplicative inverse. Observe that, if we set c to y^(n-1), then we get x*y^(n-1). If I can show that that has a multiplicative inverse, then I'll be done. But I'm not sure that that is the way to go. How about this instead: (x+y)(a+b)=1. Hmmm, that has potential. Then, xa+xb+ya+yb=1. Now, let a=x and let b=-y. Then, xa+xb+ya+yb=x^2-y^2. Wait, multiply this by x^2+y^2. Then, we have x^4-y^4. Do this enough times, and eventually, you'll get to y^n or y to some number that is greater than n, which amounts to the same thing, namely, y goes to 0. Then, we are left with x^m. Does x^m have a multiplicative inverse? Well, of course, it does. x^m=x*x^(m-1), and x is a unit. So, multiply x^m by x^-m and you get 1. Pretty facile, I know, but it's worth explaining these things. So, now for the actual proof.
Pf: Observe that multiplying x+y by (x^-m)(x-y)*II(x^i+y^i), i=2, m, where m is sufficiently large (n is fine), you have (x^-m)(x^m-y^m). But, y^m=0, so, you have x^-m*x^m, which is 1. So, x+y is a unit; specifically, its multiplicative inverse is (x^-m)(x-y)*II(x^i+y^i), i=2, m, where m is a number such that the product of the nonzero even numbers preceding m is greater than or equal to n. QED.

I hope... I bet there is an easier way to SHOW that there must be an inverse, other than actually FINDING the inverse... I'll keep thinking on this.

Welcom Back to Blogdom

Ok, ok, I'm back. Keep your yappers shut, I know you all missed me.
So I'm taking Ring and Field Theory this term, which is a branch of group theory.
Here is a proof that has been stumping me for a bit now. I think it's clever more than anything...

Suppose that R is a commutative ring and |R|=30, with an ideal I, where |I|=10.
Claim: I is a maximal ideal of R.
Sidebar: The order of R is 30, and, by Lagrangre's Theorem, the order of any subset divides the order of the group. Then, there are supgroups of order 10 and order 15 (call them I and J). But we aren't talking about groups, we're talking about rings. We know that there is a subring of order 10 (I). So, I need to show that I is not a subset of J or that J is not a subring (although it is a subgroup). A third possibility is to show that all groups of order 30 are isomorphic to Z(30), at which point I can fairly easily prove that I is maximal. No, I just Googled it: not every group of order 30 is isomorphic to Z(30). Wait. Wait. Wait. In I, there are elements of order 2 (because |I|=10=5*2), whereas in J, there are no elements of order 2 (because |J|=15=5*3). So, I is not a subset of J. And, by Lagrange's Theorem, there can be no other subgroups. So, I is maximal. Incidentally, J is maximal, too. Now, the formal proof.
Pf: Let R be a commutative ring, with |R|=30, and two ideas, I and J, where |I|=10 and |J|=15. By Lagrange's Theorem, there can be subgroups (and, so, subrings) of orders that divide the order of the group (or, rather, ring). Then, there can be no proper subring of order greater than 15. So, either I is maximal or J is maximal (or both). If I is not maximal, then I is a subset of J. However, I contains elements of order 2 (by Lagrange's Theorem and because 10=2*5), whereas J does not (by Lagrange's Theorem again, and because 15=3*5). So, I cannot be a subset of J. So, I is maximal. Incidentally, if there even exists a subring of order 15, then J is also maximal. QED.

Here's another that's been stumping me:
Question: Is the ring 2Z isomorphic to the ring 3Z?
Answer: Assume that 2Z is isomporphic to 3Z, where P is such an isomorphism. Then, by principal, 3Z is isomorphic to 2Z, where P(inv) is such an isomorphism. The ring 3Z has unity 1, so P(inv)(1)=1*, where 1* represents the unity of 2Z. However, no such unity exists. Then, 1 cannot map to 1*, so there is no such isomorphism P(inv). So there is no such isomorphism P, which contradicts our initial assumption.
Question: Is the ring 2Z isomorphic to the ring 4Z?
Answer: This one is a little more tricky. It feels obvious to me, frankly, that they are. They are both infinitely countable, so any mapping can be one-to-one and onto. Hmmm, let's see. Let P be such an isomorphism. Then, P(2)=4n, n in Z. Then, P(2*2)=P(2+2), implies that P(2)*P(2)=P(2)+P(2), which implies that 4n*4n=4n+4n, which implies that 16n^2=8n, which implies that 2n=1, which is impossible. So, we have a contradiction, so P cannot exist. Well, well, well, my intuition was wrong. The two aren't isomorphic. Incidentally, I can use this same method for the previous problem.

That all took me way too long. Time to get it formally written up, then off to read more ethics.

Good Morning, Proof!

Here is the third proof (or, rather, set of proofs) I'll be expected to know.
Properties of Elements and Subgroups Under Homomorphisms
Let G and G' be groups, where P maps G into G', and H is a subgroup of G.

1. Claim: P maps the identity of G to the identity of G'.
   Pf: This proof is the same as the proof for property 1 of the previous set of proofs. But I'll do it again for practice. P(e)=P(ee)=P(e)P(e), and e'P(e)=P(e). So, e'P(e)=P(e)P(e), implying that e'=P(e). qed
2. Claim: P(g^n)=[P(g)]^n.
   Pf: Again this is the same as property 2 of the previous set of properties. If n is positive, then the claim follows by mathematical induction and by the definition of homomorphisms. If n=0, then the claim follows by the previous property. If n is negative, then -n is positive. Then, P(e)=P((g^n)(g^-n))=P(g^n)P(g^-n)=P(g^n)[P(g)]^-n. Then, P(g^n)=[P(g)]^n. qed
3. Claim: If |g| is finite, then |P(g)| divides |g|.
   Pf: Let |g|=n. Then, g^n=e. Then, e=P(e)=P(g^n)=[P(g)]^n. Then, by Thm 4.2, |P(g)| divides n=|g|. qed
4. Claim: KerP is a subgroup of G.
   Pf: By property 1, KerP is nonempty. Let a,b be in KerP. Then, P(a)=P(b)=e. Then, P(ab^-1)=P(a)P(b^-1)=P(a)[P(b)]^-1=ee^-1=e. Then, ab^-1 is in KerP, so KerP is a subgroup of G. qed
5. Claim: P(a)=P(b) iff aKerP=bKerP.
   Pf: I will prove the statement "If P(a)=P(b), then aKerP=bKerP" first. Assume that P(a)=P(b). Then, e=P(a)[P(b)]^-1=P(a)P(b^-1)=P(ab^-1), which is in KerP. By property 5 of the Lemma of Cosets, iff ab^-1 is an element of a subgroup H, then aH=bH. Then, the claim follows. Now, conversely, assume that aKerP=bKerP. Then, by the same property of the Lemma of Cosets, P(ab^-1) is in KerP, and so on backwards to P(a)=P(b). qed

There is a bunch more, but I think I get the general idea. Besides, I'll be asked to prove one of several, and I doubt I'd choose this one. I'll probably choose the set of properties in the last posting. Ok, back to PHL.

Another Group Proof

Need a breather from PHL, so here's another group theory proof.
Properties of Isomorphisms Acting on Elements and Subgroups
Let G and G' be groups, and let P map G to G'. Let H be a subgroup G.

1. Claim: P maps the identity of G to the identity of G'
   Pf: Because e=ee, P(e)=P(ee)=P(e)P(e). Also, because P(e) is in G', P(e)=e'P(e). Then, e'P(e)=P(e)P(e) --> e'=P(e). qed
2. Claim: For every integer n and for every group element a in G, P(a^n)=[P(a)]^n.
   Pf: By definition of isomorphisms and by mathematical induction, if n is positive, then the claim is true. If n=0, P(a^n)=P(a^0)=P(e) and [P(a)]^n=[P(a)]^0=e. If n is negative, then -n is positive, and we have from the first claim and mathematical induction that e=P(e)=P([g^n][g^-n])=P(g^n)P(g^-n)=P(g^n)[P(g)]^-n =e. Then, P(g^n)=[P(g)]^-(-n)=P(g)^n. qed
3. Claim: For any elements a and b in G, a and b commute iff P(a) and P(b) commute.
   Pf: I will prove the claim "P(a) and P(b) commute if a and b commute" first. Assume that a and b commute. Then, ab=ba. P(ab)=P(a)P(b) and P(ab)=P(ba)=P(b)P(a), so P(a)P(b)=P(b)P(a). Now I will prove the converse. Assume that P(a) and P(b) commute. Then, P(a)P(b)=P(b)P(a). Then, P(a)P(b)=P(ab)=P(b)P(a)=P(ba), so P(ab)=P(ba). Because P is one-to-one, ab=ba. qed
4. Claim: G='a' iff G'='P(a)'.
   Pf: I will prove the claim "G'='P(a)'" first. Let G='a'; then, by closure, 'P(a)' is a subset of G'. Because P is onto, for any element b in G', there is an element a^k in G such that P(a^k)=b. Thus, b=[P(a)]^k, so b is in 'P(a)'. Then, G'='P(a)'. Now I will prove the converse. Suppose that G'='P(a)'. 'a' is a subset of G (by closure, etc.). For any b in G, we have P(b) is an element of 'P(a)'. Then, for some integer k, we have P(b)=[P(a)]^k=P(a^k). Because P is one-to-one, b=a^k. Then, G='a'. qed
5. Claim: Isomorphisms preserve orders.
   Pf: Let g be in G, where |g| is n. Then, P(g^n)=P(e)=e and P(g^n)=[P(g)]^n. So, [P(g)]^n=e. So, |P(g)|=|g|. qed
6. Claim: If G is finite, then G and G' have exactly the same number of elements of every order.
   Pf: By property 5, elements of order n map to elements of order n. Then, G and G' must have the same number of elements of each order. qed
7. Claim: G is Abelian iff G' is Abelian.
   Pf: By property 3, this property follows.
   
8. Claim: G is cyclic iff G' is cyclic.
   Pf: By property 4, this property follows.
   
9. If K is a subgroup of G, then P(K) is a subgroup of G'.
   Pf: Let a,b be in K, and P(a)=c and P(b)=d. I need to show that cd^-1 is in P(K). By definition, c and d are in P(K). P(ab^-1)=P(a)P(b^-1)=P(a)[P(b)]^-1=cd^-1, which is in P(K) by closure.
   

That was fun. Now, back to PHL.

Here's a proof to kick off my monster study sess

So I'm supposed to be studying crazy hard for this PHL final, but I'm not really feelin' it. So I'm going to spend a little time doing a proof or two for Group first, to get me motivated. Here goes:
The Fundamental Theorem of Cyclic Subgroups
Claim: Every subgruop of a cyclic group is cyclic. Moreover, if |'a'|=n, then the order of any subgroup of 'a' is a divisor of n; and, for each positive divisor k of n, the group 'a' has exactly one subgroup of order k -- namely, 'a^(n/k)'.
Pf: Let G='a' and suppose that H a subgroup of G.
To prove the first claim (that every subgroup of a cyclic group is itself cyclic), we need to show that H is cyclic. Assume that H does not equal just the identity e. I claim that H contains an element of the form a^t, where t is positive. Since G='a', every element of H has the form a^t; and, when a^t belongs to H with t<0, h="'a^m'." g="'a'," b="a^k" k="mq+r," k="a^(mq+r)="(a^mq)(a^r)-">a^r=(a^-mq)(a^k); since a^k and a^-mq are both in H, a^r is in H. However, m is the least positive integer such that a^m is in H, but r is less than m and greater than or equal to 0. So, r=0, implying that b=a^k=a^-mq=(a^m)^q which is in 'a^m'. Then, the arbitrary element b is in the cyclic subgroup of H 'a^m', so H='a^m', so H is cyclic. This proves the first claim.
To prove the second claim (if |'a'|=n, then the order of any of 'a' will be a divisor of n), suppose that |'a'|=n and H is a subgroup of 'a'. H is cyclic, so let H='a^m', where m is the least positive integer such that a^m is in H. Let b=a^mq again, such that a^mq=e. Then, e=a^mq=b=a^n, implying that mq=n. So, the order of the subgroups of a cyclic group divide the order of the group.
To prove the third and final claim (for each positive divisor k of n, the group 'a' has exactly one subgroup of order k, 'a^(n/k)'), let k be any positive divisor of n. I need to show that 'a^(n/k)' is the one and only subgroup of 'a' of order k. |'a^(n/k)'|=n/gcd(n,n/k)=k. Now, let H be any subgroup of 'a' of order k. I know that H='a^m', where m divides n. Then, m=gcd(n, m) and k=|a^m|=|a^gcd(n,m)|=n/gcd(n,m)=n/m. Thus, m=n/k, and H='a^(n/k)'.
qed

That was pretty confusing. I need to work on that one.
Ok, PHL time. I'll publish another one in a bit.

Three Problems from Discrete

Here are three problems from the review sheet for Discrete Math. They are all counting problems. I'll post other types, too, but these ones are the trickiest, personally.

1. Question: In how many ways can 12 (identical) apples be distributed among 5 (distinct) children so that no child gets more than 7 apples?
   Solution: This is a "bins" problem. Let's look at the total number of ways of distributing the apples, without the qualifier. There are 12 apples and 5 children; thinking of the children as apple-receptacles (bins), there are 4 dividers between the 5 bins. So, there are 12+4=16 total objects -- 12 items and 4 dividers -- so I need to decide where to put 12 apples OR 4 dividers in a total of 16 objects. Then, the total number of ways to distribute the apples is 16C12=16C4. However, this includes the possibility that one kid will have at least 7 apples. Let's now assume that one kid does indeed at least 7 apples; giving him or her 7 apples off the bat reduces our number of objects from 16 to 9. So, there are 9C5=9C4 ways of distributing the remaining 5 apples. However, there are 5 different kids, so each of these combinations can occur 5 different times. So, there are really 5(9C5) ways of distributing the remaining 5 apples. Of course, we want the situation in which this DOESN'T happen, so the real solution is the total distributions minus the unwanted distributions, or 16C4-d(9C4).
   
2. Question: How many arrangements of all of the letters of JUPITER are there with the vowels occurring in alphabetical order (but not necessarily consecutively)?
   Solution: Let's focus just on the vowels first. There are three vowels, and they need to be in the order EIU. There are seven spaces total, so there are 7C3 ways to distribute the vowels; of course, if there were no alphabetical qualifier, then there would be 3(7C3) ways to distribute the vowels, but, since they MUST go in a certain order, there is really 1(7C3) ways. Now, we have 4 remaining letters, each of which must be used once. So, there are 4! ways to distribute them. Then, there are 4!(7C3) possible arrangements.
   
3. Question: At a birthday party, 36 identical balloons are distributed to 8 distinct children. If the balloons are distributed randomly, what is the probability that one child will get 20 or more balloons?
   Solution: This is a probability question, so I'm going to do it in 2 (or 3) steps. First, I'm going to figure out what the denominator will be. In this case, it will be the total ways of distributing the 36 balloons. Again, this is a bins problem, and there are 36 items and 8 bins (with 7 dividers), so there are 43 objects. Then, the total number of distributions is 43C7. This is the denominator. However, we want the ways in which the one kid gets 20 or more balloons. This will be the numerator. Let's give one kid 20 balloons, just give 'em away. Then, there are 23 objects left (36-20+8-1=23). So, there are 23C7 distributions; again, however, there are 8 kids, so the numerator is 8(23C7). Then, the probability is 8(23C7)/(43C7).
   

These are just my answers. I'll edit in corrections when the answers are posted. Tomorrow (or maybe later today), expect some problems concerning recurrence relations, functions, and equivalence relations. For now, I'm off to study PHL.

Group Theory Final Study Guide 1

So, I'll be posting study guides for Group Theory and PHL in chunks over the next few days. I'll also be posting some problems from the Discrete Math review sheet. What can I say? It's crunch time, folks...
I'll be expected to know the definitions of the following terms for my Group Theory final:

1. Group
2. Order of an element
3. Factor group
4. Group homomorphism
5. Kernel of a homomorphism

Ok, here goes. Keep in mind, this is from memory as much as possible.

1. Group: A group G is a set with a binary operation that has the following characteristics: 1) It is transitive; that is, for all a,b,c in G, (ab)c=a(bc). 2) There is an identity element e, such that, for all a in G, ae=ea=a. 3) There are inverses; for all all a in G, there is an element b in G such that ab=ba=e.
   
2. Order of an element: In a group G with element g, the order of g is the smallest positive integer n such that g^n=e.
   
3. Factor group: Define a group G with a normal subgroup H. The factor group G/H is defined as G/H={aH| a in G}, under the operation (aH)(bH)=abH. What does this mean? It means that G/H is the set of all (distinct) cosets of H in G, under the specified operation. It should be noted that the orders |aH| and |a| may not be equal. In fact, even though H contains e, the identity of G/H is NOT e, but, rather H (specifically, it is eH). Further, note that (aH)^2=(a^2)H, NOT (a^2)(H^2). Just remember that G/H is a set of (distinct!) cosets of H in G under the operation aH*bH=abH. And breath deep.
   
4. Homomorphism: A homomorphism P on a group G is a mapping from G into G' that preserves operation; that is, for all a,b in G, P(ab)=P(a)P(b). A few things to note: P maps INTO not ONTO; rather, not necessarily onto.
   
5. Kernel of a homomorphism: Define a group G and a homomorphism P that maps G to G' with the identity element e. Then, the kernel of P is KerP={x in G| P(x)=e}; that is, the kernel is the set of all elements in G that are mapped to the identity of G' by P.
   

Here are some things to remember about homomorphisms:

1. P carries the identity of G to G'.
   
2. P(g^n)=(P(g))^n for all n in Z. This means that...
   
3. If |g| is finite, then |P(g)| divides |g|.
   
4. KerP is a subgroup of G.
   
5. P(a)=P(b) iff aKerP=bKerP. I'll come back to this one, I think...
   
6. If P(g)=g', then Pinv(g')={x in G| P(x)=g'}=gKerP. This means that Pinv(g') is a SET, not necessarily just one element. Also, note that P(KerP)=e and P(gKerP)=g'. Interesting...
   
7. If H is a subgroup of G, then P(H) is a subgroup of G'.
   
8. If H is cylic, then P(H) is cylic.
   
9. If H is Abelian, then P(H) is Abelian.
   
10. If H is normal, then P(H) is normal.
    
11. The order of P(H) divides the order of H.
    
12. KerP is always normal to G.
    
13. If P is onto and KerP={e}, then P is an isomorphism from G onto G'.
    

Here are some things to remember about factor groups:

1. If G/Z(G) is cyclic, then G is Abelian.
   
2. G/Z(G) is isomorphic to Inn(G).
   
3. Cauchy's Theorem for Abelian Groups: Let G be a finite Abelian group and let p be a prime that divides the order of G. Then G has an element of order p.
   

That's all for the moment. The super important things to recall will be the properties of homomorphisms and Cauchy's Theorem. That's a lot of properties to recall about homomorphisms.
I'll post some proofs on Sunday, and some properties and examples and such on Monday or Tuesday. Also, expect some problems from Discrete later tonight.
Ciao.

Here's the final draft of my paper on mathematical statements as analytic statements. I'm very pleased with how it turned out. I didn't spend as much time on how identity statements are analytic as I would have liked, but I think that I did focus on things that were within the scope of a 4-ish page paper. Let me know what you think.

Mathematical Statements as Analytic

I claim that statements of mathematics are analytic. This challenges Kant’s view of mathematical statements. First, I will try to show why Kant’s reasoning may be contradictory. Then, taking each of his criteria independently, I will examine them in relation to mathematical statements. Finally, I will identify and address likely flaws in my arguments.

Allow me to point out a potential contradiction in Kant’s argument. Kant defines analytic and synthetic statements as follows: an analytic statement is a statement in which the predicate adds no new content to the concept of the subject; a synthetic statement is a statement in which the predicate does add new content to the concept of the subject (Ayer, 77). In the example “7+5=12”, he reasons that, because the reader can conceptualize “7+5” without conceptualizing “12” and vice versa, it must be synthetic. Finally, in the example, “all bodies take up space”, he argues that the truth of “all bodies take up space” is subject to the Law of Non-Contradiction (Ayer, 77). It would seem that, according to Kant, all three of these criteria are equivalent. Here, then, is a contradiction. Assume that “7+5=12” is synthetic by Kant’s reasoning. However, it cannot be true that “7+5=12" and 7+5=(not)12.” So, the truth of the statement is subject to the Law of Non-Contradiction. Then, it must be analytic. However, the statement cannot be both analytic and synthetic. So, if Kant is asserting that his three criteria are equivalent, then he appears to contradict himself (Ayer, 78). For the sake of this paper, I will consider all three of his criteria, in the hopes of showing that, regardless of which is chief among them (which is outside the scope of this paper), mathematical statements will be held analytic.

Let us first examine the psychological criterion: the subject and the predicate can be conceptualized independently in a synthetic statement and not independently in an analytic statement (B/F, 140). What does it mean to conceptualize objects such as “7+5” and “12”? I maintain that the concept of the complex object “7+5” is the union of the concepts of the objects “7”, “+”, and “5”. What, then, is the concept of the object “7”? I claim that we have no way of conceptualizing “7” without conceptualizing fundamental numbers and operations. Conceptualize an integer “n”. Now, conceptualize the integer immediately following “n”. Of course, you probably thought of “n+1”; then, in order to conceptualize any number, we must rely on at least addition and “1”. What about, the reader may protest, very large numbers, say 792? We have no way to conceptualize the object “792” as a value independent of its component values; when we think of “792”, we really think of “”7(10^2)+9(10^1)+2(10^0)”. That is to say, we cannot conceptualize any number without at the same time conceptualizing addition, multiplication, exponentiation, and the numbers “0”, “1”, and “10” (and division, for rational numbers, etc.). Then, by this argument, when we examine the statement “7+5=12”, the ideas of “7”, “+”, and “5” are all entailed in “12”, because we must conceptualize repeated addition of “1” for “7”, “5”, and “12”. It would appear, then, that the statement is analytic.

Next, let us examine the logical criterion: the relation between the subject and predicate is subject to the Law of Non-Contradiction in an analytic statement and not in a synthetic statement (Ayer, 77). Kant gives the statement “all bodies are heavy” as an example of a synthetic statement that fails this criterion, and “all bodies are extended” as an example of an analytic statement that fulfills this criterion. Certainly, it is possible for a body to be heavy and not heavy, whereas it is impossible for a body to take up space and not take up space. However, as I have pointed out, it is impossible by the definitions of the constituent symbols that “7+5=12” and “7+5=(not)12” are both true statements. Then, the statement would again seem to be analytic.

Finally, we come to Kant’s original definitions: an analytic statement is a statement in which the predicate adds no new content to the concept of the subject; a synthetic statement is a statement in which the predicate does add new content to the concept of the subject. This is a criterion of neither psychology nor logic, but, rather, of semantics (B/F, 140). That is to say, what the reader knows is not relevant to this distinction; what are relevant are the definitions attributed to the subject and predicate. Is there content in the predicate that is not present in the subject? What exactly does Kant mean by “content”? I hold that “content” refers to the set of properties attributed to an object. Then, all “bodies” have the property “being extended” but not “being heavy.” How does this help us make sense of the contents of “7+5” and “12”? What sort of property could be attributed to “12” that is not attributed to “7+5” or vice versa? The canny reader might say that “7+5” has the property of being two numbers added together, whereas “12” is only one number. However, since “12=7+5”, “12” has the property of being two numbers added together, as well; similarly, “7+5” has the property of having one value, namely, “12”. I claim that, because “7+5” and “12” are related through an identity, no new content can possibly be added to the subject by the predicate. The set of properties of “7+5” is the same as the set of properties of “12”, so “12” can attribute to “7+5” no new properties. Observe that this is without regard to what the reader comprehends; the reader might be under the impression that “7+5=0”, but, still, by the definitions of the constituent symbols, no new content can possibly be added to “7+5” by “12”. And, again, the statement would appear to be analytic.

My reasoning is not without flaws. In the case of the psychological criterion, one might note that irrational numbers cannot possibly be conceptualized through fundamental numbers and operations, because they cannot be expressed as one integer over another non-zero integer. However, they can be expressed as an infinite sum of rational numbers, and, since (it seems to me) we cannot conceptualize “infinity,” we cannot conceptualize a number that is defined as an infinite sum of numbers. Then, we can only conceptualize approximations of irrational numbers. However, if this is true, is it also true that “pi=3.1415” since our concept of pi is 3.1415 (or more digits, depending on one’s accuracy)? Certainly not, regardless of to how many decimal places you extend the predicate. So, it seems that we have some concept of pi that exceeds the aid of other fundamental numbers and operations, puncturing a hole in my argument that all numbers must be conceptualized as such. In the case of the semantic criterion, it could be noted that, however much I want to eschew the reader, there must be one. A statement cannot be viewed purely in terms of its semantics; the reader always brings conceptualizations to it. We cannot escape psychology. I have little response to this attack. Let us assume that the statement “7+5=12” is presented to a person who does not understand the constituent symbols. By the argument for the semantic criterion, they need not be able to for the statement to be analytic, since the statement is true by definition of those symbols. However, this regresses: there must be someone who knows the definition of the symbols, someone who can conceptualize them, or else the statement would be without meaning. I admit that this is a dire flaw in my argument for the semantic criterion, and leads down epistemic paths beyond the scope of this paper. Finally, my claim stated, “Statements of mathematics are analytic,” yet I have only taken the example “7+5=12.” The mathematically-minded reader should observe that, in order to fully demonstrate the veracity of my claim, I would need to also examine statements of inequality and functions (especially functions that are not one-to-one or onto). However, this is again beyond the scope of this paper.

I believe that I have adequately showed how Kant’s reasoning leads to a contradiction if one assumes that his semantic, logical, and psychological criteria are equivalent. Then, taking them to be separate, I hope to have given the reader cause to believe that mathematical statements are analytic by each criterion. It is outside the range of this paper, however, to explore whether Kant is truly assuming the equivalence of his criteria, and, if he is not, to choose which shall hold priority in making the distinction between analytic and synthetic statements.

Works Cited

Ayer, Alfred Jules. Language, Truth, and Logic. New York: Dover Publications, Inc, 1946.

Baggini, Julian, and Peter S. Fosl. The Philosopher’s Toolkit. Malden: Blackwell Publishing, 2003.

Kant and Stuff

So, I'm writing this paper for my philosophy class. It's about the distinction between analytic and synthetic statements. Specifically, I argue that all mathematical truths are analytic statements. Kant gives the following definitions. An analytic statement is a statement in which the predicate adds no new content to the concept of the subject. A synthetic statement is a statement in which the predicate adds new content to the concept of the subject. He also claims that the statement "7+5=12" is synthetic. That is, he claims that the concept of "12" is not entailed in the concept of "7+5". I would disagree for a few reasons (I know, bold, right? Disagreeing with Kant... sheesh), but there's a point I'd like to brainstorm a bit, instead. What does Kant mean by "concept of the subject"? Why didn't he just say "adds new content to the subject"? What is the difference between "the subject" and "the concept of the subject"?
After a lot of thought, I think that what Kant is saying is that "7+5" contains the concepts "7", "5", and "+", whereas "12" contains only the concept "12". Specifically, the idea of addition is not contained within "12", whereas it is in "7+5". I would disagree, and here's my argument: Conceptualize the integer n. Now, conceptualize the integer immediately following n. Of course, you probably conceptualized n+1. In doing so, you conceptualized addition. I would claim, then, that all numbers require the conceptualization of addition, multiplication, or exponentiation. For example, take the number 352. We use the decimal system, so we have ideas of "1", "10" and "100". ("Ah, a regress! How do we have those concepts?" you say, to which I politely reply, "See my inductive argument above for the concept of the number 10, and so on.") So, when we conceptualize "352", we really conceptualize "3*10^2+5*10^1+2*10^0". We have no concept of what "352" is without the concepts of addition, multiplication, and exponentiation. Or, at least, that's how it seems to me. So, in short, if Kant's reasoning for the synthetic status of "7+5=12" is that "7+5" contains addition and "12" does not, I would heartily disagree. Again, that's how it seems to me, that's how I look at numbers. I wouldn't know what 352 is without basic operations. For that matter, I wouldn't know what 7 is without the ideas of "1" and "addition". Maybe I'm crazy...

PHL and Group Theory Midterm Re-Hash

I was reunited with two midterms today, and what glorious reunions they were! The first was PHL, Methods and Concepts. Here are some of the things that I missed, and some things that the prof liked in particular:

1. A regress is a fallacy in which the logic of the argument requires the existence of a prior, or meta, object, which, in turn, requires the further existence of a prior or meta object, ad infinitum. Then, there is no stable, logical truth for the argument to be based on, so it cannot prove anything. Apparently, this definition, which I put forward in my exam, was not satisfactory. I believe that this is because of the ambiguity of the phrase "stable, logical truth for the argument to stand on," which employs the metaphors of stability and standing. However, the definition itself is correct, just slightly unclear.
   
2. The prof apparently enjoyed my comments about the masked man fallacy: "Are knowledge, beliefs, and perceptions of an object essential qualities of an object?" This is the key of the masked man fallacy; in fact, knowledge, beliefs, and perceptions are not essential qualities. As I wrote in my exam, "an object is identical to another object regardless if I know it is. An object's identity or essence is not related to how that object is perceived." I think I rocked the masked man fallacy.
   
3. Category mistakes were the worst of it. A category mistake is a fallacy in which an object is taken to mean something other than what it actually means; more formally, it is a fallacy in which an object is attributed qualities that cannot be applied to it. The category mistake in the statement, "The average employee of Golman Sachs made $563447 last year", then, is this: the average employee is not an actual employee, there to greet you at the door, nor is it some ghostly spirit-employee. It is a mathematical construction based on statistics. Simple as that.
   

Very pleased with how that turned out. I'm going to post some ruminations about my upcoming paper here in a bit: Mathematical Truths as A Priori Analytic Truths.

The second exam I got back today was Group Theory. I anticipated a low-mid A... and I was not disappointed in my assessment of my work. Again, here are the problems in which I lost points:

1. I lost one point because I just didn't read the problem fully and forgot to determine whether the permutation A was even or odd. A=(29)(24)(13)(17)(15). Because there are an odd number of 2-cycles, A is an odd permutation. Pretty easy, just forgot it. I think he was pretty lenient in only taking off one point, for which I am thankful.
   
2. I made a leap-o'-logic in the one-to-one part of the following proof. Let G be a finite Abelian group of order 12. Claim: the mapping P: G->G, defined by P(x)=x^5, is an automorphism. Pf: P is an automorphism iff P is one-to-one, onto, and operation preserving. One-to-one: Let a,b be in G and P(a)=P(b). Then, a^5=b^5. This implies that (a^5)(b^-5)=e=(ab^-1)^5. Then, the order of (ab^-1) must be 5; however, by Lagrange's Theorem, the order of the group (12, in this case) is divisible by the order of the element. Because 5 does not divide 12, the order of (ab^-1) cannot be 5. The only other option, then, is that (ab^-1)=e, implying that a=b. So P is one-to-one. Onto: Since G is finite and one-to-one, then it is onto as well. [Note: I did a little proof of onto-ness, but I really didn't need to; I'll keep this little fact in mind for next time.] Operation Preserving: P(ab)=(ab)^5=(a^5)(b^5)=P(a)P(b). So P is operation preserving. So, P is an isomorphism.
   
3. Question: Are the groups Z(2)#Z(5) and Z(10) isomorphic? If so, provide an isomorphism, If not, explain why. Solution: Yes, Z(2)#Z(5) and Z(10) are isomorphic. To see this, note that they have the same numbers of each element. [Here's where I messed up; I miscalculated the order of the element (0,3) in Z(2)#Z(5) as 10 instead of 5.] Because they are isomorphic, a generator maps to a generator. So, P((1,1))=1, since (1,1) and 1 are generators of Z(2)#Z(5) and Z(10), respectively. Then, a possible isomorphism is P(n(1,1))=n.
   

Overall, I'm very pleased with how I did on this exam. I shouldn't have miscalculated the order of (0,3), but, even if I had decided that they were isomorphic, I'm not sure I could have figured out that isomorphism in the allotted time. Maybe I'm not giving myself enough credit. As for the other missed points... Well, the first was a stupid mistake and the second was a problem in my understanding of one-to-one proofs, and it has been rectified.
Ok, time to send a few emails, then I'll be back to write about my PHL paper.

Post-Exam Re-Hash

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.

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:

1. Z(n) under regular addition
   
2. U(n) under regular multiplication
3. Aut(Z(n)) under function composition

Properties:

1. Iff G is Abelian, then P(G) is Abelian.
   
2. 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:

1. In Z(n) with element k, if gcd(n,k)=1 (n,k relatively prime), then k is a generator of Z(n).
   
2. If |G| is prime, then G is cyclic.
   
3. Every subgroup of a cyclic group is cyclic.
   
4. 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).
   
5. S(n) is cyclic.
   

Properties:

1. G is cyclic iff P(G) is cyclic.
2. 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:

1. Any subgroup H of an Abelian group G is normal to G.
   
2. The centralizer Z(G) is always normal to G.
   
3. A(n) is always normal to S(n).
   
4. R(n) is always normal to D(n).
   
5. 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:

1. The identity always maps to the identity.
   
2. G is cyclic iff P(G) is cyclic.
   
3. G is Abelian IFF P(G) is Abelian.
   
4. G and P(G) have the same number of elements of each order, if G is finite.
   
5. G and P(G) have the same order.
   
6. |a|=|P(a)|; that is, P preserves the order of an element.
   
7. For a,b in G, a,b commute iff P(a),P(b) commute.
8. For all a in G, P(a^n)=(P(a))^n.
9. If K is a subgroup of G, then P(K) is a subgroup of P(G).
   
10. Aut(Z(n)) is isomorphic to U(n).
    

Cosets: Let H be a subset of a group G with element a; then, aH={ah| h is in H}. If H is a subgroup of G, then aH is a left coset of G. Similar definitions exists for Ha and aH(a^-1).
Properties:

1. a is in aH.
2. aH=H iff a is in H.
   
3. aH=bH iff a is in bH.
   
4. aH=bH or aH&bH={0}.
   
5. aH=bH iff (a^-1)b is in H.
   
6. |aH|=|bH|.
   
7. aH=Ha iff H=aH(a^-1).
   
8. aH is a subgroup of G iff a is in H.
   
9. The number of distinct cosets (left, right, OR whatever) of H in G is |G|/|H| (Lagrange's Theorem).
   

Lagrange's Theorem and Corollaries:
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:

1. The order of an external direct product is the product of the orders of the individual groups.
   
2. The order of an element of an external direct product is the least common multiple of the orders of the components of the element.
   
3. G#H is cyclic iff |G| and |H| are relatively prime.
   
4. 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)

This last property is still a little mysterious to me, but I'm coming around.
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.

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.

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.

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.

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.

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?

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.