The Set of Complex Numbers

In today's blog I go over the definition of complex numbers and show how this definition can be used to prove that the set of complex numbers forms a field.

Definition 1: Complex Number

A complex number is an ordered pair of real numbers: (x,y) where x,y are real numbers.


Definition 2: Addition of Complex Numbers

(a,b) + (c,d) = (a+c,b+d)


Definition 3: Multiplication of Complex Numbers

(a,b)*(c,d) = (a*c - b*d,a*d + b*c)


Definition 4: Equality

(a,b) = (c,d) if and only if a = c and b = d


Lemma 1: The set of complex numbers is closed on addition

Proof:

This follows directly from the fact that the real numbers are closed on addition [see Lemma 1, here] and Definition 2 above.

QED


Lemma 2: The set of complex numbers is closed on multiplication.

Proof:

This follows directly form the fact that the real numbers are closed on multiplication [see Lemma 2, here] and Definition 3 above.

QED


Lemma 3: The set of complex numbers supports the commutative rule for addition

Proof:

(1) By Definition 2 above:

(a,b) + (c,d) = (a+c,b+d)

(2) Since the real numbers support the commutative rule for addition [see Lemma 3, here]:

(a+c,b+d) = (c+a,d+b) = (c,d) + (a,b)

QED


Lemma 4: The set of complex numbers supports the associative rule for addition

Proof:

(1) By Definition 2 above:

[(a,b) + (c,d)] + (e,f) = (a+c,b+d) + (e,f) = ([a+c]+e,[b+d]+f)

(2) Since the real numbers support the associative rule for addition [see Lemma 4, here]:

([a+c]+e,[b+d]+f) = (a+[c+e],b+[d+f]) = (a,b) + [(c,d) + (e,f)]

QED


Lemma 5: The set of complex numbers support the commutative rule for multiplication

Proof:

(1) By definition 3 above, we have:

(a,b)*(c,d) = (a*c - b*d,a*d + b*c)

(2) Since the real numbers support the commutative rule for multiplication (see Lemma 5, here):

(a*c - b*d,a*d + b*c) = (c*a - d*b,d*a + c*b)

(3) Since the real numbers support the commutative rule for addition (see Lemma 3, here):

(c*a - d*b,d*a + c*b) = (c*a - d*b,c*b + d*a)

(4) Using Definition 3 above again:

(c,d)*(a,b) = (c*a - d*b,c*b + d*a)

QED


Lemma 6: The set of complex numbers support the associative rule for multiplication

Proof:

By definition 3 above, we have:

[(a,b)*(c,d)]*(e,f) = ([a*c - b*d],[a*d + b*c])*(e,f) =

= ([a*c-b*d]*e - [a*d+b*c]*f,[a*c - b*d]*f + [a*d+b*c]*e) =

= (a*c*e - b*d*e -a*d*f + b*c*f, a*c*f - b*d*f + a*d*e + b*c*e) =

= (a*[c*e - d*f] - b*[c*f + d*e],a*[c*f + d*e] + b*[c*e - d*f]) =

= (a,b)*([c*e - d*f],[c*f + d*e]) = (a,b)*[(c,d)*(e,f)]

QED


Lemma 7: The set of complex numbers support the distributive rule

Proof:

(1) By Definition 2 above:

(a,b)*[(c,d) + (e,f)] = (a,b)*(c+e,d+f)

(2) By Definition 3 above:

(a,b)*(c+e,d+f) = (a*(c+e) - b*(d+f),a*(d+f) + b*(c+e)) =

= (a*c+a*e - b*d -b*f, a*d+a*f +b*c+b*e) =

= ([a*c - b*d] + [a*e - b*f],[a*d + b*c] + [a*f + b*e]) =

= (a*c-b*d,a*d + b*c) + (a*e-b*f,a*f + b*e) =

= (a,b)*(c,d) + (a,b)*(e,f)

QED


Lemma 8: The set of complex numbers have an additive identity (0,0)

Proof:

(a,b) + (0,0) = (a+0,b+0) = (a,b)

QED


Lemma 9: Every element of the set of complex numbers has an additive inverse (-a,-b)

Proof:

(a,b) + (-a,-b) = (a+-a,b+-b) = (0,0)

QED


Lemma 10: The set of complex numbers has a multiplicative identity (1,0)

Proof:

(a,b)*(1,0) = (a*1 - b*0, a*0 + b*1) = (a,b)

QED


Lemma 11: If (a,b) ≠ (0,0) then a² + b² ≠ 0

Proof:

(1) From Definition 4 above:

(a,b) ≠ (0,0) implies either a ≠ 0 or b ≠ 0.

(2) a≠ 0 → a² is greater than 0

(3) b≠ 0 → b² is greater than 0

(4) So a² is 0 or positive and b² is 0 or positive

(5) In all cases, a² + b² is positive since:

position + 0 = positive

0 + positive = positive

positive + positive = positive

QED


Lemma 12: Every nonzero element of the set of complex numbers has a multiplicative inverse

Proof:

(1) Let (a,b) be any nonzero element of the set of complex numbers

(2) Let c =1/(a² + b²)

We know that a² + b² is nonzero from Lemma 11 above.

(3) The multiplicative inverse is (a*c,-b*c)

(4) And we see that:

(a,b)*(a*c,-b*c) = (a*a*c - b*(-b*c),a*(-b*c) + b*(a*c)) =

= (a*a*c +b*b*c,-a*b*c + a*b*c) = (a*a*c + b*b*c,0)

(5) a*a*c + b*b*c = a*a/(a*a + b*b) + b*b/(a*a + b*b) =

= (a*a + b*b)/(a*a + b*b) = 1

QED


Theorem 13: The complex numbers form a field

Proof:

(1) The complex numbers are closed on addition [see Lemma 1 above] and multiplication [see Lemma 2 above].

(2) The complex numbers support the commutative property of addition [see Lemma 3 above], the associative property of addition [see Lemma 4 above], the commutative property of multiplication [see Lemma 5 above], an associative property of multiplication [see Lemma 6 above], and a distributive property [see Lemma 7 above].

(3) The set of complex numbers has an additive identity property [see Lemma 8 above], an additive inverse property [see Lemma 9 above], a multiplicative identity property [see Lemma 10 above], and a multiplicative inverse property [see Lemma 12 above].

(4) From all these properties, the complex numbers form a field. [see Definition 3, here]

QED


Definition 5: i

i = (0,1)


Theorem 14: i² = (-1,0)

Proof:

The result follows directly from Definition 3 above:

(0,1)*(0,1) = (0*0 - 1*1,0*1 - 1*0) = (-1,0)

QED


Theorem 15: All real numbers can be represented as complex numbers

(1) Any real number x can be represented as (x,0) [see definition 1 above]

(2) This correspondence holds over addition

x + y = z if and only if (x,0) + (y,0) = (x+y,0) = (z,0)

(3) This correspondence holds over multiplication

x*y = z if and only if (x,0)*(y,0) = (x*y - 0*0,x*0 + 0*y) = (x*y,0) = (z,0)

QED


Definition 6: a+bi

a+bi = (a,b)

References

• H.A. Thurston, The Number System, Dover Publications, 1967
• Bruce E. Meserve, Fundamental Concepts of Algebra, Dover Books, 1981.

The Set of Real Numbers

In a previous blog, I showed how the Dedekind cut could be used to define the real numbers.

In today's blog, I will show that the real numbers form a field.

Lemma 1: The real numbers are closed on addition.

Proof:

(1) We can define the real numbers based on a Dedekind cut. [see Definition 2, here]

(2) Let x,y be the real numbers.

(3) From the definition of the Dedekind cut, x is the set of rational numbers that are less than x and y is the set of rational numbers that are less than y.

(4) x+y is defined as the set of rational numbers in x added to the set of rational numbers in y so that x+y is the set of all of possible sums.

(5) Since the rational numbers are closed on addition [see Lemma 2, here], it follows that x+y is also closed on addition.

QED

Lemma 2: The real numbers are closed on multiplication

Proof:

(1) We can define the real numbers based on a Dedekind cut. [see Definition 2, here]

(2) Let x,y be the real numbers.

(3) From the definition of the Dedekind cut, x is the set of rational numbers that are less than x and y is the set of rational numbers that are less than y.

(4) xy is defined as the set of rational numbers in x multiplied to the set of rational numbers in y so that xy is the set of all of possible products.

(5) Since the rational numbers are closed on multiplication [see Lemma 3, here], it follows that xy is also closed on multiplication.

QED

Lemma 3: The set of real numbers support the commutative rule for addition

Proof:

(1) By the definition of addition for real numbers, addition follows the properties of the set of rationals. [see Definition 5, here]

(2) So, the conclusion follows from the fact that the rational numbers support the commutative rule for addition. [see Lemma 4, here]

QED

Lemma 4: The set of real numbers support the associative rule for addition

Proof:

(1) By the definition of addition for real numbers, addition follows the properties of the set of rationals. [see Definition 5, here]

(2) So, the conclusion follows from the fact that the rational numbers support the associative rule for addition. [see Lemma 5, here]

QED

Lemma 5: The set of real numbers support the commutative rule for multiplication.

Proof:

(1) By the definition of multiplication for real numbers, multiplication follows the properties of the set of rationals. [see Definition 7, here]

(2) So, the conclusion follows from the fact that the rational numbers support the commutative rule for multiplication. [see Lemma 11, here]

QED

Lemma 6: The set of real numbers support the associative rule for multiplication

Proof:

(1) By the definition of multiplication for real numbers, multiplication follows the properties of the set of rationals. [see Definition 7, here]

(2) So, the conclusion follows from the fact that the rational numbers support the associative rule for multiplication. [see Lemma 8, here]

QED

Lemma 7: The set of real numbers support the distributive rule

Proof:

(1) The properties of multiplication of reals is based on the properties of rational numbers [see Definition 7, here] and the properties of addition of reals is based on the properties of rational numbers [see Definition 5, here].

(2) So, the conclusion follows from the fact that the rational numbers support the associative rule for multiplication. [see Lemma 10, here]

QED

Lemma 8: The set of real numbers have an additive identity

Proof:

(1) The additive identity is the set of all rational numbers less than 0.

(2) Let x be any real number.

(3) The x+0 be the set of all rational numbers less than x added to all rational numbers less than 0.

(4) Let a be any rational number less than x.

(5) Let b be any rational number less than 0 so that be must be negative.

(6) a + b is thus less than a which is less than x.

(7) Since b can be as close to 0 as we want, a+b can be as close to x as we want.

QED

Lemma 9: The real numbers support an additive inverse property

Proof:

(1) Let x be any real number

(2) Let -x be the set of rational numbers that are less than -x.

(3) Using the definition for addition (see Definition 5, here):

x+-x is the set of all rational numbers less than 0.

QED

Lemma 10: The set of real numbers supports a multiplicative identity property

Proof:

(1) Let x be any real number

(2) The multiplicative inverse is 1 which is the set of rational numbers less than 1.

(3) It is clear that x*1 = {the set of rational numbers less than x } = x.

QED

Lemma 11: The set of real numbers supports a multiplicative inverse property

Proof:

(1) Let x = be any nonzero real number

(2) The multiplicative inverse is 1/x

(3) This is clear since the set defined by x*1/x is the set of all rational numbers less than 1.

QED

Theorem 12: The real numbers form a field

(1) The real numbers are closed on addition [see Lemma 1 above] and multiplication [see Lemma 2 above].

(2) The real numbers support the commutative property of addition [see Lemma 3 above], the associative property of addition [see Lemma 4 above], the commutative property of multiplication [see Lemma 5 above], an associative property of multiplication [see Lemma 6 above], and a distributive property [see Lemma 7 above].

(3) The set of real numbers has an additive identity property [see Lemma 8 above], an additive inverse property [see Lemma 9 above], a multiplicative identity property [see Lemma 10 above], and a multiplicative inverse property [see Lemma 11 above].

(4) From all these properties, the real numbers form a field. [see Definition 3, here]

QED

The Set of Rational Numbers

In today's blog, I show how to formally construct the set of rational numbers from the set of integers.

I will then give a proof that the set of rational numbers forms a field. If you need a review of fields, check out here.

Definition 1: Set of rational numbers

We can define the set of rational numbers as the ordered pair of integers (a,b) where a,b are integers and b ≠ 0.


Definition 2: Addition of rationals

(a,b) + (c,d) = (ad + bc, bd)


Definition 3: Multiplication of rationals

(a,b) * (c,d) = (ac,bd)


Definition 4: Equality of rationals

Two rational numbers (a,b) and (c,d) are equal if and only if ad=bc.


Definition 5: Comparison of rationals

(a,b) is less than (c,d) if and only if abd² is less than b²cd.


Lemma 1: All integers can be represented as rational numbers

(1) Any integer x can be represented as (x,1) [see definition 1 above]

(2) This correspondence holds over addition

x + y = z if and only if (x,1) + (y,1) = (x*1+y*1,1*1) = (x+y,1) = (z,1)

(3) This correspondence holds over multiplication

x*y = z if and only if (x,1)*(y,1) = (xy,1*1) = (xy,1) = (z,1)

QED


Lemma 2: The set of rational numbers is closed on addition

Proof:

(1) The integers are closed on addition [see Lemma 1, here] and multiplication [see Lemma 2, here].

(2) So, it follows from Definition 2 above that the rational numbers are closed on addition.

QED


Lemma 3: The set of rational numbers is closed on multiplication

Proof:

The follows directly from Definition 3 and the fact that the integers are closed on multiplication [see Lemma 2, here].

QED


Lemma 4: The set of rational numbers satisfy the Commutative Rule for Addition

Proof:

(1) From Definition 2 above:

(a,b) + (c,d) = (ad + bc, bd)

(2) Since integers are commutative by addition (see Lemma 7, here):

(ad + bc, bd) = (bc + ad, bd)

(3) From Definition 2 again, we get:

(bc + ad,bd) = (c,d) + (a,b)

QED


Lemma 5: The set of rational numbers satisfy the Associative Rule for Addition

Proof:

From Definition 2 above:

[(a,b) + (c,d)] + (e,f) = (ad+bc,bd) + (e,f) = (adf+bcf + bde,bdf) = (a,b) + (cf + de,df) =

= (a,b) + [(cf + de,df)] = (a,b) + [(c,d) + (e,f)]

QED


Lemma 6: The set of rational numbers has an Additive Identity for all elements.

Proof:

(1) Using Definition 2 above, we have:

(a,b) + (0,c) = (a*c + 0*b,b*c) = (ac,bc)

(2) Using Definition 4 above, we note that:

(ac,bc) = (a,b) since acb = bca [using the commutative property multiplication for integers, see Lemma 8, here]

QED


Lemma 7: The set of rational numbers has an Additive Inverse for all elements.

Proof:

(1) Let (a,b) be a rational number.

(2) Then, it's additive inverse is (-a,b) since:

(a,b) + (-a,b) = (a*b + -a*b,b*b) = (ab-ab,b*b) = (0,b*b)

QED


Lemma 8: The set of rational numbers supports the Associative Rule for Multiplication

Proof:

Using Definition 3 above, we have:

[(a,b)*(c,d)]*(e,f) = [(ac,bd)]*(e,f) = (ace,bdf) = (a,b)*[(ce,df)] = (a,b)*[(c,d)*(e,f)]

QED


Lemma 9: (c,c) = (1,1)

Proof:

The follows directly from definition 4 above since:

c*1 = 1*c

QED


Lemma 10: The set of rational numbers supports the Distributive Rule

Proof:

(1) Using Definition 2 and Definition 3 above, we have:

(a,b)[(c,d) + (e,f)] = (a,b)*(cf+de,df) = (acf + ade,bdf)

(2) Using Definition 3 above and Lemma 8 above, we have:

(acbf + aebd,bdbf) = (b,b)*(acf + aed,bdf) = (1,1)*(acf + aed,bdf) = (acf + aed,bdf)

(3) Using Definition 2 above, we have:

(ac,bd) + (ae,bf) = (acbf + aebd,bdbf)

QED


Lemma 11: The set of rational numbers supports the Commutative Rule for Multiplication

Proof:

(1) Using Definition 3 above, we have:

(a,b)*(c,d) = (ac,bd)

(2) Using the Commutative Property of Multiplication for Integers (see Lemma 8, here):

(ac,bd) = (ca,db)

(3) Using Definition 3 above, we have:

(ca,db) = (c,d)*(a,b)

QED


Lemma 12: The set of rational numbers has a Multiplicative Identity

Proof:

For any rational number (a,b), we have (see Definition 3 above):

(a,b)*(1,1) = (a*1,b*1) = (a,b)

QED


Lemma 13: For every nonzero element, the set of rational numbers has a Multiplicative Inverse

Proof:

(1) Let (a,b) be any rational number.

(2) Then (b,a) will be its multiplicative inverse since:

(a,b)*(b,a) = (ab,ba)

(3) Using the Commutative Property of Multiplication of Integers (see Lemma 8, here), we have:

(ab,ba) = (ab,ab)

(4) Using Lemma 8 above, we have (ab,ab)=1.

QED


Theorem 14: The set of rational numbers forms a field

Proof:

This follows directly from Lemma 2 through Lemma 13 above and from Definition 3, here.

QED

References

• "Rational Numbers", Wikipedia.Org
• Bruce E. Meserve, Fundamental Concepts of Algebra, Dover Books, 1981.
  

Polynomials of an odd degree have at least one real root

Today, I present a proof taken from Edwards & Penney's Calculus and Analytic Geometry and PlanetMath.org.

I show that any polynomial of odd degree must have at least one root that is real.

Lemma 1:

lim (x → ∞) c/x = 0

where c is a nonzero constant

NOTE: This means that for any positive number ε, we can find a number δ such that:

for all abs(x) ≥ δ, abs(c/x) is less than ε

[See Definition 1, here for definition of mathematical limits]

Proof:

(1) Let ε be any positive number

(2) Assume c is positive.

(3) Let δ = 1 + c/ε

(4) So, then δ is greater than c/ε

(5) Which means that 1/δ is less than ε/c

(6) Which means that c/δ is less than ε

(7) For all n ≥ δ, it follows that:

c/n ≤ c/δ [which is less than ε from step #5 above]

(8) -c/δ is greater than -ε [this follows directly from step #5 from multiplying -1 to both sides]

(9) For all n ≤ -δ, it follows that:

c/n ≥ -c/δ [which is greater than -ε from step #7 above]

(10) Assume that c is negative

(11) Let δ = c/ε - 1

(12) So δ is less than c/ε

(13) So 1/δ is greater than ε/c

(14) Since c is negative, c/δ is less than ε [from multiplying a negative number to both sides]

(15) So for all n ≥ δ, it follows that:

c/n ≤ c/δ [which is less than ε from step #14 above]

(16) -c/δ is greater than -ε [this follows directly from step #14 from multiplying -1 to both sides]

(17) For all n ≤ -δ, it follows that:

c/n ≥ -c/δ [which is greater than -ε from step #16 above]

QED

Corollary 1.1:

limit (c/xⁱ) = 0

where c is a constant and i is a positive integer

Proof:

(1) For i=1, it is true from Lemma 1 above

(2) Let δ be the same δ from Lemma 1 above which depends on the sign of c.

(3) For all n ≥ δ, we have:

c/nⁱ ≤ c/n ≤ c/δ which is less than ε

(4) For all -n ≤ -δ, we have:

c/nⁱ ≥ c/n ≥ -c/δ which is greater than -ε

QED

Corollary 1.2:

Let g(x) = a₁/x + a₂/x² + ... + a_n-1/xⁿ

limit (x → ∞) g(x) = 0

Proof:

(1) For each a_i/xⁱ, the limit is 0. [From Corollary 1.1 above]

(2) Since g(x) is the sum of these values, we apply the Addition Rule [see Corollary 8.1, here] to get:

limit (x → ∞) g(x) = 0

QED

Lemma 2:

If f(x) is a polynomial of odd degree, there exists values a,b such that:

f(a) is less than 0 and f(b) is greater than 0

Proof:

(1) Let f(x) be a polynomial of an odd degree n such that:

f(x) = a₀xⁿ + a₁x^n-1 + ... + a_n-1x + a_n = 0

(2) We can make f(x) monic (where xⁿ does not have a coefficient) by dividing both sides by a₀.

So, we can assume the following monic form:

xⁿ + a₁x^n-1 + ... + a_n-1x + a_n = 0

(3) Let g(x) = (1/xⁿ)[a₁x^n-1 + ... + a_n-1x + a_n] =

= a₁/x + a₂/x² + ... + a_n-1/x^n-1 + a_n/xⁿ

(4) Then:

f(x) = xⁿ[1 + g(x)]

(5) Using Corollary 1.2 above, we know that there exists δ such that:

for all abs(x) ≥ δ, abs(g(x)) is less than 1 [where ε = 1]

(6) So, it follows that 1 + g(x) is greater than 0.

(7) Let b be any positive number greater than δ.

(8) It follows that f(b) is greater than 0 since bⁿ*[1 + g(x)] is greater than 0.

(9) Let a be any negative number where a is less than -δ.

(10) It follows that f(a) is less than 0 since aⁿ*[1 + g(x)] is less than 0.

QED


Theorem 3: A polynomial of odd degree has at least one real root

Proof:

(1) Let f(x) be a polynomial of odd degree.

(2) All polynomials are continuous [see Corollary 1.1, here], so f(x) is continuous.

(3) There exists a number a such that f(a) is less than 0. [see Lemma 2 above]

(4) There exists a number b such that f(b) is greater than 0. [see Lemma 2 above]

(5) Therefore, there exists at least one real root [see Weierstrass Intermediate Value Theorem, here]

QED

References

• "polynomial equation of odd degree", PlanetMath.Org
• Edwards, Jr. C. H. & Penney, David E., Calculus and Analytic Geometry, Prentice Hall, 1990
  

Elementary Symmetric Polynomials

If we look at Girard's Theorem, we see that:

xⁿ + a₁x^n-1 + a₂x^x-2 + ... + a_n = (x - x₁)*...*(x - x_n)

Now if we solve for each a_i in terms of x_i, we can restate the equation in terms of the elementary symmetric polynomials. In today's blog, I will show a proof of this using induction.


Definition 1: Elementary Symmetric Polynomials

s₁, ..., s_n such that:

s₁ = x₁ + ... + x_n

s₂ = x₁x₂ + ... + x_n-1x_n

s₃ = x₁x₂x₃ + ... + x_n-2x_n-1x_n

...

s_n = x₁x₂*...*x_n

So, let get down to showing the theorem.

Theorem 1: Restatement of Girard's Theorem in terms of the Elementary Symmetric Polynomials:

Xⁿ - s₁X^n-1 + s₂X^n-2 - ... + (-1)ⁿs_n = (X - x₁)(X - x₂)*...*(X-x_n)

Proof:

(1) xⁿ + a₁x^n-1 + a₂x^x-2 + ... + a_n = (x - x₁)*...*(x - x_n) [see Girard's Theorem]

(2) Assume n=1

(3) x + a₁ = x - x₁ = x - s₁

(4) Assume that the theorem holds true up until n.

(5) So that we have:

Xⁿ - (x₁ + ... + x_n)X^n-1 + (x₁x₂ + ... + x_n-1x_n)X^n-2 - ... + (-1)ⁿ(x₁x₂*...*x_n) = (X - x₁)(X - x₂)*...*(X-x_n)

(6) Multiplying (X - x_n+1) to both sides gives us:

(X - x₁)(X - x₂)*...*(X-x_n)*(X - x_n+1) = (X - x_n+1)[Xⁿ - (x₁ + ... + x_n)X^n-1 + (x₁x₂ + ... + x_n-1x_n)X^n-2 - ... + (-1)ⁿ(x₁x₂*...*x_n)] =

[Xⁿ⁺¹ - (x₁ + ... + x_n)Xⁿ + (x₁x₂ + ... + x_n-1x_n)X^n-1 - ... + (-1)ⁿX(x₁x₂*...*x_n)] - [Xⁿ(x_n+1) - (x_n+1)(x₁ + ... + x_n)X^n-1 + (x_n+1)(x₁x₂ + ... + x_n-1x_n)X^n-2 - ... + (-1)ⁿ(x₁x₂*...*x_n*x_n+1)]

= Xⁿ⁺¹ - (x₁ + ... + x_n + x_n+1)Xⁿ + (x₁x₂ + ... + x_nx_n+1)X^n-1 ... + (-1)ⁿ⁺¹(x₁*...*x_n+1) =

= Xⁿ⁺¹ - s₁Xⁿ + s₂X^n-1 - ... + (-1)ⁿ⁺¹s_n+1

QED

Quotient Rings

The following definitions and lemmas are taken from Jean Tignol's Galois' Theory of Algebraic Equations.

In a previous blogs, I wrote about cosets and ideals. In today's blog, I will show how we can bring these ideas together to define quotient rings. Here are links to review the properties of groups, subgroups, or commutative rings.

Definition 1: A/I

A/I = { a + I such that a ∈ A}

Note: This is a set of sets. For example, if a + I is a coset, then A/I is the set of distinct cosets. For review of the a + I notation, see here.

Example 1.1: Modular sets

The sets Z/nZ are all examples of A/I.

Z/2Z = { 0+2z, 1+2z } since { 0 + 2z = 2 + 2z = 2z + 2z, 1 + 2z = 3 + 2z = ... }

Z/3Z = { 0 + 3z, 1 + 3z, 2 + 3z }

A/I becomes especially interesting when A is a Commutative Ring and I is in an Ideal. I will assume both of these properties for the rest of this article.

Definition 2: Addition for A/I

(a + I) + (b + I) = (a + b) + I

Definition 3: Multiplication for A/I

(a + I) * (b + I) = ab + I

Lemma 1: Addition for A/I is well defined

Proof:

(1) Let:

s + I = s' + I

t + I = t' + I

(2) Using Lemma 1, here, it follows that:

s -s' ∈ I

and

t - t' ∈ I

(3) So, there exists a,b such that a, b ∈ I and:

s = s' + a

t = t' + b

(4) s + t = (s' + a) + (t' + b) = s' + a + t' + b

(5) s + t + I = s' + t' + (a + b) + I

(6) Since a ∈ I and b ∈ I, it follows that a + b ∈ I (from Closure)

(7) Using Lemma 2, here, we then have:

(a+b) + I = I

(8) So that:

s + t + I = s' + t' + I

QED

Lemma 2: Multiplication for A/I is well defined

Proof:

(1) Assume that I is an ideal.

(2) Let:

s + I = s' + I t + I = t' + I

(3) Using Lemma 1, here, it follows that:

s -s' ∈ I

and

t - t' ∈ I

(4) There exists a,b such that a, b ∈ I and:

s = s' + a t = t' + b

(5) st = (s' + a)(t' + b) = s't' + at' + s'b + ab

(6) st + I = s't' + at' + s'b + ab + I

(7) Since a,t',s',b ∈ I, we have (see Definition 2, here, and Definition 1, here for details):

at' ∈ I

s'b ∈ I

ab ∈ I

(8) So, at' + s'b + ab + I = I [See Lemma 2, here]

(9) And:

st + I = s't' + I

QED

Lemma 3: If A is a Commutative Ring and I is an Ideal, then A/I is a ring

Proof:

(1) Commutative Rule for Addition

(a + I) + (b + I) = (a + b) + I = (b + a) + I = (b + I) + (a + I)

(2) Associative Rule for Addition

[(a + I) + (b + I)] + (c + I) = (a + b) + I + c + I = (a + b + c) + I = a + I + (b + c) + I = (a + I) + [(b + I) + (c + I)]

(3) Additive Identity

0+I is the additive identity since 0 ∈ A and for all a, (a + I) + (0 + I) = (a + 0) + I = a + I

(4) Additive Inverse

-a+I is the additive inverse since a ∈ A → -a ∈ A and (a + I) + (-a + I) = (a + -a) + I = 0 + I

(5) Associative Rule for Multiplication

[(a + I)*(b+I)](c + I) = (ab + I)(c + I) = (abc + I) = (a + I)(bc + I) = (a+I)[(b+I)(c+I)]

(6) Distributive Rule

(a + I)[(b + I) + (c + I) ] = [(a + I)(b+I)] + [(a+I)(c+I)] = (ab + I) + (ac + I)

QED

Definition 5: Quotient Ring

The ring A/I is called the quotient ring of A by the ideal I.

Example 5.1: Sets that form quotient rings

Z/2Z and Z/3Z are factor rings [See Example 1.1 above for details]

Reference

• Jean-Pierre Tignol, Galois' Theory of Algebraic Equations, World Scientific, 2001

Cosets

The following definitions and lemmas are taken from Jean Tignol's Galois' Theory of Algebraic Equations.

Definition 1: g + H

Let g + H = { g + h such that h ∈ H }.

Example 1.1:

Let G be the set { 0, 1, 2, 3 }

Let H be the set { 9, 10, 11 }

Then:

0 + H = { 9, 10, 11 }

1 + H = { 10, 11, 12 }

2 + H = { 11, 12, 13 }

3 + H = { 12, 13, 14 }


Definition 2: coset of H in G

The set g + H is a coset if and only if there exists a group G such that g ∈ G and H is a subgroup of G.

Note: Technically, definition 3 above describes a left coset. A coset can also be defined as H + g which is called a right coset. The notation of g + H defines a coset based on addition. Cosets can also be defined on multiplication and represented as gH or Hg.

Example 2.1:

Let G = the set of integers Z
Let H = 2Z = the set of even integers

1 ∈ Z
1+H = odd integers = { ... -3, -1, 1, 3, ... }

Example 2.2: Cyclic Group Z₄

Z₄ = { 0, 1, 2, 3}

It is a group since:

(1) Closure

Since Z₄ is always modulo 4, it is clear that that operation of addition is closed (for example: 3 + 2 = 1)

(2) Associativity

For any elements a,b,c ∈ Z₄, (a + b) + c = a + (b + c)

(3) Identity Element

0 is the identity element

(4) Inverse Element

Since it is modulo 4, each element has an inverse: 0+0=0, 1+3=0, 2+2=0

Let H = { 0 , 2 }

H is a subset and H is itself a group since:

(1) It has closure: 0+2=2, 0+0=0, 2+2=0

(2) It has associativity.

(3) It has a identity element: 0

(4) From #1, it is clear that each element is its own inverse.

From Z₄ and H, there are 2 distinct cosets:

0 + H = { 0, 2}
1 + H = { 1, 3}
2 + H = { 2, 0} = 0 + H
3 + H = { 3, 1} = 1 + H

Lemma 1:

For the coset H in G:

For all a,b ∈ G:

a + H = b + H if and only if a - b ∈ H

Proof:

(1) Assume that a + H = b + H

(2) So, for all x ∈ (a + H) → x ∈ (b + H)

(3) a ∈ a + H, b ∈ b + H [since H is a group and therefore 0 ∈ H]

(4) a ∈ b + H [follows directly from step #2]

(5) Let c = a - b

(6) b + c ∈ b + H [since b + c = a and a ∈ b + H]

(7) So c ∈ H [from step #6 and Definition 3 above]

(8) Assume that (a-b) ∈ H

(9) Assume that x ∈ a + H

(10) Let y = x - a

(11) y ∈ H [since x = a + y]

(12) y + (a - b) ∈ H since H is a group

(13) x - b ∈ H [since y + (a - b) = (x - a) + (a - b) = x - b]

(14) Then x ∈ b + H since [b + x-b = x]

(15) We can make the same argument if x ∈ b + H so this shows that a + H = b + H.

QED

Lemma 2:

For the coset H in G:

a ∈ H → a + H = H

Proof:

(1) Assume that a ∈ H

(2) Assume that x ∈ a + H

(3) Then there exists h such that x = a + h where h ∈ H [See Definition 1 above]

(4) But if a ∈ H and h ∈ H, then a + h ∈ H. [since H is a group, see Definition 2 above and the Closure property of groups]

(5) So x ∈ H

(6) Assume that x ∈ H

(7) Let b = x - a

(8) Since a ∈ H, it follows that -a ∈ H [See Definition 2 above and the Inverse property of groups]

(9) Since x ∈ H and -a ∈ H, it follows that b ∈ H [from the Closure property of groups]

(10) So then, x ∈ a + H [since b ∈ H and x = a + b from Definition 1 above]

QED

Reference

• Jean-Pierre Tignol, Galois' Theory of Algebraic Equations, World Scientific, 2001

Ideals

The following definitions and lemmas are taken from Jean Tignol's Galois' Theory of Algebraic Equations.

Definition 1: stable under multiplication

a set I is stable under multiplication by the elements in A if and only if:

a ∈ A and x ∈ I ↔ ax ∈ I.

Example 1.1: set that is stable under multiplication

A = {1}

I = {1}

Example 1.2: set that is not stable under multiplication

A= {1,2}

I = {2}

2 ∈ A and 2 ∈ I but 2*2=4 is not in I.

Definition 2: An ideal I

Let A be a commutative ring.

a set I is an ideal if and only if I is a subgroup of the additive group of A which is stable under multiplication by the elements in A (see Definition 1 above).

Example 2.1: Example of a set that is an ideal: 2Z

The set 2Z is the set of even integers.

2Z = { ... -2, 0, 2, 4, 6, ... }

2Z is a subset of the set of integers Z and Z is a commutative ring and a group.

2Z is a group on the operation of addition so it is a subgroup of Z.

2Z is stable under multiplication by elements of Z since an even integer multiplied by any integer is an even integer.

Example 2.2: Example of a set that is not an ideal: 2W

Let 2W be the set of even whole numbers = { 0, 2, 4, ... }

2W is a subset of the set of integers Z which is a commutative ring and a group.

2W is not a group on the operation of addition since there is no inverse element.

2W is not stable under multiplication by the elements of Z since -1 ∈ Z and 2 ∈ 2W but -2 is not in 2W.

Lemma 1:

The set of multiples for a given polynomial is an ideal of the set of all polynomials for a given field

Proof:

(1) Let F[X] be the set of all polynomials in the field F

(2) Let (P) be the set of multiples of polynomials for a given polynomial P so that:

(P) = { PQ where Q ∈ F[X] }

(3) All fields are commutative rings so F[X] is a Commutative Ring. [See Definition 3, here for Fields]

(4) (P) is itself a group since:

(a) Closure on addition

If pq, pq' ∈ (P), then (pq+pq')=p(q+q') ∈ (P) since (q+q') ∈ F[X]

(b) Associativity on Addition

(pq + pq') + pq'' = p([q + q'] + q'') = p(q + [q' + q'']) = pq + (pq' + pq'')

(c) Identity Element

0 = P*0 ∈ (P) since 0 ∈ F[X]

(d) Inverse Element

For all pq, there exists -pq since -pq = p(-q) and -q ∈ F[X] if q ∈ F[X]

(5) Finally, (P) is stable under multiplication since:

(a) Assume pq, pq' ∈ (P)

(b) Then q,q' ∈ F[X]

(c) p ∈ F[X]

(d) So pqq' ∈ F[X] since F[X] is closed on multiplication.

(e) So p*(pqq') ∈ (P)

QED

Reference

• Jean-Pierre Tignol, Galois' Theory of Algebraic Equations, World Scientific, 2001

Derivative of Increasing and Decreasing Functions

Lemma: Derivative of Increasing and Decreasing Functions

Let f be a continuous function on (a,b) where the at no point f'(x)=0.

If for all x on [a,b], f(x) is increasing, then f'(x) is positive.

If for all x on [a,b], f(x) is decreasing, then f'(x) is negative.

Proof:

(1) From the definition of derivatives (see Definition 1, here):

f'(x) = lim (Δx → 0) [f(x + Δx) - f(x)]/(Δx)

So, the sign of f'(x) is the sign of [f(x + Δx) - f(x)]/Δx and we can assume that is is nonzero.

(2) Case I: Δx is positive

If f(x) is strictly increasing, then f(x + Δx) - f(x) is positive and f'(x) is positive.

If f(x) is striclty decreasing, then f(x + Δx) - f(x) is negative and f'(x) is negative.

(3) Case II: Δx is negative

If f(x) is strictly increasing, then f(x + Δx) - f(x) is negative and f'(x) is positive

If f(x) is strictly decreasing, then f(x + Δx) - f(x) is positive and f'(x) is negative.

QED

An Inequality Lemma for the Cauchy Bound of Real Roots

The following result is used my proof of Cauchy's Bound for real roots.

Lemma 1: abs(c)ⁿ = abs(cⁿ)

Proof:

(1) Assume that c is nonnegative

(2) Then, cⁿ is nonnegative

(3) Then, abs(cⁿ) = cⁿ

(4) Since abs(c) = c, it follows that: cⁿ = abs(c)ⁿ

(5) Assume that c is negative

(6) We can assume that n is odd

[Otherwise, cⁿ = (-c)ⁿ = abs(c)ⁿ = abs(cⁿ) ]

(8) abs(cⁿ) = -cⁿ = (-1)ⁿ*cⁿ = (-c)ⁿ = abs(c)ⁿ

QED

Lemma 2:

Let:

a_ncⁿ = -a_n-1c^n-1 + .... + -a₀

Then:

abs(a_n)*abs(c)ⁿ ≤ abs(a_n-1)*abs(c)^n-1 + ... + abs(a₀)

Proof:

(1) Using the Triangle Inequality (see Lemma 4, here), we know that:

abs(-a_n-1c^n-1 + .... + -a₀) ≤ abs(-a_n-1c^n-1) + ... + abs(-a₀)

so that:

abs(a_ncⁿ) ≤ abs(-a_n-1c^n-1) + ... + abs(-a₀)

(2) Using a basic property of inequalities (see Lemma 1, here):

abs(a_n)*abs(cⁿ) = abs(a_ncⁿ)

and likewise:

abs(-a_n-1)*abs(c^n-1) = abs(-a_n-1c^n-1)

...

(3) So we have:

abs(a_n)*abs(cⁿ) ≤ abs(-a_n-1)*abs(c^n-1) + ... + abs(-a₀)

(4) Using Lemma 1 above, we have:

abs(a_n)*abs(c)ⁿ ≤ abs(a_n-1)*abs(c)^n-1 + ... + abs(a₀)

QED

Triangle Inequality

Definition 1: Absolute Value

abs(a) = a if a is nonnegative or abs(a)=-a if a is negative.

So for example:

abs(5) = 5

abs(0) = 0

abs(-1) = 1

Now, let's look at some basic properties

Lemma 1: abs(ab) = abs(a)*abs(b)

Proof:

Case I: both a,b positive

abs(ab) = ab = abs(a)*abs(b)

Case II: both a,b negative

abs(ab) = ab = (-a)*(-b) = abs(a)*abs(b)

Case III: one negative, one positive

Assume a is positive, b is negative (since a,b are symmetrical, we can switch them as necessary)

abs(ab) = -ab = a*(-b) = abs(a)*abs(b)

QED

Lemma 2: -abs(a) ≤ a ≤ abs(a)

Proof:

Case I: a is nonnegative

-a ≤ a ≤ a

so

-abs(a) ≤ a ≤ abs(a)

Case II: a is negative

a ≤ a ≤ -a

so

-abs(a) ≤ a ≤ abs(a)

QED

Lemma 3: abs(a) ≤ b if and only if -b ≤ a and a ≤ b.

Proof:

(1) Assume abs(a) ≤ b

Case I: a is nonnegative

abs(a) = a

Since abs(a) ≤ b, it follows that a ≤ b and b is nonnegative

Since b is nonnegative and a is nonnegative, then it -b ≤ a.

Case II: a is negative

Since abs(a) ≤ b, it follows that -a ≤ b which is the same as -b ≤ a and therefore b must be nonnegative.

Since b is nonnegative, it follows that a ≤ b.

(2) Assume that -b ≤ a and a ≤ b.

Case I: a is nonnegative

Since a ≤ b, it follows that b is nonnegative

So abs(a) ≤ b.

Case II: a is negative

Since -b ≤ a, it follows that b ≥ -a.

Since a is negative, -a is positive, and we have:

abs(a) ≤ b.

QED

Lemma 4: Triangle Inequality

For all real numbers a,b

abs(a + b) ≤ abs(a) + abs(b)

Proof:

(1) For all real numbers a,b (from Lemma 1 above)

-abs(a) ≤ a ≤ abs(a)

-abs(b) ≤ b ≤ abs(b)

(2) Adding these two conditions together gives us:

-[abs(a) + abs(b)] ≤ a + b ≤ abs(a) + abs(b)

(3) Let c = a+b and d =abs(a) + abs(b)

(4) Using Lemma 3, we know that:

abs(c) ≤ d if and only if -d ≤ c and c ≤ d.

(5) But using step #2, we know that:

-d = -[abs(a) + abs(b)] ≤ c = a + b

and

c = a + b ≤ d = abs(a) + abs(b)

(6) So, using step #4 we get:

abs(c) ≤ d

which is equivalent to:

abs(a + b) ≤ abs(a) + abs(b)

QED

Polynomials are continuous

For a definition of polynomials, see Definition 1, here. For a definition of continuous functions, see Definition 1, here.

Lemma 1: f(x)=x is continuous

Proof:

(1) Let ε be any arbitrary value.

(2) Let δ = ε

(3) For any point c, it is clear that if x lies in (c - δ, c + δ), then f(x)=x lies in (f(c) - ε, f(c) + ε )

QED

Corollary 1.1 : Polynomials are continuous

Proof:

(1) The function f(x)=x is continuous. [See Lemma 1 above]

(2) Since the product of continuous functions is continuous [See Lemma 3, here], then f(x)=xⁿ where n is a positive integer is also continuous.

(3) Since f(x)=C is continuous [See Lemma 1, here], it follows that any function of the form cxⁿ is also continuous.

(4) Since the addition of continuous functions is continuous [See Lemma 2, here], it follows that any polynomial function is continuous since it consists of the form:

f(x) = c₀ + c₁x + c₂x² + ... + c_nxⁿ

where each c_i is a constant.

QED

Lemma 2: The Derivative of a polynomial is itself a polynomial

Proof

(1) The derivative of each term of a polynomial is itself a term of a polynomial [See the Lemma 2, here]

(2) So, it follows that the derivative itself is also a polynomial. [See Definition 1, here]

QED

Corollary 2.1: The derivative of a polynomial is a continuous function.

Proof:

This follows directly from Lemma 2 above and Corollary 1.1 above.

QED

Interval of a Function with Simple Roots

Lemma: Interval of a Function with Simple Roots

Let f be a function with simple roots such that f(c)=0

Then there exists an interval (a,b) such that:

c is in (a,b)

for all x in (a,b), f'(x) is all positive or all negative

Proof:

(1) Since f has only simple roots and f(c)=0, then it follows that f'(c) ≠ 0. [See Corollary 1.1, here]

(2) Since f is a polynomial, we know that f'(x) is continuous. [See Corollary 2.1, here]

(3) Since f'(c) is nonzero, let ε be nonzero and less than abs{ f'(c) }.

(4) Since f'(x) is continuous at c, there exists a number δ such that if x is in the (c - δ, c + δ), then f'(x) is in (f'(c)-ε, f'(c)+ε). [By the definition of a continuous function]

(5) Since ε is less than abs{f'(c) }, it follows that for x in (c -δ, c + δ), f'(x) is either entirely positive or entirely negative.

QED