well-founded set

In mathematics, a binary relation is called well-founded (or wellfounded or foundational) on a set or, more generally, a class if every non-empty subset has a minimal element with respect to ; that is, there exists an such that, for every , one does not have . In other words, a relation is well-founded if:
(\forall S \subseteq X)\; \neq \varnothing \implies (\exists m \in S) (\forall s \in S) \lnot(s \mathrel m)
Some authors include an extra condition that is set-like, i.e., that the elements less than any given element form a set.

Equivalently, assuming the axiom of dependent choice, a relation is well-founded when it contains no infinite descending chains, meaning there is no infinite sequence of elements of such that for every natural number .

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 is called a well-founded set if the set membership relation is well-founded on the transitive closure of . The axiom of regularity, which is one of the axioms of Zermelo–Fraenkel set theory, asserts that all sets are well-founded.

A relation is converse well-founded, upwards well-founded or Noetherian on , if the converse relation is well-founded on . In this case is also said to satisfy the ascending chain condition. In the context of rewriting systems, a Noetherian relation is also called terminating.

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 () is a well-founded relation, is some property of elements of , and we want to show that

: holds for all elements of ,

it suffices to show that:

: If is an element of and is true for all such that , then must also be true.

That is,
(\forall x \in X)\; \forall y \in X)\;[y\mathrelx \implies P(y)\implies P(x)">\mathrelx_\implies_P(y).html" ;"title="\forall y \in X)\;[y\mathrelx \implies P(y)">\forall y \in X)\;[y\mathrelx \implies P(y)\implies P(x)quad\text\quad(\forall x \in X)\,P(x).

Well-founded induction is sometimes called Noetherian induction, Bourbaki, N. (1972) ''Elements of mathematics. Commutative algebra'', Addison-Wesley. after Emmy Noether">Nicolas Bourbaki">Bourbaki, N. (1972) ''Elements of mathematics. Commutative algebra'', Addison-Wesley. after Emmy Noether.

On par with induction, well-founded relations also support construction of objects by transfinite recursion. Let be a binary relation#Relations over a set, set-like well-founded relation and a function that assigns an object to each pair of an element and a function on the initial segment of . Then there is a unique function such that for every ,
$G(x) = F\left(x, G\vert_\right).$

That is, if we want to construct a function on , we may define using the values of for .

As an example, consider the well-founded relation , where is the set of all natural numbers, and is the graph of the successor function . Then induction on is the usual mathematical induction, and recursion on gives primitive recursion. If we consider the order relation , we obtain complete induction, and course-of-values recursion. The statement that 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.

Examples

Well-founded relations that are not totally ordered include:
* The positive integers , with the order defined by if and only if divides and .
* The set of all finite strings over a fixed alphabet, with the order defined by if and only if is a proper substring of .
* The set of pairs of natural numbers, ordered by if and only if and .
* Every class whose elements are sets, with the relation ∈ ("is an element of"). This is the axiom of regularity.
* The nodes of any finite directed acyclic graph, with the relation defined such that if and only if there is an edge from to .
Examples of relations that are not well-founded include:
* The negative integers , with the usual order, since any unbounded subset has no least element.
* The set of strings over a finite alphabet with more than one element, under the usual (lexicographic) order, since the sequence is an infinite descending chain. This relation fails to be well-founded even though the entire set has a minimum element, namely the empty string.
* The set of non-negative rational numbers (or reals) under the standard ordering, since, for example, the subset of positive rationals (or reals) lacks a minimum.

Other properties

If is a well-founded relation and is an element of , then the descending chains starting at are all finite, but this does not mean that their lengths are necessarily bounded. Consider the following example:
Let be the union of the positive integers with a new element ω that is bigger than any integer. Then is a well-founded set, but
there are descending chains starting at ω of arbitrary great (finite) length;
the chain has length for any .

The Mostowski collapse lemma implies that set membership is a universal among the extensional well-founded relations: for any set-like well-founded relation on a class that is extensional, there exists a class such that is isomorphic to .

Reflexivity

A relation is said to be reflexive if holds for every 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 . To avoid these trivial descending sequences, when working with a partial order ≤, it is common to apply the definition of well foundedness (perhaps implicitly) to the alternate relation < defined such that if and only if and . More generally, when working with a preorder ≤, it is common to use the relation < defined such that if and only if and . 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-founded relation is changed from the definition above to include these conventions.

References

* Just, Winfried and Weese, Martin (1998) ''Discovering Modern Set Theory. I'', American Mathematical Society .
* Karel Hrbáček & Thomas Jech (1999) ''Introduction to Set Theory'', 3rd edition, "Well-founded relations", pages 251–5, Marcel Dekker

{{Order theory