Interactive Real Analysis - part of MathCS.org

Next | Previous | Glossary | Map | Discussion

Theorem 2.3.3: Induction Principle

Let S be a well-ordered set with the additional property that every element except for the smallest one has an immediate predecessor. Then: if Q is a property such that:
  1. the smallest element of S has the property Q
  2. if s S has property Q then the successor of s also has property Q
then the property Q holds for every element in S.

Proof:

It is not quite obvious what it is that we have to prove: we need to show that if a property holds for the smallest element of a well-ordered set S, and it holds for every successor of a general element of that set, then it is indeed true for the whole set S.

We will prove this by contradiction: Suppose property Q is true for the smallest element of a well-ordered set S, denoted by the symbol 1. Suppose also that property Q is true for the successor n + 1 of the general element n of that set, if it is assumed to be true for that element n.

Since S is well-ordered, the subset E contains a smallest element, say n. If n = 1, we would have a contradiction immediately. If n > 1, then it must have an immediate predecessor, denoted by the element n-1.

For that element the property Q holds true, and therefore, being true for n - 1 it must be true for (n-1) + 1 = n, by assumption. Hence, the set E must be empty, and property Q is therefore true for all of S.

Next | Previous | Glossary | Map | Discussion