|
In mathematics, a binary relation, R, is well-founded (or wellfounded) on a class X if and only if every non-empty subset of X has an R-minimal element; that is, for every non-empty subset S of X, there is an element m of S such that for every element s of S, the pair (s,m) is not in R. Equivalently, assuming some choice, a relation is well-founded if and only if it contains no countable infinite descending chains: that is, there is no infinite sequence x0, x1, x2, ... of elements of X such that xn+1 R xn for every natural number n. In order theory, a partial order is called well-founded if the corresponding strict order is a well-founded relation. If the order is a total order then it is called a well-order. In set theory, a set x is called a well-founded set if the set membership relation is well-founded on the transitive closure of x. The axiom of regularity, which is one of the axioms of Zermelo-Fraenkel set theory, asserts that all sets are well-founded. An important reason that well-founded relations are interesting is because a version of transfinite induction can be used on them: if (X, R) is a well-founded relation and P(x) is some property of elements of X and you want to show that P(x) holds for all elements of X, it suffices to show that: If x is an element of X and P(y) is true for all y such that y R x, then P(x) must also be true. On par with induction, well-founded relations also support construction of objects by transfinite recursion. Let (X, R) be a set-like well-founded relation, and F a function, which assigns an object F(x, g) to each x ∈ X and each partial function g on X. Then there is a unique function G such that for every x ∈ X, That is, if we want to construct a function G on X, we may define G(x) using the values of G(y) for y R x. As an example, consider the well-founded relation (N, S), where N is the set of all natural numbers, and S is the graph of the successor function x → x+1. Then induction on S is the usual mathematical induction, and recursion on S gives primitive recursion. If we consider the order relation (N, <), we obtain complete induction, and course-of-values recursion. The statement that (N, <) is well-founded is also known as the well-ordering principle. There are other interesting special cases of well-founded induction. When the well-founded relation is the usual ordering on the class of all ordinal numbers, the technique is called transfinite induction. When the well-founded set is a set of recursively-defined data structures, the technique is called structural induction. When the well-founded relation is set membership on the universal class, the technique is known as ∈-induction. See the articles under those heads for more details. Examples of well-founded relations which are not totally ordered are: If (X, <) is a well-founded relation and x is an element of X, then the descending chains starting at x are all finite, but this does not mean that their lengths are necessarily bounded. Consider the following example: Let X be the union of the positive integers and a new element ω, which is bigger than any integer. Then X is a well-founded set, but there are descending chains starting at ω of arbitrary great (finite) length; the chain ω, n-1, n-2, ..., 2, 1 has length n for any n. The Mostowski collapse lemma implies that set membership is a universal well-founded relation: for any set-like well-founded relation R on a class X, there exists a class C such that (X,R) is isomorphic to (C,∈).
| ||||||||
|
| |||||||||
 |
|
| |