Well-founded Relation

Equivalently, assuming some Choice , a relation is well-founded iff it contains no Infinite Descending Chain s: that is, there is no infinite sequence ''x''₀, ''x''₁, ''x''₂, ... of elements of ''X'' such that ''x''_''n''+1 ''R'' ''x''_n 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 well-founded 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.

An important reason that well-founded relations are interesting is because a version of Transfinite Induction can be used on them: if (''X'', ''R'') is a well-founded relation and P(''x'') is some property of elements of ''X'' and you want to show that P(''x'') holds ''for all'' elements of ''X'', it suffices to show that:
: If ''x'' is an element of ''X'' and P(''y'') is true for all ''y'' such that ''y R x'', then P(''x'') must also be true.

On par with induction, well-founded relations also support construction of objects by Transfinite Recursion . Let (''X'', ''R'') be a Set-like well-founded relation, and ''F'' a function, which assigns an object ''F''(''x'', ''g'') to each ''x ∈ X'' and each partial function ''g'' on ''X''. Then there is a unique function ''G'' such that for every ''x ∈ X'',
:

G(x)=F(x,Gert_{\{y: y\,R\,x\}})

That is, if we want to construct a function ''G'' on ''X'', we may define ''G''(''x'') using the values of ''G''(''y'') for ''y R x''.

As an example, consider the well-founded relation (N, ''S''), where N is the set of all Natural Numbers , and ''S'' is the graph of the successor function ''x'' → ''x''+1. Then induction on ''S'' is the usual Mathematical Induction , and recursion on ''S'' gives Primitive Recursion . If we consider the order relation (N, <), we obtain Complete Induction , and Course-of-values Recursion . The statement that (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 the articles under those heads for more details.

Examples of well-founded relations which are not totally ordered are:

the positive Integer s {1, 2, 3, ...}, with the order defined by ''a'' ≤ ''b'' Iff ''a'' Divides ''b''.

the set of all finite Strings over a fixed alphabet, with the order defined by ''s'' ≤ ''t'' iff ''s'' is a substring of ''t''

the set N × N of Pairs of Natural Number s, ordered by (''n''₁, ''n''₂) ≤ (''m''₁, ''m''₂) iff ''n''₁ ≤ ''m''₁ and ''n''₂ ≤ ''m''₂.

the set of all Regular Expression s over a fixed alphabet, with the order defined by ''s'' ≤ ''t'' iff ''s'' is a subexpression of ''t''

any class whose elements are sets, with the relation defined by ''a R b'' iff ''a'' is an element of ''b'' (assuming the Axiom Of Regularity ).

any finite Directed Acyclic Graph , where the relation is defined by ''a R b'' iff there is an edge ''a''→''b''.

If (''X'', <) is a well-founded relation and ''x'' is an element of ''X'', then the descending chains starting at ''x'' are all finite, but this does not mean that their lengths are necessarily bounded. Consider the following example:
Let ''X'' be the union of the positive integers and a new element ω, which is bigger than any integer. Then ''X'' is a well-founded set, but
there are descending chains starting at ω of arbitrary great (finite) length;
the chain ω, ''n''-1, ''n''-2, ..., 2, 1 has length ''n'' for any ''n''.

The Mostowski Collapse Lemma implies that set membership is a universal well-founded relation: for any set-like well-founded relation ''R'' on a class ''X'', there exists a class ''C'' such that (''X'',''R'') is isomorphic to (''C'',∈).

Information About

Well-founded Relation