Dickson's Lemma - Formal Statement

Formal Statement

Let be the set of non-negative integers (natural numbers), let n be any fixed constant, and let be the set of -tuples of natural numbers. These tuples may be given a pointwise partial order, the product order, in which if and only if, for every, . The set of tuples that are greater than or equal to some particular tuple forms a positive orthant with its apex at the given tuple.

With this notation, Dickson's lemma may be stated in several equivalent forms:

• In every subset of, there are finitely many elements that are minimal elements of for the pointwise partial order
• In every infinite set of -tuples of natural numbers, there exist two tuples and such that, for every, .
• The partially ordered set is a well partial order.
• Every subset of may be covered by a finite set of positive orthants, whose apexes all belong to