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
Read more about this topic: Dickson's Lemma
Famous quotes containing the words formal and/or statement:
“The formal Washington dinner party has all the spontaneity of a Japanese imperial funeral.”
—Simon Hoggart (b. 1946)
“If we do take statements to be the primary bearers of truth, there seems to be a very simple answer to the question, what is it for them to be true: for a statement to be true is for things to be as they are stated to be.”
—J.L. (John Langshaw)