*** Welcome to piglix ***

Well-founded relation


In mathematics, a binary relation, R, is well-founded (or wellfounded) on a class X if and only if every non-empty subset SX has a minimal element; that is, some element m not related by sRm (for instance, "m is not smaller than") for any sS.

(Some authors include an extra condition that R is set-like, i.e., that the elements less than any given element form a set.)

Equivalently, assuming some choice, a relation is well-founded if it contains no countable infinite descending chains: that is, there is no infinite sequence x0, x1, x2, ... of elements of X such that xn+1R xn for every natural number n.

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 x is called a well-founded set if the set membership relation is well-founded on the transitive closure of 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 R is converse well-founded, upwards well-founded or Noetherian on X, if the converse relation R−1 is well-founded on X. In this case R is also said to satisfy the ascending chain condition. In the context of rewriting systems, a Noetherian relation is also called terminating.


...
Wikipedia

...