Lemma von Dickson/Aufgabe/Kommentar

Zuerst soll man sich klar machen, welche Ordnung auf ${}\mathbb {N} ^{r}$ berücksichtigt wird. Diese ist keine lexikographische Ordnung, die in Aufgabe betrachtet wurde. Für die lexikographische Ordnung ist die Aussage des Lemmas von Dickson ganz trivial (wieso?) und nicht nützlich. Die Ordnung auf ${}\mathbb {N} ^{r}$, die wir hier betrachten, ist die Produktordnung (das ist auch die Ordnung in Beispiel, wenn man dort

${}X=\{1,\ldots ,r\}\,$

und ${}\mathbb {N}$ statt ${}\mathbb {R}$ nimmt): Für ${}a=(a_{1},\dots ,a_{r}),b=(b_{1},\dots ,b_{r})\in \mathbb {N} ^{r}$ definiert man ${}a\leq b$, wenn

$a_{1}\leq b_{1},a_{2}\leq b_{2},\dots ,a_{r}\leq b_{r}.$

Diese ist klar eine Ordnung auf ${}\mathbb {N} ^{r}$, jedoch keine totale Ordnung für ${}r\geq 2$. Eine Motivation für die Produktordnung kommt aus der Teilbarkeitsrelation innerhalb eines Polynomrings: das Mononom ${}x_{1}^{a_{1}}\cdots x_{r}^{a_{r}}$ teilt das Mononom ${}x_{1}^{b_{1}}\cdots x_{r}^{b_{r}}$ genau dann, wenn ${}a\leq b$.

Aus dem Induktionsprinzip folgt, dass die natürlichen Zahlen wohlgeordnet sind, d.h. jede nichtleere Teilmenge ${}T\subseteq \mathbb {N}$ besitzt ein kleinstes Element (siehe Fakt). Also gilt das Lemma von Dickson für ${}r=1$. Für ${}r>1$ ist es eine natürliche Idee, Induktion über ${}r$ zu verwenden. Der Einfachheit halber betrachten wir nur den Fall ${}r=2$. Es empfiehlt sich, die Sache geometrisch in der Ebene ${}\mathbb {N} ^{2}\subseteq \mathbb {R} ^{2}$ vorzustellen. Die minimalen Elemente von ${}T\subseteq \mathbb {N} ^{2}$ sind dann die Randpunkte mit ganzzahligen Koordinaten, wenn man ${}T$ reell auffüllt (die konvexe Hülle nimmt). Die Aussage ist dann, dass es nur endlich viele solche Randpunkte gibt.

Wäre das Lemma falsch, würde eine Teilmenge ${}T\subseteq \mathbb {N} ^{2}$ existieren, die unendlich viele minimale Elemente

$t_{1}=(a_{1},b_{1}),t_{2}=(a_{2},b_{2}),\dots ,t_{n}=(a_{n},b_{n}),\dots$

besitzt. Die Minimalität der Elemente ${}t_{i}$ bedeutet, dass man nicht ${}t_{i}$ und ${}t_{j}$ für ${}i\neq j$ vergleichen kann. Also gilt entweder ${}a_{i}<a_{j}$ und ${}b_{i}>b_{j}$ oder ${}a_{i}>a_{j}$ und ${}b_{i}<b_{j}$. Um die Induktionsvoraussetzung anzuwenden, betrachtet man die Mengen

$A_{1}=\{a_{1},a_{2},\dots ,a_{n},\dots ,\},\ B_{1}=\{b_{1},b_{2},\dots ,b_{n},\dots ,\}\subseteq \mathbb {N} .$

Da ${}\mathbb {N}$ wohlgeordnet ist, besitzt ${}A_{1}$ ein kleinstes Element, das man ohne Einschränkung als ${}a_{1}$ annehmen kann. Dann ist es klar, dass ${}b_{1}$ das größte Element von ${}B_{1}$ ist. Nun betrachtet man die Mengen

$A_{2}=\{a_{2},a_{3},\dots ,a_{n},\dots ,\},\ B_{2}=\{b_{2},b_{3},\dots ,b_{n},\dots ,\}\subseteq \mathbb {N} .$

Wie oben kann man annehmen, dass ${}a_{2}$ das kleinste Element von ${}A_{2}$ ist. Dies folgt, dass ${}b_{2}$ das größte Element von ${}B_{2}$ ist. Wenn man diesen Prozess fortsetzt, kann man davon ausgehen, dass

$a_{1}<a_{2}<\cdots <a_{n}<\cdots ,\ b_{1}>b_{2}>\cdots >b_{n}>\cdots .$

Die zweite Bedingung impliziert jedoch, dass die Menge ${}B_{1}=\{b_{1},b_{2},\dots ,b_{n},\dots ,\}$ kein kleinstes Element besitzt, ein Widerspruch.

Das Lemma von Dickson spielt eine Rolle beim Beweis des Hilbertschen Basissatzes, der besagt, dass der Polynomring ${}k[x_{1},\ldots ,x_{n}]$ über einem Körper ${}k$ noethersch ist, d.h. jedes Ideal von ${}k[x_{1},\ldots ,x_{n}]$ ein endliches Erzeugendensystem besitzt.

Zur kommentierten Aufgabe