Added to Favorites

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 a minimal element with respect to R; 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:
## Induction and recursion

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:
## Examples

Well-founded relations which are not totally ordered include:## Other properties

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.## Reflexivity

## References

- $forall\; S\; subseteq\; X\; (S\; neq\; varnothing\; to\; exists\; m\; in\; S,\; forall\; s\; in\; S,\; (s,\; m)\; notin\; 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_{0}, x_{1}, x_{2}, ... 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.

A relation R is converse well-founded or upwards well-founded on X, if the converse relation R^{-1} is well-founded on X. In this case R is also said to satisfy the ascending chain condition.

- 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. I.e., $forall\; x\; in\; X\; ((forall\; yin\; X\; (y,R,x\; to\; P(y)))\; to\; P(x))$.

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 pair of an element x ∈ X and a function g on the initial segment {y: y R x} of X. Then there is a unique function G such that for every x ∈ X,

- $G(x)=F(x,Gvert\_\{\{y:\; 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 those articles for more details.

- the positive integers {1, 2, 3, ...}, with the order defined by a < b if and only if a divides b and a ≠ 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 proper substring of t.
- the set N × N of pairs of natural numbers, ordered by (n
_{1}, n_{2}) < (m_{1}, m_{2}) if and only if n_{1}< m_{1}and n_{2}< m_{2}. - the set of all regular expressions over a fixed alphabet, with the order defined by s < t if and only if s is a proper subexpression of t.
- any class whose elements are sets, with the relation R defined such that a R b if and only if a is an element of b (assuming the axiom of regularity).
- the nodes of any finite directed acyclic graph, with the relation R defined such that a R b if and only if there is an edge from a to b.

Counterexamples include:

- the rational numbers under the standard ordering, since, for example, the set of positive rationals lacks a minimum.

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

A relation R is said to be reflexive if a R a holds for every a in the domain of the relation. Every reflexive relation on a nonempty domain has infinite descending chains, because any constant sequence is a descending chain. For example, in the natural numbers with their usual order ≤, we have $1\; leq\; 1\; leq\; 1\; leq\; cdots$. To avoid these trivial descending sequences, when working with a reflexive relation R it is common to use (perhaps implicitly) the alternate relation R′ defined such that a R′ b if and only if a R b and a ≠ b. In the context of the natural numbers, this means that the relation <, which is well-founded, is used instead of the relation ≤, which is not. In some texts, the definition of a well-ordered relation is changed from the definition above to include this convention.

- Just, Winfried and Weese, Martin, Discovering Modern Set theory. I, American Mathematical Society (1998) ISBN 0-8218-0266-6.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Thursday September 04, 2008 at 04:18:46 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Thursday September 04, 2008 at 04:18:46 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.