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:
“Two clergymen disputing whether ordination would be valid without the imposition of both hands, the more formal one said, “Do you think the Holy Dove could fly down with only one wing?””
—Horace Walpole (1717–1797)
“Most personal correspondence of today consists of letters the first half of which are given over to an indexed statement of why the writer hasn’t written before, followed by one paragraph of small talk, with the remainder devoted to reasons why it is imperative that the letter be brought to a close.”
—Robert Benchley (1889–1945)