well-founded induction

Definition. Let $S$ be a non-empty set, and $R$ be a binary relation on $S$. Then $R$ is said to be a well-founded relation if and only if every nonempty subset $X\subseteq S$ 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 order, or even a partial order. 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 $\mathbb{N}$ of natural numbers ordered by division, i.e. $aRb$ if and only if $a$ divides $b$, and $a\ne 1$. The $R$-minimal elements of $\mathbb{N}$ are the prime numbers.

Let $\mathrm{\Phi }$ be a property defined on a well-founded set $S$. The principle of well-founded induction states that if the following is true :

1. $\mathrm{\Phi }$ is true for all the $R$-minimal elements of $S$

2. for every $a$, if for every $x$ such that $xRa$, we have $\mathrm{\Phi }(x)$, then we have $\mathrm{\Phi }(a)$

then $\mathrm{\Phi }$ is true for every $a\in S$.

As an example of application of this principle, we mention the proof of the fundamental theorem of arithmetic : every natural number has a unique factorization into prime numbers. The proof goes by well-founded induction in the set $\mathbb{N}$ 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	Theorem
Classification	msc 03B10
Related topic	PrincipleOfFiniteInduction