In today's blog, I will review some basic lemmas regarding normal subgroups and quotient groups. The concept of normal subgroups was first offered by Evariste Galois. The important idea behind normal subgroups is that when a subgroup is normal, then the set of left or right cosets is itself a group. This is what will be presented in today's blog.
I will use this result as part of Kummer's proof on Fermat's Last Theorem for regular primes.
Definition 1: Normal Subgroup
A subgroup H of a group G is called a normal subgroup of G if for all a ∈ G and all h ∈ H, there exists an element h' ∈ H such that ah = (h')a
NOTE: It is quite possible that h'=h but this is not necessary. From this perspective, normal subgroup is not necessarily an abelian group, that is, it may not be commutative (see here for definition of an abelian group).
NOTE #2: For all purposes definition 1 is the same as aH = Ha. Here's why:
For any x ∈ aH, there exists h ∈ H such that x = ah. From the definition, there exists h' such that h' ∈ H and ah=h'a which means that x=h'a which means that x ∈ Ha.
Lemma 1: A subgroup H is normal in G if and only if g-1Hg ⊆ H for all g in G.
Proof:
(1) Assume H is a normal subgroup of G.
(2) Then, for any g ∈ G, h ∈ H, there exists h' ∈ H such that hg = gh' [See Definition of a Normal Subgroup above]
(3) Thus, g-1hg = h' [Since g-1gh' = eh' = h']
NOTE: We know that g-1 ∈ G and that g-1g = e (Inverse Property of Groups, see here). We know that eh' = h' (Identity Property of Groups, see here)
(4) Therefore for all g,h, we know that g-1hg ∈ H [Since g-1hg = h' and h' ∈ H]
(5) So that g-1Hg ⊆ H [That is, for all x ∈ g-1Hg → x ∈ H]
(6) Assume that g-1Hg ⊆ H for all g ∈ G
(7) This means that Hg ⊆ gH [Since from #6, we have gg-1Hg ⊆ gH and gg-1Hg = eHg = Hg]
(8) Since g-1 ∈ G, our assumption in #6 gives us:
(g-1)-1H(g-1) = gHg-1 ⊆ H
But this also means that:
gH ⊆ Hg since gHg-1g = gH ⊆ Hg
(9) So combining step #7 and step #8 gives us: Hg = gH
NOTE: Hg = gH shows that for all h ∈ H, g ∈ G, there exists h' ∈ H such that: hg = gh'.
QED
Lemma 2: A subgroup of an abelian group is normal
Proof:
(1) Let G be an abelian group. [See here for definition of an abelian group]
(2) Let H be a subgroup of G. [See here for definition of a subgroup]
(3) g ∈ G, h ∈ H → gh = hg. [from the definition of abelian groups]
(4) Multiplying both sides by the inverse of g (see here) gives us:
g-1gh = g-1hg
This implies that:
h = g-1hg
(5) Since h ∈ H, this gives us:
h ∈ H, g ∈ G → g-1hg ∈ H.
(6) Using Lemma 1 above, we can now conclude that H is a normal subgroup of G.
QED
Definition 2: Quotient Group
Let G be a group and H a normal subgroup of G. The Quotient Group is defined as as the coset aH such that {aH : a ∈ G} and is represented as G/H
Example 1: Z/2Z under addition = { 0+2Z, 1+2Z}
Let Z be the set of integers.
We can see that the left coset 2z = the set of even integers = { ..., -2, 0, 2 ... }
Z/2Z = {a(2Z) : a ∈ Z} = two distinct cosets {0 + 2z, 1 + 2z}
Lemma 3: if aH = a'H, then there exists h ∈ H such that a' = ah
Proof:
(1) a' ∈ a'H [H is a group → e ∈ H → a'e ∈ a'H]
(2) a' ∈ aH [since aH = a'H]
(3) From #2, there exists h ∈ H such that a' = ah
QED
Lemma 4: aH = H if and only if a ∈ H
Proof:
(1) Assume aH = H
(2) a = ae ∈ aH
(3) So combining #1 and #2, a ∈ H
(4) Assume a ∈ H
(5) x ∈ aH → x=ah with h ∈ H
(6) But if a ∈ H and h ∈ H, then ah ∈ H (by property of closure, see here)
(7) From #5 and #6, we conclude that aH ⊆ H
(8) Let h ∈ H
(9) From #4 and #8, ah ∈ H and a-1h ∈ H
(10) So, h = eh = (aa-1)h = a(a-1h)
(11) So, from #10, h ∈ aH and therefore H ⊆ aH
(12) Combining #7 (aH ⊆ H) and #11 (H ⊆ aH) gives us: aH = H
QED
Lemma 5: A Quotient Group is itself a group under the operation (aH)(bH) = abH.
Proof:
(1) Let H be a normal subgroup of G.
(2) Let G/H be the quotient group { aH : a ∈ G }
(3) First, we need to prove that (aH)(bH) = abH is a well-defined operation. In other words, we need to show that aH=a'H, bH = b'H → (a'b')H = (ab)H
NOTE: A function maps each of its input to exactly one output (see here for Wikipedia's review of a mathematical function) So, we need to prove if the inputs are equal, the outputs are equal.
(3) Assume that aH = a'H and bH = b'H with a,a',b,b' ∈ G
(4) Then a' = ah1 and b' = bh2 for some h1,h2 in H [By Lemma 3 above]
(5) Then a'b'H = (ah1)(bh2)H
(6) Using Lemma 4 above, since h1, h2 ∈ H we know that:
h1H = H
h2H = H
So that we have:
(ah1)(bh2)H = (ah1)bH
(7) Since H is a normal subgroup of G, we know that b ∈ G → bH=Hb [See definition 1 above, note 2]
This gives us:
(ah1)bH = (ah1)Hb
Using Lemma 4 above gives us
(ah1)Hb = aHb = abH
(8) Closure: x ∈ G/H, y ∈ G/H → xy ∈ G/H since:
x ∈ G/H → there exists a ∈ G such that x = aH.
y ∈ G/H → there exists b ∈ G such that y = bH
xy = (aH)(bH) = (ab)H [Definition of operation]
xy ∈ G/H since a ∈ G, b ∈ G → ab ∈ G so (ab)H ∈ G/H.
(9) Identity: H
e ∈ G → eH ∈ G/H
e ∈ H so eH = H [From Lemma 4 above]
Further, we see that:
(aH)(H) = (aH)(eH) = (ae)H = aH
(14) Inverse: a-1H
x ∈ G/H → x = aH such that a ∈ G
a ∈ G → a-1 ∈ G
So a-1H ∈ G/H
Further,
(aH)(a-1H) = (aa-1)H = eH = H
(15) Associativity:
(aHbH)cH = (ab)HcH = (ab)cH [From the definition of the operation for this group]
= a(bc)H = [(ab)c = a(bc) since a,b,c ∈ G and G is a group so is characterized by associativity]
= aH(bc)H = [From the definition of operation for this group: aH(bc)H = a(bc)H]
= aH(bHcH) [From the defintion of operation for this group: bHcH = (bc)H]
QED
Tuesday, June 06, 2006
Friday, June 02, 2006
Group Theory: Lagrange's Theorem
In today's blog, I review the proof for Lagrange's Theorem. The theorem is named after Joseph-Louis Lagrange who first stated it. The first complete proof came 30 years later.
In today's blog, I also use the concept of order, subgroup, and coset. The concept of the coset was first proposed by Evariste Galois. The term "coset" was coined by G. A. Miller in 1910.
The content of today's blog is taken from Joseph A. Gallian's Contemporary Abstract Algebra.
Definition 1: Order of a Group
The number of elements of a group.
NOTE: If you need to review the definition of the group, see here.
Definition 2: Subgroup
If H is a subset of a group G and H is a group itself under the operation of G, then H is a subgroup of G.
Definition 3: Coset of H in G
Let G be a group and H a subgroup of G. For any a ∈ G, the set aH { ah : h ∈ H } is called the left coset of H in G containing a. The set Ha { ha : h ∈ H } is called the right coset of H in G containing a.
NOTE: An important idea behind the coset is that it is a distinct partition of elements (see Lemma 2 below). From the property of closure, we know that if two values are elements of a group, then their product (by this, I mean the result of the group operation) is also an element of the group.
From this, we know that the set of cosets can be divided up as follows: a1H, a2H, ..., arH where r is a positive integer and where for each coset i ≠ j → aiH ∩ ajH = ∅ [See Lagrange's Theorem below to see how this partitioning can be used]
Example 1 Coset: Z9
Let G = Z9 = { 0, 1, 2, 3, 4, 5, 6, 7, 8 } with operation '+'
NOTE: Z9 is the set of integers modulo 9 [See here for a review of modular arithmetic]
Let H = { 0, 3, 6 } with operation '+'
We can see that H is a subgroup of G
The left coset in this case is a+H (note it would aH is the operation were '*')
Here are the cosets:
0 + H = { 0, 3, 6 } = 3 + H = 6 + H
1 + H = { 1, 4, 7 } = 4 + H = 7 + H
2 + H = {2, 5, 8} = 5 + H = 8 + H
We can see that all cosets are either equal or distinct. I present a proof of this in Lemma 2 below.
Example 2: Even integers
Let Z be the set of integers
Then 2Z is a left coset which includes { ..., 0, 2, 4 , 6, ... }
Lemma 1: aH = H if and only if a ∈ H
Proof:
(1) Assume aH = H
(2) Then, a = ae ∈ aH = H
(3) Assume a ∈ H
(4) aH ⊆ H since h ∈ H → ah ∈ H [By property of closure, see here if needed]
(5) H ⊆ aH since:
(a) Let h be any element of H.
(b) a-1 ∈ H since a ∈ H [By the inverse property, see here if needed]
(c) a-1H ∈ H [By property of closure, see here if needed]
(d) So h = eh = (aa-1)h = a(a-1h) [By identity property, inverse property, and associative property, see here if needed]
(e) But a(a-1h) ∈ aH so that from (#5d), h ∈ aH.
(6) So H = aH since H ⊆ aH and aH ⊆ H.
QED
Lemma 2: if aH, bH are two cosets, then aH = bH or aH ∩ bH = ∅
Proof:
(1) Assume that aH ∩ bH ≠ ∅
(2) Let x ∈ aH ∩ bH since aH ∩ bH ≠ ∅
(3) Then there exists h1, h2 such that:
x = ah1
x= bh2
Since x is found in both aH and bH by assumption.
(4) Thus, a = xh1-1 = (bh2)h1-1
(5) From this, aH = [(bh2)h1-1]H = b(h2h1-1H) = bH [By Lemma 1 above]
QED
Theorem: Lagrange's Theorem
If G is a finite group and H is a subgroup of G, then the order of H divides the order of G.
Proof:
(1) Let a1H, a2H, ..., arH denote the distinct left cosets of H in G. [See Definition 3 above for details on left cosets of H in G.]
NOTE: If two cosets are equal then we only count them once.
(2) For each a ∈ G, we have aH = aiH for some i by our construction in step #1.
(3) a ∈ aH since:
a = ae and ae ∈ aH since H is a subgroup. [See Definition 2 above for details on subgroups]
(4) Thus, each member of G belongs to one of the cosets aiH [from step #2 and step #3.]
(5) G = a1H ∪ a2H ∪ ... ∪ arH [This follows directly from step #4]
(6) From Lemma 2 above, we know aiH = ajH or aiH ∩ ajH = ∅ and since each ai is distinct, we get:
order(G) = order(a1H) + order(a2H) + ... + order(arH)
(7) Since order(aiH) = order(H) for each i (by the definition of cosets, see definition 3 above, we have:
order (G) = r*order(H)
QED
In today's blog, I also use the concept of order, subgroup, and coset. The concept of the coset was first proposed by Evariste Galois. The term "coset" was coined by G. A. Miller in 1910.
The content of today's blog is taken from Joseph A. Gallian's Contemporary Abstract Algebra.
Definition 1: Order of a Group
The number of elements of a group.
NOTE: If you need to review the definition of the group, see here.
Definition 2: Subgroup
If H is a subset of a group G and H is a group itself under the operation of G, then H is a subgroup of G.
Definition 3: Coset of H in G
Let G be a group and H a subgroup of G. For any a ∈ G, the set aH { ah : h ∈ H } is called the left coset of H in G containing a. The set Ha { ha : h ∈ H } is called the right coset of H in G containing a.
NOTE: An important idea behind the coset is that it is a distinct partition of elements (see Lemma 2 below). From the property of closure, we know that if two values are elements of a group, then their product (by this, I mean the result of the group operation) is also an element of the group.
From this, we know that the set of cosets can be divided up as follows: a1H, a2H, ..., arH where r is a positive integer and where for each coset i ≠ j → aiH ∩ ajH = ∅ [See Lagrange's Theorem below to see how this partitioning can be used]
Example 1 Coset: Z9
Let G = Z9 = { 0, 1, 2, 3, 4, 5, 6, 7, 8 } with operation '+'
NOTE: Z9 is the set of integers modulo 9 [See here for a review of modular arithmetic]
Let H = { 0, 3, 6 } with operation '+'
We can see that H is a subgroup of G
The left coset in this case is a+H (note it would aH is the operation were '*')
Here are the cosets:
0 + H = { 0, 3, 6 } = 3 + H = 6 + H
1 + H = { 1, 4, 7 } = 4 + H = 7 + H
2 + H = {2, 5, 8} = 5 + H = 8 + H
We can see that all cosets are either equal or distinct. I present a proof of this in Lemma 2 below.
Example 2: Even integers
Let Z be the set of integers
Then 2Z is a left coset which includes { ..., 0, 2, 4 , 6, ... }
Lemma 1: aH = H if and only if a ∈ H
Proof:
(1) Assume aH = H
(2) Then, a = ae ∈ aH = H
(3) Assume a ∈ H
(4) aH ⊆ H since h ∈ H → ah ∈ H [By property of closure, see here if needed]
(5) H ⊆ aH since:
(a) Let h be any element of H.
(b) a-1 ∈ H since a ∈ H [By the inverse property, see here if needed]
(c) a-1H ∈ H [By property of closure, see here if needed]
(d) So h = eh = (aa-1)h = a(a-1h) [By identity property, inverse property, and associative property, see here if needed]
(e) But a(a-1h) ∈ aH so that from (#5d), h ∈ aH.
(6) So H = aH since H ⊆ aH and aH ⊆ H.
QED
Lemma 2: if aH, bH are two cosets, then aH = bH or aH ∩ bH = ∅
Proof:
(1) Assume that aH ∩ bH ≠ ∅
(2) Let x ∈ aH ∩ bH since aH ∩ bH ≠ ∅
(3) Then there exists h1, h2 such that:
x = ah1
x= bh2
Since x is found in both aH and bH by assumption.
(4) Thus, a = xh1-1 = (bh2)h1-1
(5) From this, aH = [(bh2)h1-1]H = b(h2h1-1H) = bH [By Lemma 1 above]
QED
Theorem: Lagrange's Theorem
If G is a finite group and H is a subgroup of G, then the order of H divides the order of G.
Proof:
(1) Let a1H, a2H, ..., arH denote the distinct left cosets of H in G. [See Definition 3 above for details on left cosets of H in G.]
NOTE: If two cosets are equal then we only count them once.
(2) For each a ∈ G, we have aH = aiH for some i by our construction in step #1.
(3) a ∈ aH since:
a = ae and ae ∈ aH since H is a subgroup. [See Definition 2 above for details on subgroups]
(4) Thus, each member of G belongs to one of the cosets aiH [from step #2 and step #3.]
(5) G = a1H ∪ a2H ∪ ... ∪ arH [This follows directly from step #4]
(6) From Lemma 2 above, we know aiH = ajH or aiH ∩ ajH = ∅ and since each ai is distinct, we get:
order(G) = order(a1H) + order(a2H) + ... + order(arH)
(7) Since order(aiH) = order(H) for each i (by the definition of cosets, see definition 3 above, we have:
order (G) = r*order(H)
QED
Tuesday, May 23, 2006
Modular Arithmetic and Unique Mappings
Today, I talk about a result using modular arithmetic that I use in the properties of cyclotomic integers.
Lemma 1: For a given odd prime λ, each value i, 2*i, 3*i, ... (λ-1)*i maps to a distinct value of 1,2,3,...,(λ-1) modulo λ
Proof:
(1) Let a,b be any integer between 1 and λ-1 where a ≠ b
(2) Let i be any integer between 1 and λ - 1.
(3) Assume that a*i ≡ b*i (mod λ) where a,b are distinct.
(4) So λ divides a*i - b*i and there exists c such that λc = ai-bi = i(a-b)
(5) By Euclid's Lemma, λ divides either i or λ divides a-b.
(6) We know that λ doesn't divide i since i is between 1 and λ -1.
(7) So λ divides a-b
(8) But this means that a-b=0 since a,b are between 1 and λ - 1 and if a,b are distinct then abs(a-b) is between 1 and λ-2 which is not divisible by λ
(9) So we have a contradiction and we reject our assumption in (3).
QED
Lemma 1: For a given odd prime λ, each value i, 2*i, 3*i, ... (λ-1)*i maps to a distinct value of 1,2,3,...,(λ-1) modulo λ
Proof:
(1) Let a,b be any integer between 1 and λ-1 where a ≠ b
(2) Let i be any integer between 1 and λ - 1.
(3) Assume that a*i ≡ b*i (mod λ) where a,b are distinct.
(4) So λ divides a*i - b*i and there exists c such that λc = ai-bi = i(a-b)
(5) By Euclid's Lemma, λ divides either i or λ divides a-b.
(6) We know that λ doesn't divide i since i is between 1 and λ -1.
(7) So λ divides a-b
(8) But this means that a-b=0 since a,b are between 1 and λ - 1 and if a,b are distinct then abs(a-b) is between 1 and λ-2 which is not divisible by λ
(9) So we have a contradiction and we reject our assumption in (3).
QED
Monday, May 22, 2006
modular arithmetic and functions
Today, I want to go over a single lemma which I use in my analysis of cyclotomic integers.
Lemma 1:
if α,β are integers such α ≡ β (mod γ) and f(x) = xn + a1xn-1 + ... + an
then f(α) ≡ f(β) (mod γ)
Proof:
(1) f(α) - f(β) = [(α)n - (β)n] + [a1(α)n-1 - a1(β)n-1] + ... + [an-1α - an-1β] + [an - an]
(2) Now, since α ≡ β (mod γ), we also have:
(α)2 ≡ (β)2 (mod γ)
all the way up to:
(α)n-1 ≡ (β)n-1 (mod γ)
and:
(α)n ≡ (β)n (mod γ)
(3) So this means that γ divides all parts of
[(α)n - (β)n] + [a1(αn-1 - βn-1)] + ... + [an-1(α - β)]
(4) Which means that γ divides f(α) - f(β)
QED
Lemma 1:
if α,β are integers such α ≡ β (mod γ) and f(x) = xn + a1xn-1 + ... + an
then f(α) ≡ f(β) (mod γ)
Proof:
(1) f(α) - f(β) = [(α)n - (β)n] + [a1(α)n-1 - a1(β)n-1] + ... + [an-1α - an-1β] + [an - an]
(2) Now, since α ≡ β (mod γ), we also have:
(α)2 ≡ (β)2 (mod γ)
all the way up to:
(α)n-1 ≡ (β)n-1 (mod γ)
and:
(α)n ≡ (β)n (mod γ)
(3) So this means that γ divides all parts of
[(α)n - (β)n] + [a1(αn-1 - βn-1)] + ... + [an-1(α - β)]
(4) Which means that γ divides f(α) - f(β)
QED
Saturday, May 20, 2006
Fields and Rings
In today's blog, I will talk about the assumptions behind the idea of a field. I use the concept of a field in the proof for the Division Algorithm for Polynomials.
Definition 1: Ring
A ring R is a nonempty set with two binary operations: addition (a + b) and multiplication (ab).
It has the following properties:
1. Commutative Rule for Addition: a + b = b + a
2. Associative Rule for Addition: (a + b) + c = a + (b + c)
3. Additive Identity: there exists a value 0 ∈ R such that a + 0 = a for all a ∈ R
4. Additive Inverse: for all elements a ∈ R, there exists a value -a ∈ R such that a + -a = 0.
5. Associative Rule for Multiplication: a(bc) = (ab)c
6. Distributive Rule: a(b + c) = ab + ac and (b + c)a = ba + ca
Definition 2: Commutative Ring
A ring that has the following additional property:
7. Commutative Rule for Multiplication: ab = ba
Definition 3: Field
A field is a commutative ring R with unity in which every nonzero element is a unit.
It has all the properties of a commutative ring plus:
8. Multiplicative Identity (unity): there exists a value 1 ∈ R such that such that a * 1 = a for all a ∈ R
9. Multiplicative Inverse (every nonzero element is a unit): for all nonzero elements a ∈ R, there exists an inverse a-1 ∈ R such that a*a-1 = 1.
Examples:
1. The set of integers Z is a commutative ring with unity 1. [See here for more information on the integers]
2. The set Zn is a commutative ring with unity 1. [See here for more information on modular arithmetic]
3. The set of 2x2 matrices with integer entries is a noncommutative ring with unity. [See here for more information on 2x2 matrices]
4. If p is prime, then the set Zp is a field. [See here for more information on modular arithmetic]
5. The set of rational numbers Q is a field.
6. The set of real numbers R is a field.
7. The set of complex numbers is a field. [See here for more information on complex numbers]
8. The set of Gaussian Integers is a ring. [See here for more information on Gaussian Integers]
9. The set of Eisenstein Integers is a ring. [See here for more information on Eisenstein Integers]
References
Definition 1: Ring
A ring R is a nonempty set with two binary operations: addition (a + b) and multiplication (ab).
It has the following properties:
1. Commutative Rule for Addition: a + b = b + a
2. Associative Rule for Addition: (a + b) + c = a + (b + c)
3. Additive Identity: there exists a value 0 ∈ R such that a + 0 = a for all a ∈ R
4. Additive Inverse: for all elements a ∈ R, there exists a value -a ∈ R such that a + -a = 0.
5. Associative Rule for Multiplication: a(bc) = (ab)c
6. Distributive Rule: a(b + c) = ab + ac and (b + c)a = ba + ca
Definition 2: Commutative Ring
A ring that has the following additional property:
7. Commutative Rule for Multiplication: ab = ba
Definition 3: Field
A field is a commutative ring R with unity in which every nonzero element is a unit.
It has all the properties of a commutative ring plus:
8. Multiplicative Identity (unity): there exists a value 1 ∈ R such that such that a * 1 = a for all a ∈ R
9. Multiplicative Inverse (every nonzero element is a unit): for all nonzero elements a ∈ R, there exists an inverse a-1 ∈ R such that a*a-1 = 1.
Examples:
1. The set of integers Z is a commutative ring with unity 1. [See here for more information on the integers]
2. The set Zn is a commutative ring with unity 1. [See here for more information on modular arithmetic]
3. The set of 2x2 matrices with integer entries is a noncommutative ring with unity. [See here for more information on 2x2 matrices]
4. If p is prime, then the set Zp is a field. [See here for more information on modular arithmetic]
5. The set of rational numbers Q is a field.
6. The set of real numbers R is a field.
7. The set of complex numbers is a field. [See here for more information on complex numbers]
8. The set of Gaussian Integers is a ring. [See here for more information on Gaussian Integers]
9. The set of Eisenstein Integers is a ring. [See here for more information on Eisenstein Integers]
References
- Joseph A. Gallian, Contemporary Abstract Algebra
- Rings, Wikipedia
Division Algorithm for Polynomials
In today's blog, I will go over a result that I use in the proof for the Fundamental Theorem of Algebra.
Today's proof is taken from Joseph A. Gallian's Contemporary Abstract Algebra.
Theorem: Division Algorithm for Polynomials
Let F be a field, f(x), g(x) ∈ F[x] with g(x) ≠ 0.
Then there exists unique polynomials q(x), r(x) in F[x] such that f(x) = g(x)q(x) + r(x) and r(x)=0 or deg r(x) is less than deg g(x).
Proof:
(1) Let f(x) = g(x)q(x) + r(x) with g(x) ≠ 0
(2) If f(x) = 0 or deg f(x) is less than g(x), then q(x)=0, r(x)=f(x)
(3) So, we can assume that f(x) ≠ 0 and deg f(x) ≥ deg g(x)
(4) Let f(x) = anxn + ... + a0
(5) Let g(x) = bmxm + ... + b0
(6) Let f1(x) = f(x) - anbm-1xn-mg(x)
(7) We note that deg f1(x) is less than deg f(x) since:
f(x) - anbm-1xn-mg(x) =
= anxn + ... + a0 - anbm-1xn-m(bmxm + ... + b0) =
= ann - anxn + an-1xn-1 + ... + a0 - anbm-1bm-1xn-1 - ... - anbm-1b0xn-m =
= an-1xn-1 + ... + a0 - anbm-1bm-1xn-1 - ... - anbm-1b0xn-m
So that f1(x) has a degree of n-1 while f(x) has a degree of n.
(8) Now, we are ready to prove this theorem by induction.
(9) The assumption is true for deg f(x) = 0
deg f(x) is 0 → f(x)=C where C is a constant.
If deg g(x) is 0, then g(x) = D where D is a nonzero constant and q(x) = C/D and r(x)=0.
If deg g(x) is greater than 0, then q(x)=0 and r(x)=C.
(10) We can now assume that the assumption holds for all polynomials up to degree n-1.
(9) We see that:
f(x) = anbm-1xn-mg(x) + f1(x)
where the degree of f1(x) is n-1 [See step #7]
(10) But by the induction hypothesis (step #10), we can assume that there exists q1(x) and r1(x) where r1(x) has a degree lower than g(x).
(11) Therefore, we have:
anbm-1xn-mg(x) + f1(x) = anbm-1xn-mg(x) + q1(x)g(x) + r1(x) =
= [anbm-1xn-m + q1(x)]g(x) + r1(x)
(12) Which proves that degree r(x) is less than degree g(x) by principle of induction.
(13) Now, we still need to prove uniqueness of q(x),r(x)
(14) Suppose that:
f(x) = g(x)q(x) + r(x) = g(x)q'(x) + r'(x) where r(x),r'(x)=0 or deg r(x),r'(x) is less than deg g(x)
(15) Now, if we substract both equations, we get:
0 = g(x)[q(x) - q'(x)] + [r(x) - r'(x)]
which is the same as:
r'(x) - r(x) = g(x)[q(x) - q'(x)]
(16) Now since r'(x) and r(x) have degree less than g(x), the only way that this can be true is if r'(x) - r(x) = 0
(17) But then r'(x) = r(x) and q(x) = q'(x)
QED
References
Today's proof is taken from Joseph A. Gallian's Contemporary Abstract Algebra.
Theorem: Division Algorithm for Polynomials
Let F be a field, f(x), g(x) ∈ F[x] with g(x) ≠ 0.
Then there exists unique polynomials q(x), r(x) in F[x] such that f(x) = g(x)q(x) + r(x) and r(x)=0 or deg r(x) is less than deg g(x).
Proof:
(1) Let f(x) = g(x)q(x) + r(x) with g(x) ≠ 0
(2) If f(x) = 0 or deg f(x) is less than g(x), then q(x)=0, r(x)=f(x)
(3) So, we can assume that f(x) ≠ 0 and deg f(x) ≥ deg g(x)
(4) Let f(x) = anxn + ... + a0
(5) Let g(x) = bmxm + ... + b0
(6) Let f1(x) = f(x) - anbm-1xn-mg(x)
(7) We note that deg f1(x) is less than deg f(x) since:
f(x) - anbm-1xn-mg(x) =
= anxn + ... + a0 - anbm-1xn-m(bmxm + ... + b0) =
= ann - anxn + an-1xn-1 + ... + a0 - anbm-1bm-1xn-1 - ... - anbm-1b0xn-m =
= an-1xn-1 + ... + a0 - anbm-1bm-1xn-1 - ... - anbm-1b0xn-m
So that f1(x) has a degree of n-1 while f(x) has a degree of n.
(8) Now, we are ready to prove this theorem by induction.
(9) The assumption is true for deg f(x) = 0
deg f(x) is 0 → f(x)=C where C is a constant.
If deg g(x) is 0, then g(x) = D where D is a nonzero constant and q(x) = C/D and r(x)=0.
If deg g(x) is greater than 0, then q(x)=0 and r(x)=C.
(10) We can now assume that the assumption holds for all polynomials up to degree n-1.
(9) We see that:
f(x) = anbm-1xn-mg(x) + f1(x)
where the degree of f1(x) is n-1 [See step #7]
(10) But by the induction hypothesis (step #10), we can assume that there exists q1(x) and r1(x) where r1(x) has a degree lower than g(x).
(11) Therefore, we have:
anbm-1xn-mg(x) + f1(x) = anbm-1xn-mg(x) + q1(x)g(x) + r1(x) =
= [anbm-1xn-m + q1(x)]g(x) + r1(x)
(12) Which proves that degree r(x) is less than degree g(x) by principle of induction.
(13) Now, we still need to prove uniqueness of q(x),r(x)
(14) Suppose that:
f(x) = g(x)q(x) + r(x) = g(x)q'(x) + r'(x) where r(x),r'(x)=0 or deg r(x),r'(x) is less than deg g(x)
(15) Now, if we substract both equations, we get:
0 = g(x)[q(x) - q'(x)] + [r(x) - r'(x)]
which is the same as:
r'(x) - r(x) = g(x)[q(x) - q'(x)]
(16) Now since r'(x) and r(x) have degree less than g(x), the only way that this can be true is if r'(x) - r(x) = 0
(17) But then r'(x) = r(x) and q(x) = q'(x)
QED
References
- Joseph A. Gallian, Contemporary Abstract Algebra.
Properties of cos θ + i sin θ
In today's blog, I will go over some basic trigonometric properties that I use in my proof for the Fundamental Theorem of Algebra.
Lemma 1: [(cos α + i sin α) ]a = cos (a*α) + i sin (a*α)
Proof:
(1) From Euler's Formula, we know that:
eiα = cos α + i sin (α)
(2) So, we see that:
(eiα)a = ei*a*α
(3) Finally,
ei(a*α) = cos (a*α) + i sin (a*α)
QED
Lemma 2: (cos α + i sin α)(cos β + i sin β) = cos(α + β) + i sin(α + β)
Proof:
(1) Again, using Euler's Formula, we have:
eiα = cos α + i sin α
eiβ = cos β + i sin β
(2) So multiplying these two values together gives us [see here if a review of exponents are needed]:
(eiα)(eiβ) = eiα + iβ = ei(α + β)
(3) Finally,
ei(α + β) = cos(α + β) + i sin(α + β)
QED
Lemma 1: [(cos α + i sin α) ]a = cos (a*α) + i sin (a*α)
Proof:
(1) From Euler's Formula, we know that:
eiα = cos α + i sin (α)
(2) So, we see that:
(eiα)a = ei*a*α
(3) Finally,
ei(a*α) = cos (a*α) + i sin (a*α)
QED
Lemma 2: (cos α + i sin α)(cos β + i sin β) = cos(α + β) + i sin(α + β)
Proof:
(1) Again, using Euler's Formula, we have:
eiα = cos α + i sin α
eiβ = cos β + i sin β
(2) So multiplying these two values together gives us [see here if a review of exponents are needed]:
(eiα)(eiβ) = eiα + iβ = ei(α + β)
(3) Finally,
ei(α + β) = cos(α + β) + i sin(α + β)
QED
Argand Diagram
An Argand Diagram is a way of visualizing complex numbers. It involves graphing a complex number to the Cartesian coordinates.
There are two ways to represent a complex number:
x + iy
r (cos φ + i sin φ)
Both of these ways are equivalent since:
Here is the Argand Diagram:
One important point to remember is that in the r (cos φ + i sin φ) form, all values can be positive since r is an absolute magnitude and φ is a value between 0 and 2π using radians (or in degrees, between 0 and 360).
References
There are two ways to represent a complex number:
x + iy
r (cos φ + i sin φ)
Both of these ways are equivalent since:
Here is the Argand Diagram:
One important point to remember is that in the r (cos φ + i sin φ) form, all values can be positive since r is an absolute magnitude and φ is a value between 0 and 2π using radians (or in degrees, between 0 and 360).
References
- Complex Number, Wikipedia
Sunday, May 07, 2006
Using Maclaurin Series to define exponents
It is easy to define exponents in terms of positive integers.
xn = x1 * x2 * ... * xn
It is also straight forward to define exponents for 0, negative integers, and rational numbers. I wrote more about this in a previous blog.
But what about the complex numbers? What does it mean to have a value such as 5i. In fact, a very well known equation is Euler's Identity (see here):
eiπ + 1 = 0
To handle this, we need a new definition for exponents that is consistent with their use for rational numbers but which can also handle the complex domain.
One way is to use the Maclaurin Series. In a previous blog, I showed that the Maclaurin series is:
f(x) = f(0) + (x/1!)f'(0) + (x2/2!)f''(0) + (x3/3!)f'''(0) + ... + (xn/n!)fn(0)
Now, if we define an exponent as a function so that ex becomes:
f(x) = ex
Applying derivatives, we get:
f(0) = e0 = 1
And likewise, all fn(0) = 1
Substituting these results into the above equation gives us:
ex = 1 + (x/1!) + (x2/2!) + ... + xn/n!
Now ay = ey*ln(a) since:
(a) eln(a) = a [See here for details on ln if needed]
(b) ln(ay) = y*ln(a) [See here for detalis on ln if needed]
So, we can use the equation for ex to define ay
ay = ey*ln(a) = 1 + (y*ln(a))/1! + (y*ln(a))2/2! + ... + (y*ln(a))n/n!
So for example,
13 = 1 + (3*ln(1))/1! + (3*ln(2))2/2! + ... + =
= 1 + (0)/1! + (0)/2! + ...
21 = 1 + (1*ln(2))/1! + (1*ln(2))2/2! + ... + =
1 + ln(2) + ln(2)*ln(2)/2 + ln(2)*ln(2)*ln(3)/6 + ...
= 1 + 0.693... + 0.240... + 0.0555... + ... = 2
Finally, let's ask the question about ai, which equals:
ai = 1 + (i*ln(a)) + (i*ln(a))2/2! + ... + (i*ln(a))n/n!
= 1 + i*ln(a) - [ln(a)]2/2 -i*[ln(a)]3/3! + [ln(a)]4/4! + ...
= (1 - [ln(a)]2/2 + [ln(a)4/4! + ...) + i(ln(a) - [ln(a)3/3! + ln(a)5/5! + ...)
xn = x1 * x2 * ... * xn
It is also straight forward to define exponents for 0, negative integers, and rational numbers. I wrote more about this in a previous blog.
But what about the complex numbers? What does it mean to have a value such as 5i. In fact, a very well known equation is Euler's Identity (see here):
eiπ + 1 = 0
To handle this, we need a new definition for exponents that is consistent with their use for rational numbers but which can also handle the complex domain.
One way is to use the Maclaurin Series. In a previous blog, I showed that the Maclaurin series is:
f(x) = f(0) + (x/1!)f'(0) + (x2/2!)f''(0) + (x3/3!)f'''(0) + ... + (xn/n!)fn(0)
Now, if we define an exponent as a function so that ex becomes:
f(x) = ex
Applying derivatives, we get:
f(0) = e0 = 1
And likewise, all fn(0) = 1
Substituting these results into the above equation gives us:
ex = 1 + (x/1!) + (x2/2!) + ... + xn/n!
Now ay = ey*ln(a) since:
(a) eln(a) = a [See here for details on ln if needed]
(b) ln(ay) = y*ln(a) [See here for detalis on ln if needed]
So, we can use the equation for ex to define ay
ay = ey*ln(a) = 1 + (y*ln(a))/1! + (y*ln(a))2/2! + ... + (y*ln(a))n/n!
So for example,
13 = 1 + (3*ln(1))/1! + (3*ln(2))2/2! + ... + =
= 1 + (0)/1! + (0)/2! + ...
21 = 1 + (1*ln(2))/1! + (1*ln(2))2/2! + ... + =
1 + ln(2) + ln(2)*ln(2)/2 + ln(2)*ln(2)*ln(3)/6 + ...
= 1 + 0.693... + 0.240... + 0.0555... + ... = 2
Finally, let's ask the question about ai, which equals:
ai = 1 + (i*ln(a)) + (i*ln(a))2/2! + ... + (i*ln(a))n/n!
= 1 + i*ln(a) - [ln(a)]2/2 -i*[ln(a)]3/3! + [ln(a)]4/4! + ...
= (1 - [ln(a)]2/2 + [ln(a)4/4! + ...) + i(ln(a) - [ln(a)3/3! + ln(a)5/5! + ...)
radians
The idea of radians is to define degrees in terms of pi. In a previous blog, I showed how Archimedes' proof for the area of a circle can be used to establish pi.
Definition Radian: There are 2Ï€ radians in a circle.
In other words 2Ï€ radians = 360 degrees.
A straight line has π radians and a right angle has π/2 radians.
This is useful because it enables trigonometric functions to be expressed in terms of taking π as a value.
Here are some examples:
sin (Ï€/2) = 1
sin (Ï€) = 0
sin(2Ï€) = 0
cos (Ï€/2) = 0
cos(Ï€) = -1
cos(2Ï€) = 1
Lemma 1: sin(nπ) = 0 where n is any integer
Proof:
(1) sin(0) = 0 and sin(Ï€)=0 [See Property 1, here]
(2) sin(x + &2pi;) = x [See Property 5, here]
(3) So, we can see that:
if n is even, then n = 2x and sin (nπ) = sin(x*2π) = sin(0 + x*2π) = sin(0) = 0
if n is odd, then n = 2x+1 and sin(nπ) = sin(x*2π + π) = sin(π) = 0
QED
Lemma 2: The area of a sector = (1/2)θr2
Proof:
(1) We know that the area of a circle = πr2 (see Corollary 2, here)
(2) An angle of a circle = (θ/2π) of a circle.
(3) So therefore, the area of a sector = (θ/2π)(πr2) = (1/2)θr2
QED
Definition Radian: There are 2Ï€ radians in a circle.
In other words 2Ï€ radians = 360 degrees.
A straight line has π radians and a right angle has π/2 radians.
This is useful because it enables trigonometric functions to be expressed in terms of taking π as a value.
Here are some examples:
sin (Ï€/2) = 1
sin (Ï€) = 0
sin(2Ï€) = 0
cos (Ï€/2) = 0
cos(Ï€) = -1
cos(2Ï€) = 1
Lemma 1: sin(nπ) = 0 where n is any integer
Proof:
(1) sin(0) = 0 and sin(Ï€)=0 [See Property 1, here]
(2) sin(x + &2pi;) = x [See Property 5, here]
(3) So, we can see that:
if n is even, then n = 2x and sin (nπ) = sin(x*2π) = sin(0 + x*2π) = sin(0) = 0
if n is odd, then n = 2x+1 and sin(nπ) = sin(x*2π + π) = sin(π) = 0
QED
Lemma 2: The area of a sector = (1/2)θr2
Proof:
(1) We know that the area of a circle = πr2 (see Corollary 2, here)
(2) An angle of a circle = (θ/2π) of a circle.
(3) So therefore, the area of a sector = (θ/2π)(πr2) = (1/2)θr2
QED
Friday, May 05, 2006
Euclid's Proof for the Pythagorean Theorem
In today's blog, I will go over Euclid's proof for the Pythagorean Theorem as presented in Euclid's elements. There is a very large number of different proofs for this result. The simplest involve tiles that show how squares of the two sides can be refitted to form a square on the hypotenuse. One proof was discovered by American president, James Garfield.
Theorem: In a right triangle, the hypotenuse squared is equal to the sum of the other sides squared.
Proof:
(1) Since BAC is a right angle, we can extend AC to make a square GFBA and we can extend AB to make a square ACKH. (See here for details on the construction)
(2) We can also build a square based on BC. (See here for details on the construction)
(3) Let AL be a line that is parallel to BD and CE. (See here for details on the construction)
(4) ∠ DBA ≅ ∠ FBC since ∠ FBA and ∠ DBC are right angles and we get this result if we add ∠ ABC to both.
(5) triangle DBA ≅ triangle FBC by Side-Angle-Side (see here) since:
(a) ∠ DBA ≅ ∠ FBC (#4)
(b) FB ≅ AB since they are sides of the same square.
(c) BC ≅ BD since they are sides of the same square.
(6) The parallelogram BL is double the triangle ABD since they have the same base (BD) and since they are in the same parallel. (see Corollary 3.1 here for details)
(7) Likewise, the parallelogram GFBA is double the triangle FBC for the same reason as step #6.
(8) From step #5, we can conclude that the parallelogram BL is congruent to the parallelogram GFBA.
(9) We can follow the same steps to show that parallelogram CL is congruent to parallelogram ACKH since:
(a) ∠ KCB ≅ ∠ ACE since ∠ BCE, ∠ ACK are right angles and we can add ∠ ACB to each.
(b) AC ≅ CK and BC ≅ CE since the sides of the same square are congruent.
(c) So that triangle KCB ≅ triangle ACE by Side-Angle-Side.
(d) parallelogram CL is double the area of triangle ACE
(e) parallelogram CA is double the aera of triangle KCB
(f) So therefore parallelogram CL ≅ parallelogram CA
(10) So that we have the square of BC is congruent to the square of AB added to the square of AC since:
(a) the square BDEC = parallelogram BL + parallelogram CL
(b) parallelogram BL ≅ square of AB
(c) parallelogram CL ≅ square of AC
QED
Corollary 1: In a right triangle, the hypotenuse is longest of the three sides of a triangle.
Proof:
(1) Assume that the hypotenuse h is equal or less than one side s1
(2) Then, h2 is less than s12 + s22
(3) But this contradicts the Pythagorean Theorem so we can reject our assumption.
QED
Corollary 2: sin2(θ) + cos2(θ) = 1.
Proof:
(1) From the main theorem, for any right triangle with base sides x and y and with hypotenuse z, we have:
x2 + y2 = z2
(2) If θ is the angle between z and x, then we have (see here):
sin θ = y/z
cos θ = x/z
So that:
sin2(θ) = y2/z2
cos2(θ) = x2/z2
(3) Now if we divide the equation in step #1, by z2 on both sides we get:
x2/z2 + y2/z2 = 1.
(4) Now inserting the values in step #2 gives us:
sin2(θ) + cos2(θ) = 1.
QED
Theorem: In a right triangle, the hypotenuse squared is equal to the sum of the other sides squared.
Proof:
(1) Since BAC is a right angle, we can extend AC to make a square GFBA and we can extend AB to make a square ACKH. (See here for details on the construction)
(2) We can also build a square based on BC. (See here for details on the construction)
(3) Let AL be a line that is parallel to BD and CE. (See here for details on the construction)
(4) ∠ DBA ≅ ∠ FBC since ∠ FBA and ∠ DBC are right angles and we get this result if we add ∠ ABC to both.
(5) triangle DBA ≅ triangle FBC by Side-Angle-Side (see here) since:
(a) ∠ DBA ≅ ∠ FBC (#4)
(b) FB ≅ AB since they are sides of the same square.
(c) BC ≅ BD since they are sides of the same square.
(6) The parallelogram BL is double the triangle ABD since they have the same base (BD) and since they are in the same parallel. (see Corollary 3.1 here for details)
(7) Likewise, the parallelogram GFBA is double the triangle FBC for the same reason as step #6.
(8) From step #5, we can conclude that the parallelogram BL is congruent to the parallelogram GFBA.
(9) We can follow the same steps to show that parallelogram CL is congruent to parallelogram ACKH since:
(a) ∠ KCB ≅ ∠ ACE since ∠ BCE, ∠ ACK are right angles and we can add ∠ ACB to each.
(b) AC ≅ CK and BC ≅ CE since the sides of the same square are congruent.
(c) So that triangle KCB ≅ triangle ACE by Side-Angle-Side.
(d) parallelogram CL is double the area of triangle ACE
(e) parallelogram CA is double the aera of triangle KCB
(f) So therefore parallelogram CL ≅ parallelogram CA
(10) So that we have the square of BC is congruent to the square of AB added to the square of AC since:
(a) the square BDEC = parallelogram BL + parallelogram CL
(b) parallelogram BL ≅ square of AB
(c) parallelogram CL ≅ square of AC
QED
Corollary 1: In a right triangle, the hypotenuse is longest of the three sides of a triangle.
Proof:
(1) Assume that the hypotenuse h is equal or less than one side s1
(2) Then, h2 is less than s12 + s22
(3) But this contradicts the Pythagorean Theorem so we can reject our assumption.
QED
Corollary 2: sin2(θ) + cos2(θ) = 1.
Proof:
(1) From the main theorem, for any right triangle with base sides x and y and with hypotenuse z, we have:
x2 + y2 = z2
(2) If θ is the angle between z and x, then we have (see here):
sin θ = y/z
cos θ = x/z
So that:
sin2(θ) = y2/z2
cos2(θ) = x2/z2
(3) Now if we divide the equation in step #1, by z2 on both sides we get:
x2/z2 + y2/z2 = 1.
(4) Now inserting the values in step #2 gives us:
sin2(θ) + cos2(θ) = 1.
QED
Tuesday, May 02, 2006
Archimedes and the area of a circle
In today's blog, I will go over Archimede's proof that the area of a circle is (1/2)rc. When this proof is combined with Euclid's proof (most likely from Eudoxus), it is possible to show that for all circles, the ratio of C/D is constant.
Postulate 1: For a given chord of a circle, the segment of the circumference is longer than the chord.
In the example above, BDC is longer than BC.
Postulate 2: For a given segment of the circumference, lines connected above it combined are longer.
In the example above, AG + GE is greater than the segment of the circumference AE.
Lemma 1: The area of a regular polygon is (1/2)h*Q where Q is the sum of the perimeter.
Proof:
(1) A regular polygon can be divided up into a sum of triangles.
(2) The area of each triangle is equal to (1/2)*(GH)*(DE) [See here for details if needed]
(3) So, the area of the polygon = (# of sides)*(1/2)*(GH)*(DE)
(4) Let Q = the sum of the bases (for example, for the hexagon above, Q = DE + EF + FA + AB + BC + CD)
(5) Then, the area of the polygon = (1/2)*(GH)*Q
QED
Theorem: The area of a circle is (1/2)circumference * radius
Proof:
(1) Let K = (1/2)*C*R where C = circumference and R = radius.
(2) Let A = the area of the circle.
(3) Assume that A is greater than K
(4) We can inscribe a polygon inside A that is greater than K and less than A. [See Lemma 2 and the Method of Exhaustion here for details]
(5) So, the area of the polygon = (1/2)*Q*h where h is the distance from the center to the base and where Q is the perimeter of the polygon. [See Lemma 1 above]
(6) But Q is less than C (see Postulate 1 above) and h is less than R.
(7) So we have Area Polygon = (1/2)Q*h which is less than (1/2)*C*R
(8) But this contradicts step #4 so we reject step #3.
(9) Now, let's assume that K is greater than A.
(10) We can circumscribe a polygon P around A such that P is greater than A but less than K. [See Lemma 3 and Method of Exhaustion here for details.]
(11) From Lemma 1 again, we know that the area of this polygon is (1/2)*Q*h where Q is the perimeter of the polygon and h is the height.
(12) In the case of the circumscribed polygon (see diagram for Postulate 2), h = R.
(13) Using Postulate 2 above, we see that Q is greater than C.
(14) But then the area of the polygon is greater than K since (1/2)*Q*R is greater than (1/2)*C*R
(15) But this contradicts step #10 so we reject our assumption at step #9.
(16) Now, we apply the Law of Trichomoty (see here) and we are done.
QED
Corollary 1: For all circles, the ratio of Circumference to Diameter is constant
Proof:
(1) We know from Euclid (see here) that for any two circles C1 and C2 that:
Area1/Area2 = (Diameter1)2/(Diameter2)2
(2) We know from Theorem 1 above that:
Area of circle = (1/2)*radius*circumference.
(3) Combining step #1 with step #2 and using R=(1/2)D gives us:
[(1/2)*(1/2)D1*C1]/[(1/2)*(1/2)D2*C2] = [D1]2/[D2]2
(4) Canceling out (1/4)/(1/4) gives us:
[D1*C1]/[D2*C2] = [D1]2/[D2]2
(5) Multiplying both sides by (D2/D1) gives us:
C1/C2 = D1/D2
which means that:
C1*D2 = C2*D1
and finally that:
C1/D1 = C2/D2
QED
Definition 1: π
From the Corollary, we know that the ratio of the circumference to the diameter is constant. π is this ratio from circumference to diameter. In other words, π = C/D.
Corollary 2: The area of a circle is πr2.
Proof:
(1) From the theorem, the area of a circle is (1/2)(circumference)(radius)
(2) From the definition above, π = C/D
This means that C = D*Ï€ = 2*r*Ï€
(3) Putting this all together gives us:
area = (1/2)(circumference)(radius) = (1/2)(2*r*π)(r) = πr2
QED
References
Postulate 1: For a given chord of a circle, the segment of the circumference is longer than the chord.
In the example above, BDC is longer than BC.
Postulate 2: For a given segment of the circumference, lines connected above it combined are longer.
In the example above, AG + GE is greater than the segment of the circumference AE.
Lemma 1: The area of a regular polygon is (1/2)h*Q where Q is the sum of the perimeter.
Proof:
(1) A regular polygon can be divided up into a sum of triangles.
(2) The area of each triangle is equal to (1/2)*(GH)*(DE) [See here for details if needed]
(3) So, the area of the polygon = (# of sides)*(1/2)*(GH)*(DE)
(4) Let Q = the sum of the bases (for example, for the hexagon above, Q = DE + EF + FA + AB + BC + CD)
(5) Then, the area of the polygon = (1/2)*(GH)*Q
QED
Theorem: The area of a circle is (1/2)circumference * radius
Proof:
(1) Let K = (1/2)*C*R where C = circumference and R = radius.
(2) Let A = the area of the circle.
(3) Assume that A is greater than K
(4) We can inscribe a polygon inside A that is greater than K and less than A. [See Lemma 2 and the Method of Exhaustion here for details]
(5) So, the area of the polygon = (1/2)*Q*h where h is the distance from the center to the base and where Q is the perimeter of the polygon. [See Lemma 1 above]
(6) But Q is less than C (see Postulate 1 above) and h is less than R.
(7) So we have Area Polygon = (1/2)Q*h which is less than (1/2)*C*R
(8) But this contradicts step #4 so we reject step #3.
(9) Now, let's assume that K is greater than A.
(10) We can circumscribe a polygon P around A such that P is greater than A but less than K. [See Lemma 3 and Method of Exhaustion here for details.]
(11) From Lemma 1 again, we know that the area of this polygon is (1/2)*Q*h where Q is the perimeter of the polygon and h is the height.
(12) In the case of the circumscribed polygon (see diagram for Postulate 2), h = R.
(13) Using Postulate 2 above, we see that Q is greater than C.
(14) But then the area of the polygon is greater than K since (1/2)*Q*R is greater than (1/2)*C*R
(15) But this contradicts step #10 so we reject our assumption at step #9.
(16) Now, we apply the Law of Trichomoty (see here) and we are done.
QED
Corollary 1: For all circles, the ratio of Circumference to Diameter is constant
Proof:
(1) We know from Euclid (see here) that for any two circles C1 and C2 that:
Area1/Area2 = (Diameter1)2/(Diameter2)2
(2) We know from Theorem 1 above that:
Area of circle = (1/2)*radius*circumference.
(3) Combining step #1 with step #2 and using R=(1/2)D gives us:
[(1/2)*(1/2)D1*C1]/[(1/2)*(1/2)D2*C2] = [D1]2/[D2]2
(4) Canceling out (1/4)/(1/4) gives us:
[D1*C1]/[D2*C2] = [D1]2/[D2]2
(5) Multiplying both sides by (D2/D1) gives us:
C1/C2 = D1/D2
which means that:
C1*D2 = C2*D1
and finally that:
C1/D1 = C2/D2
QED
Definition 1: π
From the Corollary, we know that the ratio of the circumference to the diameter is constant. π is this ratio from circumference to diameter. In other words, π = C/D.
Corollary 2: The area of a circle is πr2.
Proof:
(1) From the theorem, the area of a circle is (1/2)(circumference)(radius)
(2) From the definition above, π = C/D
This means that C = D*Ï€ = 2*r*Ï€
(3) Putting this all together gives us:
area = (1/2)(circumference)(radius) = (1/2)(2*r*π)(r) = πr2
QED
References
- Archimedes, The Measure of a Circle
- William Dunham, Journey Through Genius
- David Joyce, Euclid's Elements
Sunday, April 30, 2006
Method of Exhaustion
In today's blog, I go over the proof for Eudoxus's Method of Exhaustion. This proof is used later in Euclid's proof that the areas of circles are in proportion to the squares of their diameters.
Theorem: Method of Exhaustion
Let x,y be any two positive real numbers where x is greater than y. If we continually remove a quantity v ≥ (1/2) from x, then eventually, we will be left with a value that is smaller than y.
Proof:
(1) We will only need to prove this for v = 1/2 since:
(a) This proof is done if we can show that there exists n such that (1/2)n*x is less than y.
(b) We only need to prove it for v=1/2 since we know that if v is less than (1/2), then:
vn*x is less than (1/2)*n*x.
(2) Let m be an integer such that m ≥ x/y + 1
(3) So that ym is greater than x
(a) Since ym is greater than y(x/y + 1) = x + y
(b) and x + y is greater than x since y is nonzero.
(4) There exists a value n such that 2n is greater than m.
(a) Let m = 1
(b) 21 = 2 is greater than 1.
(c) Assume this is true up to n.
(d) So that 2n is greater than n.
(e) Since 2n is greater than 1, we know that:
2n + 2n = 2*(2n) = 2n+1 is greater than n+1.
(f) So that this is true by induction.
(5) Thus, we see that y/x is greater than 1/2n
(a) ym is greater than x (step #2)
(b) so, m is greater than x/y
(c) and 1/m is less than y/x (or in other words, y/x is greater than 1/m)
(d) Now, 2n is greater than m so 1/2n is less than 1/m which also means that it is less than y/x.
(6) Thus (1/2)nx is less than y since y/x is greater than (1/2)n means that y is greater than (1/2)n*m.
QED
Now, let's look at two applications of the Method of Exhaustion.
Lemma 1: If a square is inscribed in a circle, its area is greater than half the area of the circle.
Proof:
(1) Let EFGH be a square that is inscribed in the circle above (see here for details on this construction).
(2) Let KLMN be a square that is circumscribed around the circle above (see here for details on this construction).
(3) The area of KLMN is greater than the area of the circle.
(4) The square EFGH is equal to (1/2) the area of KLMN since:
(a) Each square KFCE, FLGC, CGMH, ECHN are (1/4) the area of KLMN.
(b) Each triangle EFC, CFG, HCG, ECH is (1/4) the area of EFGH
(c) Each triangle EFC, CFG, HCG, ECH is (1/2) the area of the corresponding square KFCE, FLGC, CGMH, ECHN.
(d) Therefore, area EFGH = (1/2) * area KLMN
(5) Finally, area EFGH = (1/2)* area KLMN which is greater than the area of (1/2) the circle (from step #3).
QED
Lemma 2: For any area A that is smaller than the area of a circle C, there exists a regular polygon P that is smaller than C but greater than A.
Proof:
(1) Let us form a circle C on the diameter FH. [See here for details on construction]
(2) It is possible to find points E,G such EFGH forms a square that is inscribed in circle C [See here for details on this construction]
(3) The area of the square EFGH is greater than (1/2) the area of circle C [See Lemma 1 above]
(4) We can constructs points K, N, M, and L so that point K is midway between points E and F, N is midway between E and H, M is midway between H and G, and L is midway between G and F. [See here for details on this construction]
(5) Each triangle EKG, FLG, GMH, and HNE is greater in area than half the segment of the circle about it since:
(a) From each triangle, we can construct a rectangle that has an area greater than the circle segment. For example, around triangle EKG we can construct a rectangle as in the diagram above.
(b) Each half of the triangle is exactly 1/4 the size of the rectangle since each point bisects the side of the circumscribed square.
(c) So the triangle EKG is equal to (1/2) the area of the rectangle.
(d) Since the area of the rectangle is greater than the area of the segment, (c) gives us that the triangle EKG is greater than (1/2) the area of the segment.
(6) We can keep repeating this step so that each time, we remove more than (1/2) the area:
(a) We select the midpoints to each of the existing segments. [See step #4 for details]
(b) We form a triangle with these new midpoints from the points of the segment that this new point bisected.
(c) This set of triangles together forms a new regular polygon.
(d) Each triangle has more area than half the circle segment that had previously remained. [This is the same as the argument in step #5]
(11) So, then there eventually exists a polygon EKFLGMHN such that the area of this polygon is greater than the area of S. [From the Method of Exhaustion above since each time we do step #6, we are subtracting greater than 1/2 of the remaining area from the circle.]
QED
Lemma 3: If a regular polygon P1 with area A1 is circumscribed around a circle C, then there exists a smaller polygon P2 with area A2 that can also be circumscribed around circle C such that:
A2 - C is less than (1/2)(A1 - C)
Proof:
(1) Let C be a circle formed from diameter BD with center E. [See here for details on construction]
(2) Circumscribe a square GHKF around circle C. [See here for details on construction]
(3) Find a point M that lies on circle C and is midway between A and B [See here for details on construction]
(4) Let ON be a line tangent to M such that N is on GA and O is on GB.
(5) ∠ GMN is a right angle [See here for details]
(6) GN is greater than MN [See the corollary here for details]
(7) MN ≅ AN since:
(a) ∠ EAN ≅ ∠ EMN since they are both right angles.
(b) AE,ME are both radii, so we have AE ≅ ME and therefore (see Theorem 1, here), ∠ EAP ≅ ∠ EMP
(c) Using subtraction of step #7b from step #7a gives us ∠ NAM ≅ ∠ NMA.
(d) And #7c gives us AN ≅ MN since congruent angles implies congruent sides (see Corollary to Theorem 1, here)
(8) So GN is greater than AN too
(9) triangle AMN and triangle GMN have the same height since they are both on the same base AG and since they share the same vertice at M.
(10) Now, we can conclude that area of GMN is greater than the area of AMN since they share the same height (step #9) but the base of GMN is greater than the base of AMN (step #8) since area = (1/2)base * height (See Lemma 2 here for details if needed)
(11) triangle GLA ≅ triangle GLB by Side-Angle-Side since:
(a) GB ≅ GA since they are the sides of the same square.
(b) ∠ BGL ≅ ∠ AGL since we can prove triangle GAE ≅ triangle GBE by Side-Side-Side.
(c) Both triangles share the same side at GL.
(12) So the area of OGN is greater than half the area of BGA.
(13) The argument in step #11 applies to each side and we can conclude that converting this polygon from a 4-sided to 8-sided regular polygon results in removing greater than (1/2) the difference between the area of the 4-sided polygon and the area of the circle.
(14) We can use the same method to divide an 8-sided polygon to a 16-sided polygon and so on.
QED
References
Theorem: Method of Exhaustion
Let x,y be any two positive real numbers where x is greater than y. If we continually remove a quantity v ≥ (1/2) from x, then eventually, we will be left with a value that is smaller than y.
Proof:
(1) We will only need to prove this for v = 1/2 since:
(a) This proof is done if we can show that there exists n such that (1/2)n*x is less than y.
(b) We only need to prove it for v=1/2 since we know that if v is less than (1/2), then:
vn*x is less than (1/2)*n*x.
(2) Let m be an integer such that m ≥ x/y + 1
(3) So that ym is greater than x
(a) Since ym is greater than y(x/y + 1) = x + y
(b) and x + y is greater than x since y is nonzero.
(4) There exists a value n such that 2n is greater than m.
(a) Let m = 1
(b) 21 = 2 is greater than 1.
(c) Assume this is true up to n.
(d) So that 2n is greater than n.
(e) Since 2n is greater than 1, we know that:
2n + 2n = 2*(2n) = 2n+1 is greater than n+1.
(f) So that this is true by induction.
(5) Thus, we see that y/x is greater than 1/2n
(a) ym is greater than x (step #2)
(b) so, m is greater than x/y
(c) and 1/m is less than y/x (or in other words, y/x is greater than 1/m)
(d) Now, 2n is greater than m so 1/2n is less than 1/m which also means that it is less than y/x.
(6) Thus (1/2)nx is less than y since y/x is greater than (1/2)n means that y is greater than (1/2)n*m.
QED
Now, let's look at two applications of the Method of Exhaustion.
Lemma 1: If a square is inscribed in a circle, its area is greater than half the area of the circle.
Proof:
(1) Let EFGH be a square that is inscribed in the circle above (see here for details on this construction).
(2) Let KLMN be a square that is circumscribed around the circle above (see here for details on this construction).
(3) The area of KLMN is greater than the area of the circle.
(4) The square EFGH is equal to (1/2) the area of KLMN since:
(a) Each square KFCE, FLGC, CGMH, ECHN are (1/4) the area of KLMN.
(b) Each triangle EFC, CFG, HCG, ECH is (1/4) the area of EFGH
(c) Each triangle EFC, CFG, HCG, ECH is (1/2) the area of the corresponding square KFCE, FLGC, CGMH, ECHN.
(d) Therefore, area EFGH = (1/2) * area KLMN
(5) Finally, area EFGH = (1/2)* area KLMN which is greater than the area of (1/2) the circle (from step #3).
QED
Lemma 2: For any area A that is smaller than the area of a circle C, there exists a regular polygon P that is smaller than C but greater than A.
Proof:
(1) Let us form a circle C on the diameter FH. [See here for details on construction]
(2) It is possible to find points E,G such EFGH forms a square that is inscribed in circle C [See here for details on this construction]
(3) The area of the square EFGH is greater than (1/2) the area of circle C [See Lemma 1 above]
(4) We can constructs points K, N, M, and L so that point K is midway between points E and F, N is midway between E and H, M is midway between H and G, and L is midway between G and F. [See here for details on this construction]
(5) Each triangle EKG, FLG, GMH, and HNE is greater in area than half the segment of the circle about it since:
(a) From each triangle, we can construct a rectangle that has an area greater than the circle segment. For example, around triangle EKG we can construct a rectangle as in the diagram above.
(b) Each half of the triangle is exactly 1/4 the size of the rectangle since each point bisects the side of the circumscribed square.
(c) So the triangle EKG is equal to (1/2) the area of the rectangle.
(d) Since the area of the rectangle is greater than the area of the segment, (c) gives us that the triangle EKG is greater than (1/2) the area of the segment.
(6) We can keep repeating this step so that each time, we remove more than (1/2) the area:
(a) We select the midpoints to each of the existing segments. [See step #4 for details]
(b) We form a triangle with these new midpoints from the points of the segment that this new point bisected.
(c) This set of triangles together forms a new regular polygon.
(d) Each triangle has more area than half the circle segment that had previously remained. [This is the same as the argument in step #5]
(11) So, then there eventually exists a polygon EKFLGMHN such that the area of this polygon is greater than the area of S. [From the Method of Exhaustion above since each time we do step #6, we are subtracting greater than 1/2 of the remaining area from the circle.]
QED
Lemma 3: If a regular polygon P1 with area A1 is circumscribed around a circle C, then there exists a smaller polygon P2 with area A2 that can also be circumscribed around circle C such that:
A2 - C is less than (1/2)(A1 - C)
Proof:
(1) Let C be a circle formed from diameter BD with center E. [See here for details on construction]
(2) Circumscribe a square GHKF around circle C. [See here for details on construction]
(3) Find a point M that lies on circle C and is midway between A and B [See here for details on construction]
(4) Let ON be a line tangent to M such that N is on GA and O is on GB.
(5) ∠ GMN is a right angle [See here for details]
(6) GN is greater than MN [See the corollary here for details]
(7) MN ≅ AN since:
(a) ∠ EAN ≅ ∠ EMN since they are both right angles.
(b) AE,ME are both radii, so we have AE ≅ ME and therefore (see Theorem 1, here), ∠ EAP ≅ ∠ EMP
(c) Using subtraction of step #7b from step #7a gives us ∠ NAM ≅ ∠ NMA.
(d) And #7c gives us AN ≅ MN since congruent angles implies congruent sides (see Corollary to Theorem 1, here)
(8) So GN is greater than AN too
(9) triangle AMN and triangle GMN have the same height since they are both on the same base AG and since they share the same vertice at M.
(10) Now, we can conclude that area of GMN is greater than the area of AMN since they share the same height (step #9) but the base of GMN is greater than the base of AMN (step #8) since area = (1/2)base * height (See Lemma 2 here for details if needed)
(11) triangle GLA ≅ triangle GLB by Side-Angle-Side since:
(a) GB ≅ GA since they are the sides of the same square.
(b) ∠ BGL ≅ ∠ AGL since we can prove triangle GAE ≅ triangle GBE by Side-Side-Side.
(c) Both triangles share the same side at GL.
(12) So the area of OGN is greater than half the area of BGA.
(13) The argument in step #11 applies to each side and we can conclude that converting this polygon from a 4-sided to 8-sided regular polygon results in removing greater than (1/2) the difference between the area of the 4-sided polygon and the area of the circle.
(14) We can use the same method to divide an 8-sided polygon to a 16-sided polygon and so on.
QED
References
Subscribe to:
Posts
(
Atom
)