well-founded induction

Definition. Let S be a non-empty set, and R be a binary relationMathworldPlanetmath on S. Then R is said to be a well-founded relation if and only if every nonempty subset XS has an R-minimal element (http://planetmath.org/RMinimalElement). When R is well-founded, we also call the underlying set S well-founded.

Note that R is by no means required to be a total orderMathworldPlanetmath, or even a partial orderMathworldPlanetmath. When R is a partial order, then R-minimality is the same as minimality (of the partial order). A classical example of a well-founded set that is not totally ordered is the set of natural numbersMathworldPlanetmath ordered by division, i.e. aRb if and only if a divides b, and a1. The R-minimal elements of are the prime numbersMathworldPlanetmath.

Let Φ be a property defined on a well-founded set S. The principle of well-founded induction states that if the following is true :

  1. 1.

    Φ is true for all the R-minimal elements of S

  2. 2.

    for every a, if for every x such that xRa, we have Φ(x), then we have Φ(a)

then Φ is true for every aS.

As an example of application of this principle, we mention the proof of the fundamental theorem of arithmeticMathworldPlanetmath : every natural number has a unique factorization into prime numbers. The proof goes by well-founded induction in the set ordered by division.

Title well-founded induction
Canonical name WellfoundedInduction
Date of creation 2013-03-22 12:42:17
Last modified on 2013-03-22 12:42:17
Owner ratboy (4018)
Last modified by ratboy (4018)
Numerical id 22
Author ratboy (4018)
Entry type TheoremMathworldPlanetmath
Classification msc 03B10
Related topic PrincipleOfFiniteInduction