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:
“I will not let him stir
Till I have used the approvèd means I have,
With wholesome syrups, drugs, and holy prayers,
To make of him a formal man again.”
—William Shakespeare (1564–1616)
“One is apt to be discouraged by the frequency with which Mr. Hardy has persuaded himself that a macabre subject is a poem in itself; that, if there be enough of death and the tomb in one’s theme, it needs no translation into art, the bold statement of it being sufficient.”
—Rebecca West (1892–1983)