# Well-founded relation

In mathematics, a binary relation, *R*, is called **well-founded** (or **wellfounded**) on a class *X* if every non-empty subset *S* ⊆ *X* has a minimal element with respect to *R*, that is an element *m* not related by *sRm* (for instance, "*s* is not smaller than *m*") for any *s* ∈ *S*. In other words, a relation is well founded if

Some authors include an extra condition that *R* 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 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*.^{[citation needed]}

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**, **upwards well-founded** or **Noetherian** 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. In the context of rewriting systems, a Noetherian relation is also called **terminating**.

## Induction and recursion[edit]

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, *P*(*x*) is some property of elements of *X*, and we want to show that

*P*(*x*) holds for all elements*x*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.

That is,

Well-founded induction is sometimes called Noetherian induction,^{[1]} after Emmy Noether.

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 that 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*,

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 those articles for more details.

## Examples[edit]

Well-founded relations which are not totally ordered include:

- 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 ("is an element of"). This is 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*.

Examples of relations that are not well-founded include:

- the negative integers {−1, −2, −3, …}, 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 "B" > "AB" > "AAB" > "AAAB" > … 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 rational numbers (or reals) under the standard ordering, since, for example, the set of positive rationals (or reals) lacks a minimum.

## Other properties[edit]

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 among the extensional well-founded relations: for any set-like well-founded relation *R* on a class *X* which is extensional, there exists a class *C* such that (*X*,*R*) is isomorphic to (*C*,∈).

## Reflexivity[edit]

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 . 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-founded relation is changed from the definition above to include this convention.

## References[edit]

**^**Bourbaki, N. (1972)*Elements of mathematics. Commutative algebra*, Addison-Wesley.

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