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 L. E. Dickson. It was certainly known earlier, for example to Gordan in his researches on invariant theory.

Stating it first for the two-dimensional case for clarity, let $\mathbb{N}$ be the set of nonnegative integers (natural numbers), and for any pair $(m, n)$ of natural numbers we can introduce

$R_{m,n} := \{ (r, s) \in \mathbb{N}^2 : r \geq m \text{ and } s \geq n\}$,

which is semi-infinite quarter-plane of lattice points with nonnegative integer coordinates. The lemma then states that any subset $M \subseteq \mathbb{N}^2$ is contained in the union of a finite subset of such $R_{m,n}$, where each pair $(m,n) \in M$. This is analogous to the conventional topological definition of compactness.

The generalization to $\mathbb{N}^k$ is the natural one, with $k$-tuples in place of pairs.

The statement says something about $\mathbb{N}^k$ as the topological space with the product topology arising from $\mathbb{N}$, where the latter has the (semi-continuity) topology in which the open sets are all sets

$R_m := \{m \in \mathbb{N} : r \geq m\}$

The 'rectangles' are by definition a base for the topology; Dickson's lemma says finite unions give all open sets.

As for the proof of the lemma, it can be derived directly, but it also followed directly as a special case of Hilbert's basis theorem. In fact it is essentially the case of ideals generated by monomials.

References

• Dickson, L. E. (1913). "Finiteness of the odd perfect and primitive abundant numbers with $n$ distinct prime factors". Amer. Journal Math. 35 (4): 413–422. doi:10.2307/2370405. JSTOR 2370405.