Well partial order

In mathematics, a well partial order is a partial order ≤ with the property that, for any infinite sequence x₁, x₂, x₃..., there must exist distinct indices i and j with x_i ≤ x_j.

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.

Table of contents

1 Examples 2 History 3 Applications

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 infinfinite 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 factor 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 Aⁿ of all strings of n elements of A (for example, if A is the set {0,1}, then A³ would be the set of all 3-digit binary numbers). Define a partial order ≤ⁿ on Aⁿ by letting x ≤ⁿ y when x_i ≤ y_i for every position i. If ≤ is a well partial order, then so is ≤ⁿ. (This is a special case of Higman's lemma.)
• The set of graphs with ≤ defined by letting G₁ ≤ G₂ whenever G₁ is a graph minor of G₂ is a well partial order. This is the core of the Robertson-Seymour graph minor theorem, a very deep result in graph theory.

History

(not written yet)

Applications

(not written yet)