Well-founded relation

An important reason that well-founded relations are interesting is because a version of transfinite induction can be used on them: if ({{math|X, R}}) is a well-founded relation, {{math|P(x)}} is some property of elements of {{mvar|X}}, and we want to show that

:{{math|P(x)}} holds for all elements {{mvar|x}} of {{mvar|X}},

it suffices to show that:

: If {{mvar|x}} is an element of {{mvar|X}} and {{math|P(y)}} is true for all {{mvar|y}} such that {{math|y R x}}, then {{math|P(x)}} must also be true.

That is,

$$(\backslash forall\; x\; \backslash in\; X)\backslash ;[(\backslash forall\; y\; \backslash in\; X)\backslash ;[y\backslash mathrel\{R\}x\; \backslash implies\; P(y)]\; \backslash implies\; P(x)]\backslash quad\backslash text\{implies\}\backslash quad(\backslash forall\; x\; \backslash in\; X)\backslash ,P(x).$$

Well-founded induction is sometimes called Noetherian induction,Bourbaki, N. (1972) Elements of mathematics. Commutative algebra, Addison-Wesley. after Emmy Noether.

On par with induction, well-founded relations also support construction of objects by transfinite recursion. Let {{math|(X, R)}} be a set-like well-founded relation and {{mvar|F}} a function that assigns an object {{math|F(x, g)}} to each pair of an element {{math|x ∈ X}} and a function {{mvar|g}} on the initial segment {{math|{{(}}y: y R x{{)}}}} of {{mvar|X}}. Then there is a unique function {{mvar|G}} such that for every {{math|x ∈ X}},

$$G(x)\; =\; F\backslash left(x,\; G\backslash vert\_\{\backslash left\backslash \{y:\backslash ,\; y\backslash mathrel\{R\}x\backslash right\backslash \}\}\backslash right).$$

That is, if we want to construct a function {{mvar|G}} on {{mvar|X}}, we may define {{math|G(x)}} using the values of {{math|G(y)}} for {{math|y R x}}.

As an example, consider the well-founded relation {{math|(N, S)}}, where {{math|N}} is the set of all natural numbers, and {{mvar|S}} is the graph of the successor function {{math|x ↦ x+1}}. Then induction on {{mvar|S}} is the usual mathematical induction, and recursion on {{mvar|S}} gives primitive recursion. If we consider the order relation {{math|(N, <)}}, we obtain complete induction, and course-of-values recursion. The statement that {{math|(N, <)}} is well-founded is also known as the well-ordering principle.

There are other interesting special cases of well-founded induction. When the well-founded relation is the usual ordering on the class of all ordinal numbers, 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. When the well-founded relation is set membership on the universal class, the technique is known as ∈-induction. See those articles for more details.

Well-founded relations that are not totally ordered include:

• The positive integers {{math|{{(}}1, 2, 3, ...{{)}}}}, with the order defined by {{math|a < b}} if and only if {{mvar|a}} divides {{mvar|b}} and {{math|a ≠ b}}.
• The set of all finite strings over a fixed alphabet, with the order defined by {{math|s < t}} if and only if {{mvar|s}} is a proper substring of {{mvar|t}}.
• The set {{math|N × N}} of pairs of natural numbers, ordered by {{math|(n₁, n₂) < (m₁, m₂)}} if and only if {{math|n₁ < m₁}} and {{math|n₂ < m₂}}.
• Every class whose elements are sets, with the relation ∈ ("is an element of"). This is the axiom of regularity.
• The nodes of any finite directed acyclic graph, with the relation {{mvar|R}} defined such that {{math|a R b}} if and only if there is an edge from {{mvar|a}} to {{mvar|b}}.

Examples of relations that are not well-founded include:

• The negative integers {{math|{{(}}−1, −2, −3, ...{{)}}}}, with the usual order, since any unbounded subset has no least element.
• The set of strings over a finite alphabet with more than one element, under the usual (lexicographic) order, since the sequence {{nowrap|"B" > "AB" > "AAB" > "AAAB" > ...}} is an infinite descending chain. This relation fails to be well-founded even though the entire set has a minimum element, namely the empty string.
• The set of non-negative rational numbers (or reals) under the standard ordering, since, for example, the subset of positive rationals (or reals) lacks a minimum.

If {{math|(X, <)}} is a well-founded relation and {{mvar|x}} is an element of {{mvar|X}}, then the descending chains starting at {{mvar|x}} are all finite, but this does not mean that their lengths are necessarily bounded. Consider the following example:

Let {{mvar|X}} be the union of the positive integers with a new element ω that is bigger than any integer. Then {{mvar|X}} is a well-founded set, but

there are descending chains starting at ω of arbitrary great (finite) length;

the chain {{math|ω, n − 1, n − 2, ..., 2, 1}} has length {{mvar|n}} for any {{mvar|n}}.

The Mostowski collapse lemma implies that set membership is a universal among the extensional well-founded relations: for any set-like well-founded relation {{mvar|R}} on a class {{mvar|X}} that is extensional, there exists a class {{mvar|C}} such that {{math|(X, R)}} is isomorphic to {{math|(C, ∈)}}.

A relation {{mvar|R}} is said to be reflexive if {{math|a R a}} holds for every {{mvar|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 {{nowrap|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 {{math|a < b}} if and only if {{math|a ≤ b}} and {{math|a ≠ b}}. More generally, when working with a preorder ≤, it is common to use the relation < defined such that {{math|a < b}} if and only if {{math|a ≤ b}} and {{math|b ≰ a}}. In the context of the natural numbers, this means that the relation <, which is well-founded, is used instead of the relation ≤, which is not. In some texts, the definition of a well-founded relation is changed from the definition above to include these conventions.

{{reflist}}

• Just, Winfried and Weese, Martin (1998) Discovering Modern Set Theory. I, American Mathematical Society {{isbn|0-8218-0266-6}}.
• Karel Hrbáček & Thomas Jech (1999) Introduction to Set Theory, 3rd edition, "Well-founded relations", pages 251–5, Marcel Dekker {{ISBN|0-8247-7915-0}}

{{Mathematical logic}}

{{Order theory}}