# 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

Transitive binary relations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

indicates that the column's property is required by the definition of the row's term (at the very left). For example, the definition of an equivalence relation requires it to be symmetric. ✗ indicates that the property may, or may not hold. All definitions tacitly require the homogeneous relation be transitive: for all if and then and there are additional properties that a homogeneous relation may satisfy. |

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*.[1][2]

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**.