Thread: use the well-ordering property to prove the Principle of Strong induction

use the well-ordering property to prove the Principle of Strong induction

I don't know how to start...

I know the well-ordering property is If S is a nonempy set of N, then there exists an element m ∈ S such that m≤k for all k∈S

and the Principle of Strong induction is:
Let P be property of N, assume:
1) P(1) holds
2) if P(1),...,P(n-1) hold, then P(n) holds ∀n≥2, then ∀n P(n)

the Principle of Strong induction is:
Let P be property of N, assume:
1) P(1) holds
2) if P(1),...,P(n-1) hold, then P(n) holds ∀n≥2, then ∀n P(n)

This is strong induction on natural numbers with usual ordering. In general, strong induction can be used on any well-ordered set, and its proof is no more difficult.

Suppose you have a set A well-ordered by <. The strong induction principle is:

If for all x in A, (for all y < x, P(y)) implies P(x), then for all x in A, P(x).

You may wonder where the base case is. The set A has the least element, call in x0. Then the premise "for all y < x0, P(y)" is vacuously true: there are no y < x0. Therefore, "(for all y < x0, P(y)) implies P(x0)" is equivalent to P(x0). The idea is that in the induction step, you have to prove P(x) from all P(y) for y < x. Since x0 is the least element, you get no help and you have to prove P(x0) directly.

The easiest way to prove strong induction is by contradiction. Assume that for all x in A, (for all y < x, P(y)) implies P(x). Also, suppose that P(x) is not universally true. Consider the set {x in A | P(x) is false} and use the well-ordering property on this set.