HOME

TheInfoList



OR:

In mathematics, a
binary relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and i ...
''R'' is called well-founded (or wellfounded) on a
class Class or The Class may refer to: Common uses not otherwise categorized * Class (biology), a taxonomic rank * Class (knowledge representation), a collection of individuals or objects * Class (philosophy), an analytical concept used differently ...
''X'' if every non-empty subset ''S'' ⊆ ''X'' has a minimal element with respect to ''R'', that is, an element ''m'' not related by ''s R m'' (for instance, "''s'' is not smaller than ''m''") for any ''s'' ∈ ''S''. In other words, a relation is well founded if :(\forall S \subseteq X)\; \neq \emptyset \implies (\exists m \in S) (\forall s \in S) \lnot(s \mathrel m) 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 the
axiom of dependent choice In mathematics, the axiom of dependent choice, denoted by \mathsf , is a weak form of the axiom of choice ( \mathsf ) that is still sufficient to develop most of real analysis. It was introduced by Paul Bernays in a 1942 article that explores whi ...
, a relation is well-founded when it contains no infinite descending chains, which can be proved when there is no infinite sequence ''x''0, ''x''1, ''x''2, ... 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 In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
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 In mathematics, an element (or member) of a set is any one of the distinct objects that belong to that set. Sets Writing A = \ means that the elements of the set are the numbers 1, 2, 3 and 4. Sets of elements of , for example \, are subset ...
relation is well-founded on the
transitive closure In mathematics, the transitive closure of a binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinit ...
of ''x''. The axiom of regularity, which is one of the axioms of
Zermelo–Fraenkel set theory In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such a ...
, 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 In mathematics, the converse relation, or transpose, of a binary relation is the relation that occurs when the order of the elements is switched in the relation. For example, the converse of the relation 'child of' is the relation 'parent&n ...
''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 In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewrite engines, or redu ...
systems, a Noetherian relation is also called terminating.


Induction and recursion

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, ''P''(''x'') is some property of elements of ''X'', and we want to show that :''P''(''x'') holds for all elements ''x'' 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. That is, :(\forall x \in X)\; \forall_y_\in_X)\;[y\mathrelx_\implies_P(y)\implies_P(x).html" ;"title="\mathrelx_\implies_P(y).html" ;"title="\forall y \in X)\;[y\mathrelx \implies P(y)">\forall y \in X)\;[y\mathrelx \implies P(y)\implies P(x)">\mathrelx_\implies_P(y).html" ;"title="\forall y \in X)\;[y\mathrelx \implies P(y)">\forall y \in X)\;[y\mathrelx \implies P(y)\implies P(x)quad\text\quad(\forall x \in X)\,P(x). Well-founded induction is sometimes called Noetherian induction,Bourbaki, N. (1972) ''Elements of mathematics. Commutative algebra'', Addison-Wesley. after Emmy Noether. On par with induction, well-founded relations also support construction of objects by transfinite recursion. Let (''X'', ''R'') be a binary relation#Relations over a set, set-like well-founded relation and ''F'' a function that assigns an object ''F''(''x'', ''g'') to each pair of an element ''x'' ∈ ''X'' and a function ''g'' on the initial segment of ''X''. Then there is a unique function ''G'' such that for every ''x'' ∈ ''X'', :G(x) = F\left(x, G\vert_\right). 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 Mathematical induction is a method for proving that a statement ''P''(''n'') is true for every natural number ''n'', that is, that the infinitely many cases ''P''(0), ''P''(1), ''P''(2), ''P''(3), ...  all hold. Informal metaphors help ...
, and recursion on ''S'' gives
primitive recursion In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined ...
. If we consider the order relation (N, <), we obtain
complete induction Mathematical induction is a method for proving that a statement ''P''(''n'') is true for every natural number ''n'', that is, that the infinitely many cases ''P''(0), ''P''(1), ''P''(2), ''P''(3), ...  all hold. Informal metaphors help ...
, and
course-of-values recursion In computability theory, course-of-values recursion is a technique for defining number-theoretic functions by recursion. In a definition of a function ''f'' by course-of-values recursion, the value of ''f''(''n'') is computed from the sequence \lan ...
. 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 In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, th, etc.) aimed to extend enumeration to infinite sets. A finite set can be enumerated by successively labeling each element with the least ...
, 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 those articles for more details.


Examples

Well-founded relations that are not totally ordered include: * The positive integers , with the order defined by ''a'' < ''b'' if and only if ''a'' divides ''b'' and ''a'' ≠ ''b''. * The set of all finite strings over a fixed alphabet, with the order defined by ''s'' < ''t'' if and only if ''s'' is a proper substring of ''t''. * The set N × N of
pairs Concentration, also known as Memory, Shinkei-suijaku (Japanese meaning "nervous breakdown"), Matching Pairs, Match Match, Match Up, Pelmanism, Pexeso or simply Pairs, is a card game in which all of the cards are laid face down on a surface and tw ...
of natural numbers, ordered by (''n''1, ''n''2) < (''m''1, ''m''2) if and only if ''n''1 < ''m''1 and ''n''2 < ''m''2. * Every class whose elements are sets, with the relation \in ("is an element of"). This is the axiom of regularity. * The nodes of any finite directed acyclic graph, with the relation ''R'' defined such that ''a R b'' if and only if there is an edge from ''a'' to ''b''. Examples of relations that are not well-founded include: * The negative integers , 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 Lexicography is the study of lexicons, and is divided into two separate academic disciplines. It is the art of compiling dictionaries. * Practical lexicography is the art or craft of compiling, writing and editing dictionaries. * Theoretic ...
) order, since the sequence "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 numbers (or reals) under the standard ordering, since, for example, the subset of positive rationals (or reals) lacks a minimum.


Other properties

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 with a new element ω that 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 among the extensional well-founded relations: for any set-like well-founded relation ''R'' on a class ''X'' that is extensional, there exists a class ''C'' such that (''X'', ''R'') is isomorphic to (''C'', ∈).


Reflexivity

A relation ''R'' is said to be reflexive if ''a'' ''R'' ''a'' holds for every ''a'' in the domain of the relation. Every reflexive relation on a nonempty domain has infinite descending chains, because any constant sequence is a descending chain. For example, in the natural numbers with their usual order ≤, we have 1 \geq 1 \geq 1 \geq \cdots. To avoid these trivial descending sequences, when working with a partial order ≤, it is common to apply the definition of well foundedness (perhaps implicitly) to the alternate relation < defined such that ''a'' < ''b'' if and only if ''a'' ≤ ''b'' and ''a'' ≠ ''b''. More generally, when working with a
preorder In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special ca ...
≤, it is common to use the relation < defined such that ''a'' < ''b'' if and only if ''a'' ≤ ''b'' and ''b'' ≰  ''a''. In the context of the natural numbers, this means that the relation <, which is well-founded, is used instead of the relation ≤, which is not. In some texts, the definition of a well-founded relation is changed from the definition above to include these conventions.


References

* Just, Winfried and Weese, Martin (1998) ''Discovering Modern Set Theory. I'',
American Mathematical Society The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings, ...
. * Karel Hrbáček & Thomas Jech (1999) ''Introduction to Set Theory'', 3rd edition, "Well-founded relations", pages 251–5,
Marcel Dekker Marcel Dekker was a journal and encyclopedia publishing company with editorial boards found in New York City. Dekker encyclopedias are now published by CRC Press, part of the Taylor and Francis publishing group. History Initially a textbook p ...
{{Order theory Binary relations