Lemme de Dickson

Soit ${\displaystyle K}$ un entier fixé, et soit ${\displaystyle S=\{(x,y)\mid xy\geq K\}}$ l'ensemble des couples de nombres dont le produit est au moins ${\displaystyle K}$. Lorsqu'il est défini sur les nombres réels positifs et muni de l'ordre produit, ${\displaystyle S}$ a une infinité d'éléments minimaux de la forme ${\displaystyle (x,K/x)}$, un pour chaque nombre positif ${\displaystyle x}$ ; cet ensemble de points est l'une des branches d'une hyperbole. Cependant, le lemme de Dickson ne concerne que les n-uplet d'entiers naturels, et sur les nombres naturels il n'y a qu'un nombre fini de couples minimaux. Chaque couple minimal ${\displaystyle (x,y)}$ d'entiers naturels vérifie ${\displaystyle x\leq K}$ et ${\displaystyle y\leq K}$, car si x était strictement supérieur à K alors (x − 1, y) appartiendrait aussi à S. Donc ${\displaystyle S}$ admet au plus ${\displaystyle K^{2}}$ éléments minimaux, un nombre fini^{[note 1]}.

Soit ${\displaystyle \mathbb {N} }$ l'ensemble des entiers naturels, soit n une constante fixe quelconque. On munit ${\displaystyle \mathbb {N} ^{n}}$ de l'ordre partiel produit, pour lequel ${\displaystyle (a_{1},a_{2},\dots ,a_{n})\leq (b_{1},b_{2},\dots b_{n})}$ si et seulement si, pour tout ${\displaystyle i}$, ${\displaystyle a_{i}\leq b_{i}}$. L'ensemble des n-uplets supérieurs ou égaux à un n-uplet particulier ${\displaystyle a=(a_{1},a_{2},\dots ,a_{n})}$ forme un orthant positif, de sommet ${\displaystyle a}$.

Avec cette notation, le lemme de Dickson peut être énoncé sous plusieurs formes équivalentes :

• pour toute partie non vide ${\displaystyle S}$ de ${\displaystyle \mathbb {N} ^{n}}$, l'ensemble des éléments minimaux de ${\displaystyle S}$ est fini et non nul^[1] ;
• ${\displaystyle (\mathbb {N} ^{n},\leq )}$ est un bel ordre ;
• toute partie non vide ${\displaystyle S}$ de ${\displaystyle \mathbb {N} ^{n}}$ peut être couverte par un ensemble fini d'orthants positifs, dont les sommets appartiennent tous à ${\displaystyle S}$.