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

_{1}, s

_{2}, etc. are all elements of S. t

_{1}, t

_{2}, 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

_{1}) 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

_{1}) 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

_{1}) 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