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 x0, x1, x2, ... of elements of X such that xn+1 R xn for every natural number n.
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.