Well-founded relation
Encyclopedia
In mathematics
, a binary relation
, R, is well-founded (or wellfounded) on a class
X if and only if every non-empty
subset
of X has a minimal element with respect to R; that is, for every non-empty
subset
S of X, there is an element m of S such that for every element s of S, the pair (s,m) is not in R:
(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 and only if it contains no countable infinite descending chain
s: that is, there is no infinite sequence x0, x1, x2, ... of elements of X such that xn+1 R 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
.
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
it suffices to show that:
That is,
Well-founded induction is sometimes called Noetherian induction, after Emmy Noether
.
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 pair of an element x ∈ X and a function g on the initial segment {y: y R x} of X. Then there is a unique function G such that for every x ∈ 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 those articles for more details.
Examples of relations that are not well-founded include:
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,∈).
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
. To avoid these trivial descending sequences, when working with a reflexive relation R it is common to use (perhaps implicitly) the alternate relation R′ defined such that a R′ b if and only if a R b and a ≠ b. 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 this convention.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a binary relation
Binary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
, R, is well-founded (or wellfounded) on a class
Class (set theory)
In set theory and its applications throughout mathematics, a class is a collection of sets which can be unambiguously defined by a property that all its members share. The precise definition of "class" depends on foundational context...
X if and only if every non-empty
Empty set
In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...
subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
of X has a minimal element with respect to R; that is, for every non-empty
Empty set
In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...
subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
S of X, there is an element m of S such that for every element s of S, the pair (s,m) is not in R:
(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 and only if it contains no countable infinite descending chain
Infinite descending chain
Given a set S with a partial order ≤, an infinite descending chain is a chain V that is a subset of S upon which ≤ defines a total order such that V has no least element, that is, an element m such that for all elements n in V it holds that m ≤ n.As an example, in the set of integers, the chain...
s: that is, there is no infinite sequence x0, x1, x2, ... of elements of X such that xn+1 R xn for every natural number n.
In order theory
Order theory
Order theory is a branch of mathematics which investigates our 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 introduces the field and gives some basic definitions...
, a partial order is called well-founded if the corresponding strict order is a well-founded relation. If the order is a total order
Total order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
then it is called a well-order
Well-order
In mathematics, a well-order relation on a set S is a strict total order on S with the property that every non-empty subset of S has a least element in this ordering. Equivalently, a well-ordering is a well-founded strict total order...
.
In set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
, a set x is called a well-founded set if the set membership relation is well-founded on the transitive closure
Transitive set
In set theory, a set A is transitive, if* whenever x ∈ A, and y ∈ x, then y ∈ A, or, equivalently,* whenever x ∈ A, and x is not an urelement, then x is a subset of A....
of x. The axiom of regularity
Axiom of regularity
In mathematics, the axiom of regularity is one of the axioms of Zermelo-Fraenkel set theory and was introduced by...
, 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
Ascending chain condition
The ascending chain condition and descending chain condition are finiteness properties satisfied by some algebraic structures, most importantly, ideals in certain commutative rings...
.
Induction and recursion
An important reason that well-founded relations are interesting is because a version of transfinite inductionTransfinite induction
Transfinite induction is an extension of mathematical induction to well-ordered sets, for instance to sets of ordinal numbers or cardinal numbers.- Transfinite induction :Let P be a property defined for all ordinals α...
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,
Well-founded induction is sometimes called Noetherian induction, after Emmy Noether
Emmy Noether
Amalie Emmy Noether was an influential German mathematician known for her groundbreaking contributions to abstract algebra and theoretical physics. Described by David Hilbert, Albert Einstein and others as the most important woman in the history of mathematics, she revolutionized the theories of...
.
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 pair of an element x ∈ X and a function g on the initial segment {y: y R x} of X. Then there is a unique function G such that for every x ∈ 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
Mathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...
, 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
Well-ordering principle
The "well-ordering principle" is a property of ordered sets. A set X is well ordered if every subset of X has a least element. An example of a well ordered set is the set of natural numbers. An example of set that is not well ordered is the set of integers...
.
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
Transfinite induction
Transfinite induction is an extension of mathematical induction to well-ordered sets, for instance to sets of ordinal numbers or cardinal numbers.- Transfinite induction :Let P be a property defined for all ordinals α...
. When the well-founded set is a set of recursively-defined data structures, the technique is called structural induction
Structural induction
Structural induction is a proof method that is used in mathematical logic , computer science, graph theory, and some other mathematical fields. It is a generalization of mathematical 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 which are not totally ordered include:- the positive integerIntegerThe integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s {1, 2, 3, ...}, with the order defined by a < b if and only ifIf and only ifIn logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
a dividesDivisorIn mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...
b and a ≠ b. - the set of all finite stringsString (computer science)In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
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 pairsCartesian productIn mathematics, a Cartesian product is a construction to build a new set out of a number of given sets. Each member of the Cartesian product corresponds to the selection of one element each in every one of those sets...
of natural numberNatural numberIn mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s, ordered by (n1, n2) < (m1, m2) if and only if n1 < m1 and n2 < m2. - the set of all regular expressionRegular expressionIn computing, a regular expression provides a concise and flexible means for "matching" strings of text, such as particular characters, words, or patterns of characters. Abbreviations for "regular expression" include "regex" and "regexp"...
s over a fixed alphabet, with the order defined by s < t if and only if s is a proper subexpression of t. - any class whose elements are sets, with the relation
("is an element of"). This is the axiom of regularityAxiom of regularityIn mathematics, the axiom of regularity is one of the axioms of Zermelo-Fraenkel set theory and was introduced by...
. - the nodes of any finite directed acyclic graphDirected acyclic graphIn mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...
, 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 {-1, -2, -3, …}, 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) 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 rational numberRational numberIn mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...
s (or reals) under the standard ordering, since, for example, the set 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 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
Mostowski collapse
In mathematical logic, the Mostowski collapse lemma is a statement in set theory named for Andrzej Mostowski.-Statement:Suppose that R is a binary relation on a class X such that...
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,∈).
Reflexivity
A relation R is said to be reflexiveReflexive relation
In mathematics, a reflexive relation is a binary relation on a set for which every element is related to itself, i.e., a relation ~ on S where x~x holds true for every x in S. For example, ~ could be "is equal to".-Related terms:...
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
. To avoid these trivial descending sequences, when working with a reflexive relation R it is common to use (perhaps implicitly) the alternate relation R′ defined such that a R′ b if and only if a R b and a ≠ b. 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 this convention.