Week 8, Day 1

Today we discussed the process of mathematical induction. 

The following is an example problem demonstrating how this process is executed: 

Step 1: Prove the statement is true at the starting point (usually n = 1)

Step 2: Assume the statement is true for n. Prove the statement is true for n + 1. 

The Well-Ordering Principle is a concept equivalent to mathematical induction. It states that every non-empty set of positive integers contains a least element. The phrase "well-ordering principle" is synonymous to "well-ordering theorem." On other occasions, it is understood to bethe proposition that the set of intergers (..., -2, -1, 0, 1, 2, 3,...) comtains a well-ordered subset, called the natural numbers, in which every nonempty subset contains a least element. Depending on the framework in which the natural numbers are introduced, this (second order) property of the set of natural numbers is either an axiom or a provable theorem. In fact, there is a proof that shows how mathematical induction implies the validity of the Well-Ordering Principle. 

Ultimately, as demonstrated by this proof, mathematical induction can be correlated to the Well-Ordering Principle, and this principle, in turn, can support induction.