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