Dickson's lemma

In mathematics, Dickson's lemma states that every set of ${\displaystyle n}$-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.

Let ${\displaystyle K}$ be a fixed number, and let ${\displaystyle S=\{(x,y)\mid xy\geq K\}}$ be the set of pairs of numbers whose product is at least ${\displaystyle K}$. When defined over the positive real numbers, ${\displaystyle S}$ has infinitely many minimal elements of the form ${\displaystyle (x,K/x)}$, one for each positive number ${\displaystyle x}$; 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 ${\displaystyle S}$ to be less than or equal to ${\displaystyle (x,K/x)}$ 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 ${\displaystyle (x,y)}$ of natural numbers has ${\displaystyle x\leq K}$ and ${\displaystyle y\leq K}$, 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, ${\displaystyle S}$ has at most ${\displaystyle K^{2}}$ minimal elements, a finite number.

...
Wikipedia