Editing Well-founded relation (section)

==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''<sub>1</sub>, ''n''<sub>2</sub>) < (''m''<sub>1</sub>, ''m''<sub>2</sub>)}} if and only if {{math|''n''<sub>1</sub> < ''m''<sub>1</sub>}} and {{math|''n''<sub>2</sub> < ''m''<sub>2</sub>}}.
* 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.