Dickson's lemma

Remarks

Equivalently, $\N^k$ with the product order is a well-quasi-ordering. The proof is by induction on $k$. From any infinite sequence in $\N^k$, extract a subsequence that is non-decreasing in the first coordinate. Then extract one that is also non-decreasing in the second coordinate, and so on. After $k$ steps the subsequence is non-decreasing in the product order, so no infinite antichain exists, and $\N^k$ is well-founded.

Example: for $S = \set{(a, b) \in \N^2 : ab \ge 6}$, the minimal elements are $(1, 6), (2, 3), (3, 2), (6, 1)$.

The main application is to monomial ideals. Identify the monomial $x_1^{a_1} \cdots x_k^{a_k}$ with $(a_1, \ldots, a_k)$; divisibility becomes the product order. So every monomial ideal in $F[x_1, \ldots, x_k]$ is generated by finitely many monomials.

Going deeper

For a student

Dickson's lemma is one of the first examples of a well-quasi-order beyond $\N$ itself: a finite product of copies of $\N$. It is the finiteness step behind Hilbert's basis theorem in the proof with Gröbner bases, and it shows that the Buchberger algorithm terminates. Higman's lemma and Kruskal's tree theorem are its analogues for words and trees.