---
tag: NQD0Q9S9M7
kind: statement
role: lemma
name: Dickson's lemma
msc: [06A07, 13P10]
uses: [NH25G6GC07, K0AWJK6NZH, 0MWKJ44V5A, 4G25S7PJ22]
about: [NH25G6GC07]
sources:
  - url: https://en.wikipedia.org/wiki/Dickson's_lemma
same_as:
  wikidata: Q5273779
  wikipedia: Dickson's lemma
---

## Statement

Let $k \ge 1$ and order $\N^k$ by the [[product order|K0AWJK6NZH]]: $(a_1, \ldots, a_k) \le (b_1, \ldots, b_k)$ when $a_i \le b_i$ for every $i$.
Let $S$ be a subset of $\N^k$.
Then $S$ has only finitely many minimal elements, and every element of $S$ is greater than or equal to one of them.

## Remarks

Equivalently, $\N^k$ with the product order is a [[well-quasi-ordering|NH25G6GC07]].
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|4G25S7PJ22]].
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.

## Explanations

### L1 human

Take any collection of points with natural number coordinates in $k$ dimensions.
Some of them are "corner" points, with no other point of the collection below and to the left in every coordinate.
Dickson's lemma says there are only finitely many corner points, and every point lies above one of them.

### L2 human

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.