Well-founded relation

{{Short description|Type of binary relation}} {{Redirect|Noetherian induction|the use in topology|Noetherian topological space}} {{stack|{{Binary relations}}}}

In [[mathematics]], a [[binary relation]] {{mvar|R}} is called '''well-founded''' (or '''wellfounded''' or '''foundational''')<ref>See Definition 6.21 in {{cite book|last1=Zaring W.M.|first1= G. Takeuti|title=Introduction to axiomatic set theory|date=1971|publisher=Springer-Verlag|location=New York|isbn=0387900241|edition=2nd, rev.}}</ref> on a [[set (mathematics)|set]] or, more generally, a [[Class (set theory)|class]] {{mvar|X}} if every [[non-empty]] [[subset]] (or subclass) {{math|''S'' ⊆ ''X''}} has a [[minimal element]] with respect to {{mvar|R}}; that is, there exists an {{math|''m'' ∈ ''S''}} such that for every {{math|''s'' ∈ ''S''}}, one does not have {{math|''s'' ''R'' ''m''}}. More formally, a relation is well-founded if: <math display=block>(\forall S \subseteq X)\; [S \neq \varnothing \implies (\exists m \in S) (\forall s \in S) \lnot(s \mathrel{R} m)].</math> Some authors include an extra condition that {{mvar|R}} is [[Set-like relation|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 when it contains no [[infinite descending chain]]s, meaning there is no infinite sequence {{math|''x''0, ''x''1, ''x''2, ...}} of elements of {{mvar|X}} such that {{math|''x''''n''+1 ''R'' ''x''''n''}} for every natural number {{mvar|n}}.<ref>{{cite web |title=Infinite Sequence Property of Strictly Well-Founded Relation |url=https://proofwiki.org/wiki/Infinite_Sequence_Property_of_Strictly_Well-Founded_Relation |website=ProofWiki |access-date=10 May 2021}}</ref><ref>{{cite book |last1=Fraisse |first1=R. |author1-link=Roland Fraïssé |title=Theory of Relations, Volume 145 - 1st Edition |date=15 December 2000 |publisher=Elsevier |isbn=9780444505422 |page=46 |edition=1st |url=https://www.elsevier.com/books/theory-of-relations/fraisse/978-0-444-50542-2 |access-date=20 February 2019}}</ref>

In [[order theory]], a [[partial order]] is called well-founded if the corresponding [[strict order]] is a well-founded relation. If the order is a [[total order]], then it is called a [[well-order]].

In [[set theory]], a set {{mvar|x}} is called a '''well-founded set''' if the [[element (mathematics)|set membership]] relation is well-founded on the [[Transitive closure (set)|transitive closure]] of {{mvar|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 {{mvar|R}} is '''converse well-founded''', '''upwards well-founded''', or '''Noetherian''' on {{mvar|X}}, if the [[converse relation]] {{math|''R''−1}} is well-founded on {{mvar|X}}. In this case {{mvar|R}} is also said to satisfy the [[ascending chain condition]]. In the context of [[rewriting]] systems, a Noetherian relation is also called '''terminating'''.

==Induction and recursion==

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, <math display=block>(\forall x \in X)\;[(\forall y \in X)\;[y\mathrel{R}x \implies P(y)] \implies P(x)]\quad\text{implies}\quad(\forall x \in X)\,P(x).</math>

Well-founded induction is sometimes called Noetherian induction,<ref>[[Nicolas Bourbaki|Bourbaki, N.]] (1972) ''Elements of mathematics. Commutative algebra'', Addison-Wesley.</ref> after [[Emmy Noether]].

On par with induction, well-founded relations also support construction of objects by [[transfinite recursion]]. Let {{math|(''X'', ''R'')}} be a [[binary relation#Relations over a set|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 set {{math|{{(}}''y'': ''y'' ''R'' ''x''{{)}}}} of predecessors of {{mvar|x}}. Then there is a unique function {{mvar|G}} such that for every {{math|''x'' ∈ ''X''}}, <math display=block>G(x) = F\left(x, G\vert_{\left\{y:\, y\mathrel{R}x\right\}}\right).</math>

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 recursive functions|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.

==Examples==

Well-founded relations that are not totally ordered include: * The positive [[integer]]s {{math|{{(}}1, 2, 3, ...{{)}}}}, with the order defined by {{math|''a'' < ''b''}} [[if and only if]] {{mvar|a}} [[divisor|divides]] {{mvar|b}} and {{math|''a'' ≠ ''b''}}. * The set of all finite [[string (computer science)|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 [[Cartesian product|pairs]] of [[natural number]]s, ordered by {{math|(''n''1, ''n''2) < (''m''1, ''m''2)}} if and only if {{math|''n''1 < ''m''1}} and {{math|''n''2 < ''m''2}}. * 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 ordering|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 number]]s (or [[real numbers|reals]]) under the standard ordering, since, for example, the subset of positive rationals (or reals) lacks a minimum.

==Other properties==

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|Mostowski collapse lemma]] implies that set membership is a universal among the [[Extensionality#In_mathematics|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'', ∈)}}.

==Reflexivity==

A relation {{mvar|R}} is said to be [[reflexive relation|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.

==References==

* 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}}

== Further reading == *https://ncatlab.org/nlab/show/well-founded+coalgebra

[[Category:Wellfoundedness| ]]