Well-founded Induction
   HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern 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 Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
''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 differentl ...
''X'' if every
non-empty In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other t ...
subset In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
''S'' ⊆ ''X'' has a
minimal element In mathematics, especially in order theory, a maximal element of a subset ''S'' of some preordered set is an element of ''S'' that is not smaller than any other element in ''S''. A minimal element of a subset ''S'' of some preordered set is defin ...
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 chain In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some Set (mathematics), set X, which satisfies the following for all a, b and c in X: # a ...
s, 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 Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article intr ...
, a
partial 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 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 r ...
is a well-founded relation. If the order is a
total order In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive) ...
then it is called a
well-order In mathematics, a well-order (or well-ordering or well-order relation) on a set ''S'' is a total order on ''S'' with the property that every non-empty subset of ''S'' has a least element in this ordering. The set ''S'' together with the well-orde ...
. In
set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly conce ...
, a set ''x'' is called a well-founded set if the set membership 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 infinite ...
of ''x''. The
axiom of regularity In mathematics, the axiom of regularity (also known as the axiom of foundation) is an axiom of Zermelo–Fraenkel set theory that states that every non-empty set ''A'' contains an element that is disjoint from ''A''. In first-order logic, the ...
, 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 ...
, 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& ...
''R''−1 is well-founded on ''X''. In this case ''R'' is also said to satisfy the
ascending chain condition In mathematics, the ascending chain condition (ACC) and descending chain condition (DCC) are finiteness properties satisfied by some algebraic structures, most importantly ideals in certain commutative rings.Jacobson (2009), p. 142 and 147 These con ...
. In the context of
rewriting In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a well-formed formula, formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewr ...
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 Transfinite induction is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers. Its correctness is a theorem of ZFC. Induction by cases Let P(\alpha) be a property defined for a ...
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 In mathematics, an upper set (also called an upward closed set, an upset, or an isotone set in ''X'') of a partially ordered set (X, \leq) is a subset S \subseteq X with the following property: if ''s'' is in ''S'' and if ''x'' in ''X'' is larger ...
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 In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''cardinal n ...
, 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 In mathematics, the well-ordering principle states that every non-empty set of positive integers contains a least element. In other words, the set of positive integers is well-ordered by its "natural" or "magnitude" order in which x precedes y i ...
. 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 n ...
, the technique is called
transfinite induction Transfinite induction is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers. Its correctness is a theorem of ZFC. Induction by cases Let P(\alpha) be a property defined for a ...
. When the well-founded set is a set of recursively-defined data structures, the technique is called
structural induction Structural induction is a proof method that is used in mathematical logic (e.g., in the proof of Łoś' theorem), computer science, graph theory, and some other mathematical fields. It is a generalization of mathematical induction over natural nu ...
. 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
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s , with the order defined by ''a'' < ''b''
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bicondi ...
''a''
divides In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
''b'' and ''a'' ≠ ''b''. * The set of all finite
strings String or strings may refer to: *String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects Arts, entertainment, and media Films * ''Strings'' (1991 film), a Canadian anim ...
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 number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''Cardinal n ...
s, 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 In mathematics, the axiom of regularity (also known as the axiom of foundation) is an axiom of Zermelo–Fraenkel set theory that states that every non-empty set ''A'' contains an element that is disjoint from ''A''. In first-order logic, the ...
. * The nodes of any finite
directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ve ...
, 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. * Theoretica ...
) 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 number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ration ...
s (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 In mathematical logic, the Mostowski collapse lemma, also known as the Shepherdson–Mostowski collapse, is a theorem of set theory introduced by and . Statement Suppose that ''R'' is a binary relation on a class ''X'' such that *''R'' is s ...
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 c ...
≤, 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 Thomas J. Jech ( cs, Tomáš Jech, ; born January 29, 1944 in Prague) is a mathematician specializing in set theory who was at Penn State for more than 25 years. Life He was educated at Charles University (his advisor was Petr Vopěnka) and from ...
(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 pu ...
{{Order theory Binary relations