|
|
|
|
|
Well-founded RelationIn mathematics, a well-founded relation is an order relation R on a set X where every non-empty subset of X has an R-minimal element; that is, where for every non-empty subset S of X, there is an element m of S such that for every element s of S, s R m implies s = m. Note that this differs from the definition of the well-order relation, where the relation is required to be totally ordered and thus requires R-least elements instead of merely R-minimal ones. A set equipped with a well-founded relation is sometimes said to be a well-founded set. A well-founded set is a partially ordered set in which every non-empty subset has a minimal element. Equivalently, assuming some choice, it is a partially ordered set which contains no infinite descending chains. If the order is a total order then the set is called a well-ordered set. One reason that well-founded sets are interesting is because a version of transfinite induction can be used on them: if (X, <=) is a well-founded set and P(x) is some property of elements of X and you want to show that P(x) holds for all elements of X, you can proceed as follows: - show that P(x) is true for all minimal elements of X
- show that, if x is an element of X and P(y) is true for all y <= x with y ≠ x, then P(x) must also be true.
Examples of well-founded sets which are not totally ordered are: - the positive integers {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 numbers, ordered by (n1, n2) <= (m1, m2) iff n1 ≤ m1 and n2 ≤ m2.
- the set of all regular expressions over a fixed alphabet, with the order defined by s <= t iff s is a subexpression of t
- any set whose elements are sets, with the order defined by A <= B iff A is an element of B.
If (X, ≤) is a well-founded set 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. A familiar example of a well-founded relation is the ordinary < relation on the set of natural numbers N. Every non-empty subset of the natural numbers contains a smallest element. This is known as the well-ordering principle. Well-foundedness is interesting because the powerful technique of induction can be used to prove things about members of well-founded sets. For the example of the natural numbers above, this technique is called mathematical induction. When the well-founded set is the set of all ordinal numbers, and the well-founded relation is set membership, 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. See the articles under those heads for more details.
|
 |
| |
|
|