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.