# Interactive Real Analysis

Next | Previous | Glossary | Map

## 2.3. The Principle of Induction

### 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.

• Denote by E the set of all elements from S for which property Q is not true
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