Dickson's lemma
In mathematics, Dickson's lemma is a finiteness statement applying to n-tuples of natural numbers. It is a simple fact from combinatorics, which has become attributed to the American algebraist Dickson. It was certainly known earlier, for example to Gordan in his researches on invariant theory.
Stating it first for clarity for N2, for any pair (m,n) of natural numbers we can introduce Rm,n, the 'rectangle' of numbers (r, s) with r at least m and s at least n. This is semi-infinite in the north and east directions, in the usual plane representation. The lemma then states that any union of the Rm,n is a finite union.
The generalization to Nk is the natural one, with k-tuples in place of pairs.
The statement says something about Nk as the topological space with the product topology arising from N, where the latter has the (semi-continuity) topology in which the open sets are all sets Rm defined as all n with n at least m. The 'rectangles' are by definition a base for the topology; it says finite unions give all open sets.
As for the proof of the lemma, it can be derived directly, but a slick way is to show that it is a special case of Hilbert's basis theorem - in fact is essentially the case of ideals generated by monomials.
Referenced By
Gröbner basis | List of combinatorics topics | List of mathematical topics (D-F) | List of mathematical topics (F-Z)
|
