Well-founded relation

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.

Examples of well-founded sets which are not totally ordered are:

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₁, n₂) <= (m₁, m₂) iff n₁ ≤ m₁ and n₂ ≤ m₂.
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.

If (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.