Tuesday, November 23, 2010

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.

Tuesday, July 27, 2010

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.

Sunday, July 11, 2010

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.

Wednesday, May 12, 2010

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.

Monday, May 3, 2010

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.

Thursday, April 22, 2010

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.

Wednesday, April 21, 2010

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
Proofs to come soon.
Bubye.