The Principle of Induction

Definition: Ordered and Well-Ordered Set

• A set S is called partially ordered if there exists a relation r (usually denoted by the symbol ) between S and itself such that the following conditions are satisfied:
  1. reflexive: a a for any element a in S
  2. transitive: if a b and b c then a c
  3. anti-symmetric: if a b and b a then a = b
• A set S is called ordered if it is partially ordered and every pair of elements x and y from the set S can be compared with each other via the partial ordering relation.
• A set S is called well-ordered if it is an ordered set for which every non-empty subset contains a smallest element.

Examples:

• Determine which of the following sets and their ordering relations are partially ordered, ordered, or well-ordered:
  1. S is any set. Define a b if a = b
  2. S is any set, and P(S) the power set of S. Define A B if A B
  3. S is the set of real numbers between [0, 1]. Define a b if a is less than or equal to b (i.e. the 'usual' interpretation of the symbol )
  4. S is the set of real numbers between [0, 1]. Define a b if a is greater than or equal to b.
• Which of the following sets are well-ordered ?
  1. The number systems N, Z, Q, or R ?
  2. The set of all rational numbers in [0, 1] ?
  3. The set of positive rational numbers whose denominator equals 3 ?

Theorem: 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

Recall the this is very similar to parts of the Peano Axioms, and it is easy to see that the principle of induction applies to the well-ordered set of natural numbers.

To use the principle of induction for the natural numbers one has to proceed in four steps:

1. Define a property that you believe to be true for some ordered set (such as N)
2. Check if the property is true for the smallest number of your set (1 for N)
3. Assume that property is true for an arbitrary element of your set (n for N)
4. Prove that the property is still true for the successor of that element (n+1 for N)

Examples:

• Use induction to prove the following statements:
  • The sum of the first n positive integers is n (n+1) / 2.
  • If a, b > 0, then (a + b) ⁿ aⁿ + bⁿ for any positive integer n.
• Use induction to prove Bernoulli's inequality:
  • If x -1 then (1 + x) ⁿ 1 + n x for all n

Example:

1. The set of natural numbers, with the usual ordering, is well-ordered, and in addition every element except of 1 has an immediate predecessor. Now impose a different ordering labeled << on the natural numbers:
   • if n and m are both even, then define n << m if n < m
   • if n and m are both odd, then define n << m if n < m
   • if n is even and m is odd, we always define n << m
   Is the set of natural numbers, together with this new ordering << well-ordered ? Does it have the property that every element has an immediate predecessor ?
2. Suppose the induction principle defined above does not contain the assumption that every element except for the smallest has an immediate predecessor. Then show that it could be proved that every natural number must be even (which is, of course, not true so the additional assumption on the induction principle is necessary). A somewhat more complicated, but very useful theorem that can be proved by induction is the binomial theorem:

   Theorem: Binomial Theorem

   • Let a and b be real numbers, and n a natural number. Then:
     • 
   

   Based on the Induction principle is the principle of Recursive Definition that is used frequently in computer science.

   Definition: Recursive Definition

   • Let S be a set. If we define a function h from N to S as follows:
     1. h(1) is a uniquely defined element of S
     2. h(n) is defined via a formula that involves at most terms h(j) for 0 < j < n
   • Then this construction determines a unique function h from N to S.

   Examples:

   • Below are two recursive definitions, only one of which is valid. Which one is the valid one ?
     1. Let x₀ = x₁ = 1 and define x_n = x_{n - 1} + x_{n - 2} for all n > 1.
     2. Select the following subset from the natural numbers:
        • x₀ = smallest element of N
        • x_n = smallest element of [N - {x₀ , x₁ , x₂ , ..., x_{n + 1}}]
   When first encountering proofs by induction, it seems that anything can be proved. It is hard, in fact almost impossible, to find out why a particular property should be true when looking at an induction proof, and therefore, one might use induction to prove anything (Incidentally, such proofs are often called non-constructive proofs).

   Exercise:

   • Try to use induction to prove that the sum of the first n square numbers is equal to (n + 2)/3. (This induction proof should fail, since the statement is false - or is it true ?)
   Here is a more elaborate example of an invalid induction proof:

   Example:

   • All birds are of the same color.
   “Proof”
   • The property is clearly true for n = 1, because ‘one bird is of the same color’.
   • Assume that n birds are of the same color.
   • Now take (n+1) birds. Put one aside. There are n birds left, which, by assumption, are of the same color. For simplicity, say they are all black. Put the one bird back into the group, and take out another one. Again, there are n birds remaining, which by assumption must have the same color. In particular, the bird that was taken out in the first place must now have the same color as all the other birds, namely black. The bird taken outside was also black. Therefore, the n+1 birds must all be black.
   • But that means that we have proved property Q for all natural numbers by induction. Yet, the statement is obviously wrong. Where does this proof actually break down ?
   A similar word of caution applies to Recursive Definitions. While that principle can be very useful, one has to be careful not to get into logical difficulties.

   Example:

   • A classical example for a recursive definition that does not work is the paradox of the barber of Seville: The barber of Seville is that inhabitant of Seville who shaves every man in Seville that does not shave himself.
   • The problem here is: who shaves the barber ?

   ---

   Go Up | Next Section | Prev. Section | Glossary | Map

   ---

   (bgw)