Encyclopedia > Well-founded set

  Article Content

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 yx, 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 n1m1 and n2m2.
  • 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 Xn be a totally ordered set with n elements. Let X be the disjoint union of the Xn 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.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Michael Barrymore

... Barrymore Michael Barrymore, born 4 May 1952, is a British comedian famous for his variety shows. This article is a stub. You can help Wikipedia by fixing ...

 
 
 
This page was created in 24.3 ms