Mathematical Limits

One of the most important ideas in calculus is the concept of the mathematical limit. Limits relate to continuous functions and the basic idea is that if as a value the argument x approaches the value a, the difference between the limit L and f(x) can be arbitrarily small.

Definition 1: Mathematical Limit:

A function f(x) has a limit of L at point a if given any number ε, there exists a positive number δ such that:
if x-a lies between -δ and +δ, then f(x) - L lies between -ε and ε

This definition is very similar to the definition of a continuous function (see here) and it is not surprising that the two concepts are very closely related.

In today's blog, I will need two definitions in order to prove the Squeeze Law relating to mathematical limits.

Definition 2: Open Interval :

x is an element of an open interval (α, β) if x is greater than α and x is less than β

Definition 3: Deleted Neighborhood

A deleted neighborhood is a set of points that result from deleting a single point in an open interval.

Lemma 1: Constant Law for Limits

if f(x) = C, then lim (x → a) f(x) = C

Proof:

(1) Let δ = 1

(2) if x - a lies between -δ and +δ, we know that f(x) = C.

(3) So, we know that f(x) - C = C - C = 0 which is less than any positive value ε

QED

Lemma 2: Product Law

if lim (x → a) f(x) = L and lim(x → a)g(x) = M, then
lim(x → a)[f(x)*g(x)] = L * M

Proof:

(1) Let ε be any nonzero value. We will prove that f(x)g(x) - LM lies between -ε and +ε

(2) Since the limit of f(x) = L, we know that there exists δ₁ such that:
if x - a is between -δ₁ and +δ₁, then f(x) - L is between -ε and +ε

Since by definition, if x - a is between -δ₁ and +δ₁, then f(x) is between -L and +L.

(3) We also know that there exists δ₂ such that:
if x - a is between -δ₂ and +δ₂, then f(x) - L is between -ε/(2M) and ε/(2M).

The definition for limits is that for any given positive value (ε), we can find a positive value (δ) to get the result (see above if review is needed).

(4) And there exists δ₃ such that:
if x - a is between -δ₃ and +δ₃, then g(x) - M is between -ε/(2L) and ε/(2L)

(5) Let δ = min(δ₁,δ₂,δ₃)

(6) Now, if x - a is between -δ and +δ, then:

(a) f(x) - L is between -ε/(2M) and +ε/(2M)

(b) g(x) - M is between - ε/(2L) and + ε/(2L)

(c) M[f(x) - L] is between (M)[-ε/(2M)] and (M)[+ε/(2M)] which is between -ε/2 and ε/2.

(d) f(x)[g(x) - M] is between (L)[-ε/(2L)] and (L)[+ε/(2L)] which is between -ε/2 and ε/2.

(e) If we add (c) + (d), we get:
f(x)M - LM + f(x)g(x) - f(x)M = f(x)g(x) - LM

(f) So, f(x)g(x) - LM is between (-ε/2 + -ε/2) and (+ε/2 + +ε/2) which means that it is between -ε and +ε

(7) So LM is the limit for f(x)g(x).

QED

Lemma 3: Squeeze Law

Suppose f(x), g(x), h(x) are functions such that
(a) f(x) ≤ g(x) ≤ h(x) for a deleted neighborhood (α, β) where point a is removed.
(b) lim (x→ a) f(x) = L = lim(x→a)h(x).

Then:
lim (x→ a) g(x) = L

Proof:

(1) Let ε be an arbitary number.

(2) Using the definition of limits, we know that there exists δ₁ and δ₂ such that:

if x-a lies between -δ₁ and +δ₁, then f(x)-L lies between -ε and +ε

if x-a lies between -δ₂ and +δ₂, then h(x)-L lies between -ε and +ε

(3) Let δ = min(δ₁,δ₂)

(4) We know that δ is greater than 0. [By the definition of mathematical limit]

(5) If x-a in between -δ and +δ, we know that f(x) and h(x) are both points of the open interval (L-ε, L+ε) [Again, from the definition of mathematical limit]

(6) So L-ε is less than f(x) ≤ g(x) ≤ h(x) which is less than L + ε

(7) Combining (#5) and (#6), this gives us that for any given ε, there exists a δ such that:
if x-a is in between -δ and +δ, then g(x)-L is between -ε and +ε

(8) From (#7), L is also a limit for g(x) as x approaches a.

QED

Lemma 4: Substitution Law

If lim (x → a) g(x) = L and lim (x → L) f(x) = f(L), then lim (x → a) f(g(x)) = f(L)

Proof:

(1) Let ε be any positive real value.

(2) Because lim (y → L) f(y) = f(L), we also know that there exists a value δ₁ such that:

if (y - L) is between -δ₁ and +δ₁, then f(y) - f(L) is between -ε and +ε

(3) Because lim (x → a) g(x) = L, we know that there exists a value δ₂ such that:

if (x - a) is between - δ₂ and +δ₂, then g(x) - L is between -δ₁ and +δ₁

(4) But this means if y = g(x), then:

if (x -a ) is between -δ₂ and +δ₂, then y - L is between -δ₁ and +δ₁ and f(g(x)) - f(L) is between -ε and +ε

(5) This then proves that:

lim (x → a) f(g(x)) = f(L)

QED

Lemma 5: lim (x → a) (1/x) = 1/a if a ≠ 0

Proof:

(1) Let ε be any positive real number.

(2) Assume that a is greater than 0.

(3) abs(1/x - 1/a) = abs([a - x]/ax) = abs([x -a]/ax) = (1/a)abs(x-a)/abs(x)

(4) Let us assume that abs(a-x) is less than a/2.

We can do this since abs(x-a) approaches 0 as x moves toward a.

(5) Then x -a is between -a/2 and +a/2 which means that x is between a/2 and 3a/2.

(6) This gives us that abs(x) is greater than a/2 and 1/abs(x) is less than 2/a.

(7) So that abs(1/x - 1/a) = abs(x-a)*(1/a)*abs(1/x) which is less than abs(x-a)*(1/a)(2/a) = 2/a² * abs(x-a)

(8) Let δ be the minimum of a/2 and a²ε/2

(9) Then if x - a is between -δ and +δ, then:

abs(1/x - 1/a) is less than (2/a²)(a²ε/2) = ε

This then proves that lim (x → a) (1/x) = 1/a for when a is greater than 0.

(10) Assume that a is less than 0

(11) Then

abs(1/x - 1/a) = abs(x-a)/(-a)*1/abs(x)

(12) If we assume that abs(x-a) is less than -a/2, then:

x - a is between -a/2 and +a/2, then x is between -3a/2 and -a/2.

(13) So abs(x) is greater than -a/2.

(14) So 1/abs(x) is less than -2/a.

(15) In this case, then:

abs(1/x - 1/a) = abs(x-a)/(-a)*1/abs(x) which is less than 1/(-a)*(-2/a)*abs(x-a) = 2/a²*abs(x-a)

(16) Let δ be the minimum of -a/2 and a²ε/2

(17) Then if x - a is between -δ and +δ, then:

abs(1/x - 1/a) is less than (2/a²)(a²ε/2) = ε

This then proves that lim (x → a) (1/x) = 1/a for when a is less than 0.

QED

Lemma 6: Reciprocal Law

if lim(x → a) g(x) = L and L ≠ 0, then lim (x → a) 1/g(x) = 1/L

Proof:

(1) Let f(x) = 1/x

(2) lim (x → a) f(x) = lim (x → a) (1/x)

(3) Using Lemma 5 above, we have:

lim (x → a) f(x) = 1/L = f(L)

(4) Applying the Substitution Law (Lemma 4 above) gives us:

lim (x → a) 1/g(x) = lim (x → a) f(g(x)) = f(L) = 1/L

QED

Lemma 7: Quotient Law

if lim (x → a) f(x) = L and lim (x → a) g(x) = M ≠ 0, then:

lim (x → a) f(x)/g(x) = L/M

Proof:

(1) Using the Product Law above, we have:

lim (x → a) f(x)/g(x) = lim (x → a)f(x) * lim(x → a)1/g(x)

(2) Using the Reciprocal Law above:

lim (x → a) 1/g(x) = 1/M

(3) Combining step #1 and step #2 gives us:

lim (x → a) f(x)/g(x) = L*(1/M) = L/M

QED

Lemma 8: abs(a + b - c - d)) ≤ abs(a - c) + abs(b - d)

Proof:

(1) If (a-c),(b-d) are the same sign, then abs(a + b - c -d) = abs(a -c) + abs(b - d)

(2) If (a-c),(b-d) are not the same sign, then abs(a - c + b - d) is less than abs(a -c) + abs(b-d).

QED

Corollary 8.1: Addition Law

if lim (x → a) f(x) = L and lim(x → a)g(x) = M, then
lim(x → a)[f(x)+g(x)] = L + M

Proof:

(1) Let ε be any nonzero value.

(2) Since the limit of f(x) = L, we know that there exists δ₁ such that:
if x - a is between -δ₁ and +δ₁, then f(x) - L is between -ε/2 and +ε/2

Since by definition, if x - a is between -δ₁ and +δ₁, then f(x) is between -L and +L.

(3) Since the limit of g(x) = L, we know that there exists δ₂ such that:
if x - a is between -δ₂ and +δ₂, then g(x) - M is between -ε/2 and +ε/2

Since by definition, if x - a is between -δ₂ and +δ₂, then g(x) is between -M and +M.

(4) Let δ = min(δ₁,δ₂)

(5) Now, if x - a is between -δ and +δ, then:

(a) f(x) - L is between -ε/2 and +ε/2

(b) g(x) - M is between - ε/2 and + ε/2

(c) By Lemma 8 above, abs([f(x) + g(x)] - (L + M)) ≤ abs(f(x) - L) + abs(g(x) - M)

(d) abs(f(x) - L) + abs(g(x) - M) ≤ η/2 + η/2 = η

(7) So L+M is the limit for f(x)+g(x).

QED

References

• Mathematical Limit, Wikipedia
• Edwards & Penny, Calculus and Analytic Geometry
  

Continous Functions

In mathematics, a function is a mapping from a set of input to an output. Each input is called an argument and the set of all arguments that can be put into this function is called the domain. The set of all outputs is called the range.

The standard notation for a function is the form f(x,y,z) where x,y,z are the arguments. In most of the examples of this blog, I am only using one argument so this type of function is represented as f(x) where x is the argument.

An equation such as e=mc² is a function. In this case, c is a constant since it is the speed of light so e=mc² is a function with only one argument m. So, we could represent Einstein's equation as: f(m) = mc²

A function is said to be continuous if as a function moves through input moves through a continuum of values, the output also moves through a continuum of values. The important idea is that there are no gaps in a continuous function. If a function has gaps, then it is not continuous.

Definition 1: Continuous at a Point

A function is continuous at a point c if and only if:
for any arbitrary value ε, there exists another a positive value δ such that:
if x is a point that lies between c - δ and c + δ, then f(x) lies between f(c) - ε and f(c) + ε

The important idea here is that if a function is continuous at c, then we can choose an arbitary interval ε such that we know that f(x) lies between f(c)-ε and f(c) + ε

Definition 2: Continuous Function

A function is said to continuous if it is continuous at all points in its domain.

Definition 3: Closed Interval [α, β]

A closed interval can be thought of as a set of elements that make up a subset of the domain for a function. For an interval [α, β], this includes all values x such that α ≤ x ≤ β.

Example: a closed interval on the real numbers

For example, we could set up a closed interval [-5,5] this would then include all numbers that are greater or equal to -5 and less than or equal to 5 including -5, -4.5, 0, and 4.

To show the importance of continous functions, let's consider the Weierstrass Intermediate Value Theorem.

Theorem: Weierstrass Intermediate Value Theorem

If f(x) is continuous at all parts of a closed interval [ α, β ] and if f(α) is less than 0 and if f(β) is greater than 0, then there exists a point γ ∈ [α, β] such that f(γ) = 0.

Proof:

(1) Since f(α) is less than 0, we know that there exists a value μ such that for all values x on [α, μ] f(x) is less than 0 and μ ≥ α.

(2) We can assume that if f(x) is less than 0, then it lies on the interval [ α, μ ] since:

(a) If there was a value ζ such that ζ is greater than μ and f(ζ) is less than 0, then it follows that for x greater than μ and less than ζ , f(x) ≥ 0. (Otherwise, we could assume that ζ ∈ [ α, μ ] )

(b) For the interval specified in (a) if f(x)=0, then we are done with the proof so to finish the proof, we can assume that this is not the case.

(c) If in the interval specified in (a) f(x) is greater than 0, then we can set β to a value greater than μ and less than ζ where f(x) is greater than 0.

(d) In this case, we have a smaller interval than the original but we can make the assumption that there is no value ζ greater than μ where f(ζ) is less than 0.

(e) If we prove that f(γ)=0 exists for this smaller interval, we are likewise proving that it exists in the bigger interval.

(3) Let S be the bounded set on [α, μ] (See the note here for the definition of a bounded set)

(4) Since we are dealing with real numbers, we know that there exists a least upper bound γ for S [See here for proof]

(5) Assume f(γ) = v which is greater than 0.

(6) Since we are dealing with a continuous function, by the definition 1 above, we know that there exists a value δ such that at point γ:
if x is between γ - δ and γ + δ, then f(x) lies between f(γ) - v/2 and f(γ) + v/2. [Where I chose ε = v/2 as the arbitrary value.]

(7) From (#6), we know that if x lies between γ - δ and γ + δ, then:
f(x) lies between v - v/2 and v + v/2 [Since f(γ) = v from #5]

(8) From (#7) we have thta:
f(x) lies between v/2 and 3v/2.

(9) Now μ is greater than γ - δ since:

(a) Assume μ ≤ γ - δ

(b) Then, γ - δ is an upper bound for [α,μ] since for all x ∈ [α,μ] x ≤ γ - δ

(c) And γ - δ is less than γ since δ is a positive value.

(d) But γ is the least upper bound from #4

(e) So we have a contradiction and we reject (a).

(10) And μ is less than γ + δ since μ ≤ γ since γ is the least upper bound.

(11) Since μ is in between γ - δ (#9) and γ + δ (#10), we can use (#8) to conclude that:
f(μ) is greater than v/2 which means by step #4 that f(μ) is greater than 0.

(12) But this is a contradiction since f(μ) is less than 0 by our original assumption in #1 so we can reject our assumption in #4 and conclude that f(γ) ≤ 0.

(13) Let's assume that f(γ)=v is less than 0.

(14) Applying #7, we can conclude that if x lies between γ - δ and γ + δ, then:
f(x) is less than 0 since f(x) is less than 3v/2 which ≤ 3(0)/2 ≤ 0 [From #13]

(15) We know that there exists a value ν such that ν is greater than γ and ν is less than γ + δ since:

(a) Let ν = (2*γ + δ)/2. [We can make this assumption be the definition of multiplication, addition, and division on real numbers, see here]

(b) We see ν is less than γ + δ since γ + δ = (2*γ + 2*δ)/2 and 2*δ is greater than δ since δ is a positive value.

(c) We see that ν is greater than γ since γ = 2*γ/2 and 2*γ is less than 2*γ + δ.

(16) Since ν lies between γ - δ and γ + δ, we can use step #13 to conclude that f(ν) is less than 0.

(17) But this also contradicts our assumption in #2 since it presupposes that there exists a value ν which is greater than μ where f(ν) is less than 0.

(18) So we can reject our assumption in #13.

(19) This then gives us that f(γ) =0 since it cannot be greater than 0 (from #12) and it cannot be less than 0 (from #18)

QED

References

• Continuous Function, Wikipedia
• Function, Wikipedia
  
• Weierstrass Intermediate Value Theorem, MathWorld
  

Dedekind Cut

The Dedekind Cut is mathematical construction created by Richard Dedekind to provide a definition for the real numbers.

The Dedekind Cut itself is defined in terms of the rational numbers.

Definition 1 - Dedekind Cut

A Dedekind cut α is defined as the subset of the rational integers Q (ratios of integers) which is less than α.

NOTE: Q is used to present the set of all rational numbers; R is used to represent the set of all real numbers, and Z is used to represent the set of all integers.

Example: π

We could create a Dedekind Cut around π. In this case, we could think of 3, 22/7, -4, etc. as elements of the Dedekind Cut. On the other hand, 32/10, 4, etc. would not be elements of the cut.

Definition 2 - Set of Real Numbers R

The set of real numbers is the set of Dedekind cuts α that have the following properties:

(a) α is not empty

(b) α contains no greatest element

For any element x ∈ α, there exists y ∈ α such that x is less than y.

(c) If x,y are rational integers where y is less than x, then x ∈ α → y ∈ α.

With these definitions, we have enough the construct the properties of the real numbers.

Definition 3: Additive Identity: 0

0 is defined as the set { x ∈ Q such that x is less than 0 }

Definition 4: Multiplicative Identity: 1

1 is defined as the set { x ∈ Q such that x is less than 1 }

Definition 5: Addition

α + β is defined as the set { x + y such that x ∈ α, y ∈ β }

Definition 6: Subtraction

α - β is defined as the set { x - y such that x ∈ α, y ∈ β }

Definition 7: Multiplication

α * β is defined as the set { x * y such that x ∈ α, y ∈ β }

Definition 8: Division

α / β is defined as the set { x/y such that β ≠ 0, x ∈ α, y ∈ β }

Definition 9: Irrational Numbers

A real number α is said to be irrational if α ∩ Q does not have a least element.

Now, I will present a proof for a fundamental property of reals using the Dedekind Cut.

Theorem 1: Every real number that is bounded above has a least upper bound.

(1) Let Α be a set of real numbers that is bounded by γ such that α ∈ Α → α ≤ γ

NOTE: Bounded above just means that there is an element γ that is greater or equal to all the elements that make up A.

(2) The union of all the sets that make up Α are themselves a real number because:

(a) Since each real number α is a Dedekind cut, we know that each α is the set of x ∈ Q such that x is less than some real number.

(b) Since each α is not empty, the union of all elements that make up α is not empty.

(c) We know that the union does not have a greatest element since if it did, this element would likewise be the greatest element for whichever real number that it is an element for but this is impossible since by definition, none of the real numbers have a greatest element.

(d) If x ∈ the Union and y is less than x, then y is necessarily an element of the Union, since y would necessarily be an element of the real number that x is an element of.

(3) The union of all sets that make up A is an upper bound for A since every element of A ⊆ Union of all sets of A.

(4) Now, γ is an arbitrary upper bound, so all we need to prove is that A ⊆ γ since this shows that A is necessarily less than or equal to any given upper bound.

(5) But this is easy to prove since x ∈ A → x ∈ γ since we defined each element of A as less than γ.

QED

Theorem 2: For any positive real number ε, there exists a natural number n such that:

0 is less than 1/n is less than ε

Proof:

(1) We can find a natural number n such that:

(n-1) ≤ (1/ε) ≤ n.

(2) Taking the reciprocal for each gives us:

1/(n-1) ≥ ε ≥ 1/n.

QED

Corollary 2.1: Between any two distinct real numbers, there exists a rational number.

Proof:

(1) Let x,y be real numbers such that y is greater than x.

(2) By Theorem 2 above, there exists an integer n such that: 1/n is less than y - x.

(3) Let m = floor(n*x) where floor(n*x) returns the highest integer that is less than n*x.

(4) From this, we know that:

(m/n) ≤ x and x is less than (m+1)/n.

(5) Further, we have:

(m + 1)/n = m/n + 1/n ≤ x + 1/n is less than x + y - x = y.

(6) So that, we have:

x is less than (m+1)/n is less than y.

QED

References

• Dedekind Cut, PlanetMath
• Dedekind Cut, Wikipedia
• Supremum, Wikipedia
  

Derivatives

A derivative in mathematics refers to the rate of change of a mathematical function. For purposes of this blog, I will only focus on functions of the form f(x), that is, a function in terms of a single variable which I will label x. For those who are not familiar with the concept of a mathematical function, see here.

It is assumed that the function f(x) is continuous. This is an important assumption since any function which is not continuous does not have a derivative. On the other hand, not all continuous functions have a derivative (see here).

For continuous functions, finding the rate of change (the derivative) comes down to finding the ratio of: (Δy)/(Δx) where x is a value as small as possible. In mathematical terms, we are finding this ratio as x approaches a limit of 0. We use the limit because of the problem of division by 0. Division by 0 is undefined but it is quite valid to take the limit that a value reaches at its divisor approaches 0.

For example, 1/x = infinity as x approaches 0

NOTE: This is different than saying 1/0 which is undefined. You can think of the concept of a limit to 0 as Newton's workaround for division by 0.

Sometimes, Δy is written as dy and Δx is written as dx. In both cases, the value is meant to be the smallest value whose limit is 0.

There are many conventions for representing the derivative of a function. In my blog, I will use three forms:

d/dx(x)
f'(x)
fⁿ(x)

Each one serves a different purpose. f'(x) represents the derivative of a given function f(x). fⁿ(x) implies the n-order derivative which is equivalent to f'(f'(f'(f'...(x))))).

d/dx makes it clearer which variable is being used in the derivative. For example:
f(x) = u + v
f'(x) = du/dx + dv/dx

We can now look at a more formal definition of a derivative in terms of a limit.

Definition 1: Derivative of f(x)

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

I will show how this equation is worked out in the lemmas below.

Definition 2: Differentiable

A function is said to be differentiable at a given point if a derivative exists for that point.

In today's blog, I will go over some very basic results using derivatives.

Lemma 1: Constant Rule: If a is a constant, (d/dx)(a) = 0

f(x + Δx) - f(x) = a - a = 0

QED

Lemma 2: Power Rule: (d/dx)(axⁿ) = nax^n-1

(1) f(x) = axⁿ

(2) f(x + Δx) - f(x) = a(x + Δx)ⁿ - axⁿ

(3) Applying the Binomial Theorem, gives us:


(4) So a(x + Δx)ⁿ - axⁿ, gives us:


(5) Then, dividing by Δx gives us:


(6) Finally, since Δx approaches 0, we can replace Δx with 0 to get:


(7) This then gives us:


QED

Example 1: (d/dx)(5x) = 5

f(x) = 5x

f'(x) = (d/dx)(5x) = d/dx(5x¹) = (1)5x⁰ = 5.

Example 2: (d/dx)(1/x) = -1/(x²)

f(x) = 1/x

f'(x) = (d/dx)(1/x) = (d/dx)(x^-1) = (-1)x^-2 = -1/(x²)

Example 3: (d/dx)(4x²) = 8x

f(x) = 4x²

f'(x) = (d/dx)(4x²) = (4)(2)x¹ = 8x

Lemma 3: Derivative of a Linear Combination

f(x) = a*g(x) + b*h(x) → f'(x) = a*g'(x) + b*h'(x) where a,b are constants.

(1) f(x) = a*g(x) + b*h(x)

(2) f'(x) = f(x + Δx) - f(x) = a*g(x + Δx) + b*h(x + Δx) - [a*g(x) + b*h(x)] =

= a*[g(x+Δx) - g(x) ] + b*[h(x + Δx) - h(x)] = a*g'(x) + b*h'(x)

QED

Example 1: (d/dx)(4x + 5) = 4

f(x) = 4x + 5

f'(x) = (d/dx)(4x) + (d/dx)(5) = 4 + 0 = 4

Example 2: (d/dx)(2x² + 3x) = 4x + 3

f(x) = 2x² + 3x

f'(x) = (d/dx)(2x²) + (d/dx)(3x) = 4x + 3

Lemma 4: Product Rule: f(x) = g(x)h(x) → f'(x) = g(x)h'(x) + g'(x)h(x)(1) Let f(x) = g(x)h(x)

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

= lim(Δx → 0)[g(x + Δx)h(x+Δx)-g(x)h(x+Δx)+g(x)h(x+Δx)-g(x)h(x)]/Δx =

= lim(Δx→0)[g(x+Δx)h(x+Δx)-g(x)h(x+Δx)]/Δx +
lim(Δx→0)[g(x)h(x+Δx) - g(x)h(x)]/Δx =

= lim(Δx→0)[g(x+Δx)-g(x)]/Δx * lim(Δx→0)h(x+Δx) +
lim(Δx→0)g(x)*lim(Δx→0)[h(x+Δx)-h(x)]/Δx

(3) Now, we note that:
lim(Δx→ 0)g(x) = g(x)

lim(Δx→0)h(x+Δx) = h(x)

(4) We also note that:
lim(Δx→0)[g(x+Δx) - g(x)]/Δx = g'(x)

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

(5) Combining #2, #3, and #4 gives us:
f'(x) = g'(x)h(x) + g(x)h'(x)

QED

Lemma 5: Reciprocal Rule

If f(x) is differentiable at x and f(x) ≠ 0 and u(x)=1/f(x)

Then:

u'(x) = -f'(x)/[f(x)]²

Proof:

(1) From the definition of the derivative and the definition of u(x), we have:

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

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

(3) Since:

[f(x) - f(x + Δx)]/[Δx*f(x + Δx)*f(x)] =(-1)*(1/[f(x+Δx)f(x)])*([f(x+Δx)-f(x)]/Δx),

we can use the Product Rule for Limits (see Lemma 2, here) to get:

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

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


(5) Since:

lim (Δx → 0)(-1) = -1.

lim (Δx → 0)(1/[f(x+Δx)f(x)]) = 1/[f(x)]²

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

We have:

u'(x) = (-1)*( 1/[f(x)]²)* f'(x) = -f'(x)/[f(x)]²

QED

Lemma 6: The Quotient Rule

If f(x) and g(x) are differentiable at x and g(x) ≠ 0, and u(x)=f(x)/g(x) with u(x) differentiable at x, then:

u'(x) = [f'(x)g(x) - f(x)g'(x)]/[g(x)]²

Proof:

(1) Using the definition for u(x), we have:

u(x) = f(x)/g(x) = f(x)*1/g(x)

(2) Using the Product Rule (see Lemma 4 above), we have:

u'(x) = f(x)*D[1/g(x)] + f'(x)*[1/g(x)]

(3) Using the Reciprocal Rule (see Lemma 5 above), we know that:

D[1/g(x)] = -g'(x)/[g(x)]²

(4) Applying step #3 to step #2 gives us:

u'(x) = f(x)*[-g'(x)/[g(x)]²] + f'(x)/g(x) = [-f(x)g'(x) + f'(x)g(x)]/[g(x)]² = [f'(x)g(x) - f(x)g'(x)]/[g(x)]²

QED

Set of Integers

The set of integers can be constructed from the Natural Numbers.

We can define the set of integers as the set NxN where "x" is the Cartesian Product.

In set theory, the Cartesian Product is the combination of all the elements of one set with all the elements of the other set forming pair.

So, if N = { 1, 2, 3 ... }, then NxN = { (1,1), (1,2), (1,3), ..., (2,1),(2,2), ..., }

Here is the definition for integers:

Definition 1: Set of Integers: Z is the set NxN where (a,b) is the same number as (c,d) if and only if a + d = b + c.

NOTE: Z stands for Zahlen which is German for number.

From this perspective, each number corresponds to the set of all values (a,b) where a-b is equal to the number.

So 0 for example corresponds to { (1,1), (2,2), .... }

And -1 corresponds to { (1,2), (2,3), ... }

We can use the definition to show that (1,1) ~ (2,2) in that 1 + 2 = 1 + 2.

From this, we can now define addition, multiplication, and subtraction.

Definition 2: (a,b) + (c,d) = (a + c, b + d)

Example:

-1 + -3 = (2,3) + (5,8) = (2+5,3+8) = (7,11) = -4

Definition 3: (a,b) * (c,d) = (ac + bd, ad+bc)

Example:

-1 * -1 = (1,2)*(1,2) = (1*1 + 2*2,1*2 + 2*1) = (1 + 4,2 + 2) = (5,4) = 1

-1 * 3 = (1,2)*(4,1) = (1*4 + 2*1,1*1 + 2*4) = (4 + 2,1 + 8) = (6,9) = -3

Definition 4: (a,b) - (c,d) = (a + d, b + c)

Example:

4 - 3 = (5,1) - (4,1) = (5 + 1, 1 + 4) = (6, 5) = 1

(-3) - (-5) = (2,5) - (1,6) = (2 + 6, 5 + 1) = (8, 6) = 2

3 - 4 = (4,1) - (5,1) = (4 + 1, 1 + 5) = (5,6) = -1

Definition 5: (a,b) is less than (c,d) if and only if a + d is less than b + c

Example:

-3 is less than 4 since (2,5) is less than (5,1) since 2+1=3 is less than 5 + 5=10.

Lemma 1: Z is closed under addition.

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

(2) a + c is a natural number and b + d is a natural number (since addition is closed for natural numbers, see here)

QED

Lemma 2: Z is closed under multiplication

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

(2) ac, bd, ad, bc are all natural numbers since N is closed under multiplication (see here)

(3) ac + bd, ad + bc are natural numbers since N is closed under addition (see here)

QED

Lemma 3: Z is closed under subtraction

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

(2) a + d, b + c are both natural numbers since N is closed under addition (see here)

QED

Lemma 4: Z has 0 as the identity element for addition

n + 0 = (n+1,1) + (1,1) = (n + 2,2) = n

QED

Lemma 5: Z has 1 as the identity element for multiplication

n * 1 = (n + 1, 1)*(2,1) = (2*(n+1) + 1*1, (n+1)*1 + 2) = (2n + 3,n + 3) = n

QED

Lemma 6: Each element of Z has an inverse element for addition that is determined by reversing the pairs (b,a) is the inverse element for (a,b)

n + (-n) = (n+1,1) + (1,n+1) = (n + 1 + 1, 1 + n + 1) = (n+2,n+2) = 0

QED

Lemma 7: Z is commutative on addition: a + b = b + a

a + b = (a+1,1) + (b+1,1) = (a + b + 2,2)
b + a = (b+1,1) + (a+1,1) = (b + a + 2,2) = (a + b + 2,2) [Since natural numbers are commutative on addition, see here]

QED

Lemma 8: Z is commutative on multiplication: a*b=b*a

a*b = (a+1,1)*(b+1,1) = ((a+1)(b+1) + 1*1,(a+1)*1 + 1*(b+1)) =
= (ab + a + b + 1 + 1, a + 1 + b + 1) =
= (ab + a + b + 2,a + b + 2) = ab

b*a = (b+1,1)*(a+1,1) = ((b+1)(a+1) + 1*1,(b+1)*1 + 1*(a+1)) =
= (ba + a + b + 2, a + b + 2) =
= (ab + a + b + 2, a + b + 2) = ab [Since natural numbers are commutative on multiplication, see here]

QED

Lemma 9: Z is associative on addition

(a+b) + c = [(a+1,1) + (b+1,1)] + (c+1,1) = (a+b+2,2) + (c+1,1) = (a+b+c+3,3)=
= a+b+c

a + (b+c) = (a+1,1) + [(b+1,1) + (c+1,1)] = (a+1,1) + (b+c+2,2) = (a+b+c+3,3) =
= a+b+c

QED

Lemma 10: Z is associative on multiplication

(a*b)*c = [(a+1,1)*(b+1,1)]*(c+1,1)=
= [(a+1)(b+1) + (1)(1),(a+1)(1) + 1(b+1)](c+1,1) =
= (ab + a + b + 2, a+1+b+1)(c+1,1) = (ab+1,1)(c+1,1) =
= ((ab+1)(c+1) + (1)(1), (ab+1)(1)+(1)(c+1)) =
= (abc + ab + c + 1 + 1, ab + 1 + c + 1) =
= (abc + ab + c + 2, ab + c + 2) = abc

a*(b*c) = (a+1,1)[(b+1,1)(c+1,1)] =
= (a+1,1)((b+1)(c+1) + (1)(1),(b+1)(1)+(1)(c+1)) =
= (a+1,1)(bc + b + c + 1 + 1,b+1+c+1) =
= (a+1,1)(bc+b+c+2,b+c+2)=(a+1,1)(bc+1,1)=
= ((a+1)(bc+1) + (1)(1),(a+1)(1) + (1)(bc+1)) =
= (abc + a + bc + 1 + 1,a + 1 + bc + 1) =
= (abc + 1, 1) = abc

QED

Lemma 11: Z is distributive: (a+b)c =ac + bc.

(a+b)c = [(a+1,1)+(b+1,1)](c+1,1) = [(a + b + 2,1+1)](c+1,1) = (a+b+1,1)(c+1,1) =
= ((a+b+1)(c+1) + (1)(1),(a+b+1)(1) + (1)(c+1)) =
= (ac + bc +c + a + b + 1 + 1,a + b + 1 + c + 1) =
= (ac + bc + 1, 1) = ac + bc.

QED

References

• Integers, Wikipedia
• Integer, PlanetMath
• Integer, Dr. Noach Dana Picard's Page

Natural Numbers

The natural numbers are the numbers that are most familiar to us; they are the counting numbers that usually begin at 1 (some mathematicians hold that the natural numbers include 0). This also matches with the history of mathematics where the use of 0 was a major innovation.

The mathematician Kronecker once said:
"God made the natural numbers. Everything else is the work of man." (Quoted from here)

At the same time, this leads us to an interesting question. Is it possible to define the natural numbers in terms of a set of axioms similiar to what Euclid did for geometry?

The successful definition of natural numbers was done by two men: Richard Dedekind in his book What is a Number and the logician Guiseppe Peano. Today, these axioms are known as Peano's Axioms.

Here are a set of postulates based on Peano's Axioms:

I. The natural numbers is a set of numbers starting with 1 where each number has a unique successor which we will characterize by S(a) where a is a natural number.

II. All numbers but 1 have are themselves successors to a unique number.

III. a = b if and only if S(a) = S(b)

IV. If a property is possessed by 1 and possession by a value a implies it is also true of S(a), then we say it is true of all numbers. (Axiom of Induction)

Definition 1: m + n

m + 1 = S(m)
m + S(n) = S(m + n)

Example:

1 + 2 = S(1 + 1) = S(S(1)) = S(2) = 3

Definition 2: m * n

m * 1 = m
m * S(n) = m + (m * n)

Example:

2 * 2 = 2 + (2*1) = 2 + 2 = 4

Definition 3: m is less than n

m is less than n if there exists a natural number d such that m + d = n.

Definition 4: m - n

S(m) - 1 = m
S(m) - S(n) = m - n

If m is less than or equal to n, then it is undefined.

Lemma 1: Natural numbers are closed under addition.

(1) m+1 = S(m)
(2) Assume that there exists a value n such that m + n is a natural number.
(3) m + S(n) = S(m+n)
(4) Which must also be a natural number by Axiom I.

QED

Lemma 2: Natural numbers are closed under multiplication

(1) m*1 = m
(2) Assume that there exists a value n such that m * n is a natural number
(3) m*S(n) = m + (m*n)
(4) Which is a natural number by Lemma 1 above.

QED

Lemma 3: Natural numbers are not closed under subtraction.

m - n is undefined for the case where m ≤ n.

QED

Lemma 4: 1 + m = S(m)

(1) Case n=1:

1 + 1 = S(1)

(2) Assume that it is true up to n.

(3) 1 + (n+1) = 1 + S(n) = S(n+1)

(4) So, it is true by Axion IV.

QED

Lemma 5: Natural numbers are commutative under addition: m + n = n + m

(1) For case n=1:

m + 1 = S(m)

(2) From Lemma 4, 1 + m = S(m)

(3) Assume it is true up to n so that m+n=n+m

(4) m + (n+1) = m + S(n) = S(m+n)

(5) (n+1) + m = S(n) + m = S(n+m) = S(m+n)

(6) So, we apply Axiom IV and we are done.

QED

Lemma 6: 1*m = m*1

(1) 1*1 = 1*1

(2) S(m)*1 = S(m) [By Definition 2 above]

(3) 1*S(m) = 1 + m = m + 1 = S(m)

(4) We are done since all numbers are either 1 or a successor to another number. (by Axion II)

QED

Lemma 7: Distributive Law: (a + b)m = am + bm

(1) Case m = 1:

(a + b)1 = a + b [By Definition 2]

a(1) + b(1) = a + b [By Definition 2]

(2) So we assume that it is true up to n so that (a+b)n = an + bn.

(3) (a+b)S(n) = (a + b) + (a+b)n = a + b + an + bn = a + an + b + bn

(4) a(S(n)) + b(S(n)) = a + an + b + bn

(5) So by the Axiom of Induction we are done (see Axiom IV)

QED

Lemma 8: Natural numbers are commutative under multiplication: m * n = n * m

(1) Case n=1:

m * 1 = 1 * m [From Lemma 6 above]

(2) Assume that it is true up to n so that we have m*n=n*m

(3) m*(n+1) = m + mn [By definition 2]

(4) (n+1)*m = nm + m = m + nm = m + mn

(5) So we are done by the Axion of Induction (Axiom IV above)

QED

Lemma 9: Natural numbers are associative under addition:
(a + b) + n = a + (b + n)

(1) Case n = 1

(a + b) + 1 = S(a + b)

a + (b + 1) = a + S(b) = S(a + b)

(2) (a + b) + S(n) = S(a + b + n)

(3) a + (b + S(n)) = a + S(b + n) = S(a + b + n)

(4) It is true now in all cases since all numbers are either 1 or are a successor (by Axiom II above)

QED

Lemma 10: Natural numbers are associative under multiplication:
(a*b)*n = a*(b*n)

(1) Case n = 1

(a*b)*1 = a*b

a*(b*1) = a*b

(2) (ab)*S(n) = S(n)(ab) = (n+1)(ab) = abn + ab

(4) a*(b*S(n)) = a*(b*(n+1)) = a*((n+1)*b) = a*(bn+b) = (bn+b)*a = abn+ab

QED

References

• Peano Axioms, Wikipedia
• Peano Arithmetic, Planet Math
• Natural Numbers, Dr. Noach Dana Picard's Page
  

Continued Fractions; Loose Ends

In today' s blog, I will provide details that are used in the general proof for Continued Fractions.

Lemma 1: If x is a positive integer, then x² - 4 is not a square.

(1) First, I will show that for all positive integers greater than 2, the difference between one square and the next highest square is greater than 4 therefore no square x² - 4 can exist.

(2) For n=2, the smallest difference is 9 - 4 = 5 which is greater than 4.

(3) We assume that this is true up to n ≥ 2.

(4) So (n+1)² - n² = n² + 2n + 1 - n² = 2n + 1 ≥ 2(2) + 1 = 5.

(5) In other words, the minimal difference between any two successive squares is at least 5.

(6) Now, I will show that all differences 2 or less don't work either.

3² - 2² = 9 - 4 = 5
2¹ - 1² = 1
1² - 0² = 1

The only possible differences then are 1, 2, or a number ≥ 5.

QED

Quadratic Equation Solved

One of the most useful formulas of all time historically is the solution of the equation:
ax² + bx + c = 0.

The equation above is known as the quadratic equation.

Theorem: (-b ± √b² - 4ac)/2a is the solution to the quadratic equation.

(1) First, we multiply both sides by 4a and get:

4a²x² + 4abx + 4ac = 0

(2) Next, we add b² - b² to the equation:

4a²x² + 4abx + b² + 4ac - b² = 0

(3) Now, we add b² - 4ac to both sides which gives us:

4a²x² + 4abx + b² = b² - 4ac

(4) Further, we know that:

(2ax + b)² = 4a²x² + 4axb + b²

(5) Combining #4 and #3, gives us:

(2ax + b)² = b² - 4ac

(6) Now, taking the square root of both sides gives us:

2ax + b = ±√b² - 4ac

(7) Now, using basic algebra, we get to:

x = (-b ±√b² - 4ac)/2a.

Irrational Numbers

Irrational numbers are numbers that cannot be formed by the ratio of two integers. In Ancient Greece, the mathematician and philosopher Pythagoras created a secret society whose sole goal was to study the universe in terms of numbers. Pythagorus had discovered that musical harmonies result from perfect ratios between string sizes and became convinced that all the universe could be studied in terms of these perfect ratios. For example, the most famous discovery of his group was the Pythagorean Theorem which states that the hypotenuse (the diagonal) of a right triangle is equal to the sum of the squares of its sides. In other words: if c is the length of the hypotenus, a,b are the length of the other sides, then c² = a² + b².

It turns out that the Pythagorean Theorem is itself a proof for the existence of irrational numbers. For example, if a=1, b = 1, then c = √2. Here in lies one of the most famous irrational numbers.

Theorem: if p is a prime then √p is irrational.

(1) Assume that there exists two values a,b such that: a/b = √p and such that a,b are the lowest positive fraction such that gcd(a,b)=1.

NOTE: We know that in fractions, if a,b had any common factors, then we could divide them off and still maintain the same ratio.

(2) Then a²/b² = p and therefore a² = pb².

(3) So, we see that p divides a. So there exists a value a' such that a=pa'. [This is true by Euclid's Lemma since p is a prime and it divides either a or a]

(4) So, we get (pa')² = pb² which means that p²a'² = pb².

(5) Dividing both sides by p, we get: pa'² = b².

(6) But now we see that p divides b (again by Euclid's Lemma). This is a contradiction since a,b do not have any common divisors so we can reject our initial assumption.

QED

Lemma 1: if α is irrational, a,b are rational, and b ≠ 0, then a + bα is irrational

(1) Let x = a + bα

(2) bα = x - a

(3) α = (x - a)/b

(4) Now, this proves that x is not rational. Since if x is rational, then (x-a)/b would be rational, but this is impossible since (x-a)/b = α which is irrational.

QED

Lemma 2: if α is irrational, then 1/α is irrational

(1) Let y = 1/α

(2) Then, α = 1/y.

(3) This proves that y is not rational. If it were, then 1/y would be rational but it isn't since 1/y = α which is irrational.

QED

Lemma 3: if a,b are rational and α is irrational, and a + bα is rational, then a=b=0.

(1) By Lemma 1 above, if a + bα is rational, then b = 0.

(2) Since a + bα = 0 we know that a = 0 - bα = 0 - 0 = 0

QED

Lemma 4: For any positive real number ε, there exists a positive irrational number that is less than ε

Proof:

(1) Let p be a prime such that √p is greater than 1/ε [We can make this assumption based on Euclid's Theorem about infinite primes, see here]

(2) By the Theorem above, we know that √p is an irrational number.

(3) Now, if based on step #1, we know that:

1/√p is less than ε

(4) We also know that 1/√p is an irrational number from Lemma 2 above.

QED

Corollary 4.1: For any two distinct rational numbers, there exists an irrational number that is in between.

Proof:

(1) Let x,y be two distinct rational numbers where x is greater than y.

(2) We can see that if ε is any positive number less than x - y, then, y + ε lies in between x and y.

(3) By Lemma 4 above, we know that there exists an irrational number α that is less than ε.

(4) Further, we know that y + α is also irrational [by Lemma 1 above] and we know that y + α lies in between x and y.

QED

Review of Matrices

In today's blog, I will review some very basic results in 2x2 and 1x2 matrices.

This represents a very basic introduction that is meant to provide background for my larger blog on Fermat's Last Theorem: n = 5 (see here).

Today's blog is based on the work by Harold M. Stark in his book An Introduction to Number Theory.

1. Matrix defined

A matrix is a grouping of numbers that allows working on all the numbers at the same time.

For example, let's consider a 2 x 2 matrix that can be based on a set of numbers: 1, 2, 3, 4.

The matrix itself looks like this:


2. Addition and subtraction of matrices

Addition and subtraction of matrices are exactly the same as if you added and subtracted the numbers independently:




3. Multiplication of Numbers with Matrices

Multiplication with an integer just applies the integer to all the values involved so that:


4. Product of Two Matrices

In addition to these properites, matrices have there own special operations. The product of 2 matrices is a bit confusing. We define a product of a 1 x 2 matrix with a 2 x 2 matrix as the following:


We define a product a 2 x 2 matrix with a 2 x 2 matrix as the following:


Now, here's where it gets a bit confusing. We normally refer to a matrix using a capital letter. So let's say we have two matrices A,B such that: A is a 2x2 matrix and B is a 2x2 matrix. We cannot assume that AB = BA. For example, if we reverse the matrices above, we get the following equation:


Another important point is that there is no product defined for a 2x1 matrix and a 2x2 matrix or a 2x2 matrix and 1x2 matrix (since order is important in matrix products) and for that matter, there is no product defined a 2x2 matrix with a 1x2 matrix. In the case of 2x2 matrices, you can only get a product for a 2x2 matrix with a 2x2 matrix or a 1x2 matrix with a 2x2 matrix.

5. Determinant

A determinant is a value that is derived from a 2x2 matrix. Here is the definition:


Lemma 1: det(AB) = (detA)(detB)

(1) Let A =


Let B =


(2) AB =


(3) det(AB) = (ae+bg)(cf+dh) - (af+bh)(ce+dg) = (acef + adeh + bcfg + bdgh) - (acef + adfg + bceh + bdgh) = adeh + bcfg - adfg - bceh.

(4) det(A) = ad - bc
(5) det(B) = eh - fg
(6) So det(A)det(B) = (ad - bc)(eh - fg) = adeh + bcfg - adfg - bceh

QED

6. Identity Matrix

The Identity Matrix is referred to as I and defined as:


Lemma 2: AI = IA = A

(1) Let A =


(2) AI =


(3) IA =


QED

7. Inverse

Let A =


We denote the inverse of A as A^-1 and we define it as:
A^-1 =



Lemma 2: AA^-1 = A^-1A = I

(1)






(2)




QED

Lemma 3: det A^-1 = 1/(det A)

(1) (det A)(det A^-1) = det(AA^-1) [From Lemma 1]

(2) det(AA^-1) = det(I) [From Lemma 2]

(3) det(I) = 1*1 - 0*0 = 1. [Definition of I, Definition of Determinant]

(4) So, (det A)(det A^-1) = 1

(5) And dividing both sides by (det A) gives us:
det A^-1 = 1/(det A)

QED

7. Final Points

The last point here is that while AA^-1 = I, it is not necessarily true that ABA^-1 = B. The reason is that AB does not necessarily equal BA and we are not allowed to change the order of the matrix elements.

Basic Lemmas Needed for FLT: n = 5

Here are some basic lemmas that are used by the proof for Fermat's Last Theorem: n=5.

Lemma 1: (p+q)⁵ + (p-q)⁵ = 2p(p⁴ + 10p²q² + 5q⁴)

(1) Using the Binomial Theorem:
(p + q)⁵ = p⁵ + 5p⁴q + 10p³q² + 10p²q³ + 5pq⁴ + q⁵
(p - q)⁵ = p⁵ - 5p⁴q + 10p³q² - 10p²q³ + 5pq⁴ - q⁵

(2) Adding these two values together gives us:
2p⁵ + 20p³q² + 10pq⁴ = 2p(p⁴ + 10p²q² + 5q⁴)

QED

Lemma 2:

If:

t = q⁴ + 50q²r² + 125r⁴
u = q² + 25r²
v = 10r²

Then:

t = u² - 5v²

(1) u² = (q² + 25r²)² = q⁴ + 50q² r² + 625r⁴

(2) -5v² = -5(10r²)² = -500r⁴

(3) (q² + 25r²)² + -5(10r²)² = q⁴ + 50q² r² + 625r⁴ + -500r⁴ = q⁴ + 50q² r² + 125r⁴

QED

Some Simple Division Lemmas

In this blog, I want to outline some simple implications of the division which are very useful in basic mathematical reasoning:

Lemma 1:

If:

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

Then:

d divides c

(1) By assumption (b) and (c), we know that there exists a',b' such that:

a = a'd
b = b'd

(2) So,

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

Lemma 2:

If

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

Then

d divides b

(1) c = a + b → b = c -a = c + (-a)

(2) This results follows from Lemma 1 above.

Mathematical Induction

Mathematical induction is a method for proving a condition is true of an infinite set that obeys the well-ordering principle.

A set is considered well-ordered if for any subset of elements, one can always find one element which is the smallest. An example of a well-ordered set is the set of positive integers. One element is clearly the smallest. For example, if 1 is an element in the set, then it will be the smallest element.

Not all sets are well-ordered. For example, negative integers are not well-ordered. In such an infinite set, there is never one element which is the smallest. Likewise, real numbers are not a well-ordered set. For any number, it is possible to find another number which is smaller if only by a fraction. There is no smallest value.

It is useful to introduce some notation when talking about well-ordered sets. Sets are often refered to as capital letters such as S, T, R. Elements are often refered to as lowercase letters such as s,t,r.

We can imagine that s is an element of S, t is an element of T, and r is an element of R. Likewise, we can use a subscript to differentiate elements so that s₁, s₂, etc. are all elements of S. t₁, t₂, etc. are all elements of T.

When talking about induction, we are always trying to prove some proposition true about an entire set. When talking about a proposition or fact, I will use the following form p(). So, for example, p(s₁) means that the proposition is true of the first element of the set S. Likewise p(S) means that the proposition is true of all elements of set S.

Finally, I need to use the concept of implication which is symbolized by →. Implication doesn't say something is true or false. Rather, it describes a relationship. If a certain condition is true, then another condition follows. If I were president, I would be living in Washington, D.C. This doesn't mean that I am president and it doesn't mean that if I am living in Washington, D.C., then I am the president. It simply means that if the first condition were true (if I were the president), then the second condition would follow (then I would live in Washington, D.C.).

With this notation, I can now state the Principle of Mathematical Induction:

Theorem: Principle of Mathematical Induction: if p(s₁) is true and if p(s_n) → p(s_n+1), then p(S).

(1) Let's start by assuming that the theorem is false.

(2) Let's let s_i be the first element in order where p(s_i) is not true.

(3) Well i cannot be the first element since we are assuming that p(s₁) is true.

(4) So, this means that p(s_i-1) must be true since i is the first element where the proposition is not true.

(5) But if p(s_n) is true, then p(s_n+1) is true, so therefore p(s_i) must be true since p(s_i-1) is true.

(6) But this is a contradiction so we reject (1) and conclude that the theorem is true.

QED