wellfounded induction
Definition. Let $S$ be a nonempty set, and $R$ be a binary relation^{} on $S$. Then $R$ is said to be a wellfounded relation if and only if every nonempty subset $X\subseteq S$ has an $R$minimal element (http://planetmath.org/RMinimalElement). When $R$ is wellfounded, we also call the underlying set $S$ wellfounded.
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 wellfounded 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 wellfounded set $S$. The principle of wellfounded 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 wellfounded induction in the set $\mathbb{N}$ ordered by division.
Title  wellfounded induction 

Canonical name  WellfoundedInduction 
Date of creation  20130322 12:42:17 
Last modified on  20130322 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 