Transitive binary relations  

 
indicates that the column's property is always true the row's term (at the very left), while ✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively. All definitions tacitly require the homogeneous relation be transitive: for all if and then 
In mathematics, a binary relation R is called wellfounded (or wellfounded or foundational^{[1]}) on a set or, more generally, a class X if every nonempty subset S ⊆ X has a minimal element with respect to R; that is, there exists an m ∈ S such that, for every s ∈ S, one does not have s R m. In other words, a relation is well founded if: Some authors include an extra condition that R is setlike, i.e., that the elements less than any given element form a set.
Equivalently, assuming the axiom of dependent choice, a relation is wellfounded when it contains no infinite descending chains, which can be proved when 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.^{[2]}^{[3]}
In order theory, a partial order is called wellfounded if the corresponding strict order is a wellfounded relation. If the order is a total order then it is called a wellorder.
In set theory, a set x is called a wellfounded set if the set membership relation is wellfounded 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 wellfounded.
A relation R is converse wellfounded, upwards wellfounded or Noetherian on X, if the converse relation R^{−1} is wellfounded 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.
An important reason that wellfounded relations are interesting is because a version of transfinite induction can be used on them: if (X, R) is a wellfounded relation, P(x) is some property of elements of X, and we want to show that
it suffices to show that:
That is,
Wellfounded induction is sometimes called Noetherian induction,^{[4]} after Emmy Noether.
On par with induction, wellfounded relations also support construction of objects by transfinite recursion. Let (X, R) be a setlike wellfounded 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 wellfounded 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 courseofvalues recursion. The statement that (N, <) is wellfounded is also known as the wellordering principle.
There are other interesting special cases of wellfounded induction. When the wellfounded relation is the usual ordering on the class of all ordinal numbers, the technique is called transfinite induction. When the wellfounded set is a set of recursivelydefined data structures, the technique is called structural induction. When the wellfounded relation is set membership on the universal class, the technique is known as ∈induction. See those articles for more details.
Wellfounded relations that are not totally ordered include:
Examples of relations that are not wellfounded include:
If (X, <) is a wellfounded 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 with a new element ω that is bigger than any integer. Then X is a wellfounded 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 wellfounded relations: for any setlike wellfounded relation R on a class X that is extensional, 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 ≥ 1 ≥ 1 ≥ .... 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 a < b if and only if a ≤ b and a ≠ b. More generally, when working with a preorder ≤, it is common to use the relation < defined such that a < b if and only if a ≤ b and b ≰ a. In the context of the natural numbers, this means that the relation <, which is wellfounded, is used instead of the relation ≤, which is not. In some texts, the definition of a wellfounded relation is changed from the definition above to include these conventions.
General  

Theorems (list) and paradoxes  
Logics 
 
Set theory 
 
Formal systems (list), language and syntax 
 
Proof theory  
Model theory  
Computability theory  
Related  
Key concepts  

Results  
Properties & Types (list) 

Constructions  
Topology & Orders  
Related 