Well-founded relation

Encyclopedia : W : WE : WEL : Well-founded relation

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 x₀, x₁, x₂, ... of elements of X such that x_n+1 R x_n 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,

[G(x)=F(x,G\vert_})]

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:

the positive integers , with the order defined by a ≤ b if and only if a divides b.
the set of all finite strings over a fixed alphabet, with the order defined by s ≤ t if and only if s is a substring of t
the set N × N of pairs of natural numbers, ordered by (n₁, n₂) ≤ (m₁, m₂) if and only if n₁ ≤ m₁ and n₂ ≤ m₂.
the set of all regular expressions over a fixed alphabet, with the order defined by s ≤ t if and only if s is a subexpression of t
any class whose elements are sets, with the relation defined by a R b if and only if a is an element of b (assuming the axiom of regularity).
any finite directed acyclic graph, where the relation is defined by a R b if and only if there is an edge a→b.

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,∈).

References

Just, Winfried and Weese, Martin, Discovering Modern Set theory. I, American Mathematical Society (1998) ISBN 0821802666.

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.