Definition. Let be a non-empty set, and be a binary relation on . Then is said to be a well-founded relation if and only if every nonempty subset has an -minimal element (http://planetmath.org/RMinimalElement). When is well-founded, we also call the underlying set well-founded.
Note that is by no means required to be a total order, or even a partial order. When is a partial order, then -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 numbers ordered by division, i.e. if and only if divides , and . The -minimal elements of are the prime numbers.
is true for all the -minimal elements of
for every , if for every such that , we have , then we have
then is true for every .
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 ordered by division.
|Date of creation||2013-03-22 12:42:17|
|Last modified on||2013-03-22 12:42:17|
|Last modified by||ratboy (4018)|