In mathematics, Dickson's lemma states that every set of formula_1-tuples of natural numbers has finitely many minimal elements. This simple fact from combinatorics has become attributed to the American algebraist L. E. Dickson, who used it to prove a result in number theory about perfect numbers. However, the lemma was certainly known earlier, for example to Paul Gordan in his research on invariant theory.
Example.
Let formula_2 be a fixed natural number, and let formula_3 be the set of pairs of numbers whose product is at least formula_2. When defined over the positive real numbers, formula_5 has infinitely many minimal elements of the form formula_6, one for each positive number formula_7; this set of points forms one of the branches of a hyperbola. The pairs on this hyperbola are minimal, because it is not possible for a different pair that belongs to formula_5 to be less than or equal to formula_6 in both of its coordinates. However, Dickson's lemma concerns only tuples of natural numbers, and over the natural numbers there are only finitely many minimal pairs. Every minimal pair formula_10 of natural numbers has formula_11 and formula_12, for if "x" were greater than "K" then ("x" − 1, "y") would also belong to "S", contradicting the minimality of ("x", "y"), and symmetrically if "y" were greater than "K" then ("x", "y" − 1) would also belong to "S". Therefore, over the natural numbers, formula_5 has at most formula_14 minimal elements, a finite number.
Formal statement.
Let formula_15 be the set of non-negative integers (natural numbers), let "n" be any fixed constant, and let formula_16 be the set of formula_1-tuples of natural numbers. These tuples may be given a pointwise partial order, the product order, in which formula_18 if and only if formula_19 for every formula_20.
The set of tuples that are greater than or equal to some particular tuple formula_21 forms a positive orthant with its apex at the given tuple.
With this notation, Dickson's lemma may be stated in several equivalent forms:
Generalizations and applications.
Dickson used his lemma to prove that, for any given number formula_1, there can exist only a finite number of odd perfect numbers that have at most formula_1 prime factors. However, it remains open whether there exist any odd perfect numbers at all.
The divisibility relation among the "P"-smooth numbers, natural numbers whose prime factors all belong to the finite set "P", gives these numbers the structure of a partially ordered set isomorphic to formula_37. Thus, for any set "S" of "P"-smooth numbers, there is a finite subset of "S" such that every element of "S" is divisible by one of the numbers in this subset. This fact has been used, for instance, to show that there exists an algorithm for classifying the winning and losing moves from the initial position in the game of Sylver coinage, even though the algorithm itself remains unknown.
The tuples formula_21 in formula_16 correspond one-for-one with the monomials formula_40 over a set of formula_1 variables formula_42. Under this correspondence, Dickson's lemma may be seen as a special case of Hilbert's basis theorem stating that every polynomial ideal has a finite basis, for the ideals generated by monomials. Indeed, Paul Gordan used this restatement of Dickson's lemma in 1899 as part of a proof of Hilbert's basis theorem.
Notes.
 ;templatestyles src="Reflist/styles.css" / ;
References.
 ;templatestyles src="Reflist/styles.css" / ;