Well partial order
|
|
In mathematics, a well partial order is a partial order ≤ with the property that, for any infinite sequence x1, x2, x3, ..., there must exist indices i and j with i < j and xi ≤ xj.
Stated less formally, a well partial order has no infinite sequences that have no duplicate elements and never go up. This is a generalization to partial orders of well orders, which are total orders that have no infinite sequences that always go down. For total orders these two statements are equivalent, meaning that any well order is also a well partial order, but for partial orders it may be that at many steps the sequence goes neither up nor down.
Examples
- Any total order will be a well partial order if and only if it is a well order. So the set of positive integers (with the usual ordering) is a well partial order, but the set of all integers is not, because it contains the infinite descending sequence −1, −2, −3, ... .
- Any finite set is a well partial order, because any infinite sequence drawn from the set must contain duplicates.
- Any subset of a well partial order is also a well partial order. The proof is by contraposition: If A is a subset of B, and there is an infinite sequence of distinct elements of A that never goes up, then this sequence is also an infinite sequence of elements of B that never goes up.
- The set of positive integers with ≤ defined by x ≤ y just in case x is a divisor or y is not a well partial order; the sequence of prime numbers 2, 3, 5, 7, 11, ... contains no number that is a factor of another. But the set { 1, 2, 4, 8, 16, ... } if all powers of two, with the same definition for ≤, is a well partial order (it's isomorphic to the positive integers with the usual ordering). This shows that a subset of a non-well-partial-order can be a well partial order.
- Let ≤ be a partial order on a set A. Consider the set An of all strings of n elements of A (for example, if A is the set {0, 1}, then A3 would be the set of all 3-digit binary numbers). Define a partial order ≤n on An by letting x ≤n y when xi ≤ yi for every position i. If ≤ is a well partial order, then so is ≤n. (This is a special case of Higman's lemma.)
- The set of (isomorphism classes of) graphs with ≤ defined by letting G1 ≤ G2 whenever G1 is a graph minor of G2 is a well partial order. This statement is equivalent to the Robertson-Seymour graph minor theorem, a very deep result in graph theory.
History
(not written yet)
Applications
(not written yet)