In mathematics, a

**well-founded relation**is an order relation

*R*on a set

*X*where every nonempty subset of

*X*has an

*R*-minimal element; that is, where for every subset

*S*of

*X*, there is an element

*m*of

*S*such that for every element

*s*of

*S*,

*s R m*is

*not*true.

Note that this differs from the definition of the well-order relation, where we do not require an R-minimal element but R-least element instead.

A set equipped with a well-founded relation is sometimes said to be a **well-founded set**. A well-founded set is a partially ordered set which contains no infinite descending chains, or equivalently, a partially ordered set in which every non-empty subset has a minimal element. If the order is a total order then the set is called a well-ordered set.

One reason that well-founded sets are interesting is because a version of transfinite induction can be used on them: if (*X*, <=) is a well-founded set and P(*x*) is some property of elements of *X* and you want to show that P(*x*) holds *for all* elements of *X*, you can proceed as follows:

- show that P(
*x*) is true for all minimal elements of*X* - show that, if
*x*is an element of*X*and P(*y*) is true for all*y*<=*x*with*y*≠*x*, then P(*x*) must also be true.

- the positive integers {1, 2, 3, ...}, with the order defined by
*a*<=*b*iff*a*divides*b*. - the set of all finite strings over a fixed alphabet, with the order defined by
*s*<=*t*iff*s*is a substring of*t* - the set
**N**×**N**of pairs of natural numbers, ordered by (*n*_{1},*n*_{2}) <= (*m*_{1},*m*_{2}) iff*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*iff*s*is a subexpression of*t* - any set whose elements are sets, with the order defined by
*A*<=*B*iff*A*is an element of*B*.

*X*, ≤) is a well-founded set 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*.

A familiar example of a well-founded relation is the ordinary < relation on the set of natural numbers **N**. Every non-empty subset of the natural numbers contains a smallest element. This is known as the well-ordering principle.

Well-foundedness is interesting because the powerful technique of induction can be used to prove things about members of well-founded sets. For the example of the natural numbers above, this technique is called mathematical induction. When the well-founded set is the set of all ordinal numbers, and the well-founded relation is set membership, 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. See the articles under those heads for more details.