Editing Well-founded relation (section)

{{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]] {{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''}}. In other words, 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''<sub>0</sub>, ''x''<sub>1</sub>, ''x''<sub>2</sub>, ...}} of elements of {{mvar|X}} such that {{math|''x''<sub>''n''+1</sub> ''R'' ''x''<sub>''n''</sub>}} 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''<sup>−1</sup>}} 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'''.