Well-founded relation

A binary relation is well-founded when every nonempty subset of its domain contains an element with no related predecessor in that subset. On sets, this is equivalent to having no infinite descending chain.

Well-founded induction: A proof method that establishes a property by showing it holds whenever it holds for all smaller elements. The minimal-element condition ensures that a counterexample would yield a smaller counterexample.
Binary relation: A relation that assigns a truth value to each ordered pair from a domain. Well-foundedness is a property of a binary relation on a specified domain.
Termination (computing): The property that a computation eventually halts rather than continuing indefinitely. A well-founded measure can prove that every step of a computation makes progress toward stopping.
Well-order: A total order in which every nonempty subset has a least element. A well-order is a total, reflexive-order setting for the minimal-element property; well-founded relations need not be total.
Well-founded recursion: A method for defining values at each element from values already defined on its predecessors. Well-foundedness guarantees recursive definitions can proceed without an infinite descent.
Partial order: A reflexive, antisymmetric, transitive relation that compares some or all pairs in a set. Many familiar well-founded relations are partial orders, though well-foundedness does not require one.
Rewrite system: A set of rules that replace expressions with other expressions. Termination of rewriting often follows from a well-founded order that decreases at every rewrite.
Total order: An order in which every pair of elements is comparable. Totality is independent of well-foundedness: a well-founded relation can leave pairs incomparable.
Descending chain condition: The condition that no infinite sequence descends strictly according to a given relation. For relations on sets, this condition characterizes well-foundedness.
Strict order: An irreflexive, transitive relation that expresses one element being strictly below another. Descending chains are commonly described using the strict form of an order.

Linked from 16 pages