Well-founded set

A well-founded set is a partially ordered set which contains no infinite descending chains, or equivalently, a partially ordered set in which every non-empty subset has a minimal element. 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:

1. show that P(x) is true for all minimal elements of X
2. 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 (n₁, n₂) <= (m₁, m₂) iff n₁ ≤ m₁ and n₂ ≤ m₂.
• 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: for every positive integer n, let X_n be a totally ordered set with n elements. Let X be the disjoint union of the X_n together with a single new element x which is bigger than all other elements. Then X is a well-founded set, and there are descending chains starting at x of arbitrary (finite) length.