Zuerst soll man sich klar machen, welche Ordnung auf 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 , die wir hier betrachten, ist die Produktordnung
(das ist auch die Ordnung in
Beispiel,
wenn man dort
-
und statt nimmt):
Für definiert man , wenn
-
Diese ist klar eine Ordnung auf , jedoch keine totale Ordnung für . Eine Motivation für die Produktordnung kommt aus der Teilbarkeitsrelation innerhalb eines Polynomrings: das Mononom teilt das Mononom genau dann, wenn .
Aus dem Induktionsprinzip folgt, dass die natürlichen Zahlen wohlgeordnet sind, d.h. jede nichtleere Teilmenge
besitzt ein kleinstes Element
(siehe
Fakt).
Also gilt das Lemma von Dickson für . Für ist es eine natürliche Idee, Induktion über zu verwenden. Der Einfachheit halber betrachten wir nur den Fall . Es empfiehlt sich, die Sache geometrisch in der Ebene
vorzustellen. Die minimalen Elemente von
sind dann die Randpunkte mit ganzzahligen Koordinaten, wenn man 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
existieren, die unendlich viele minimale Elemente
-
besitzt. Die Minimalität der Elemente bedeutet, dass man nicht und für vergleichen kann. Also gilt entweder und oder und . Um die Induktionsvoraussetzung anzuwenden, betrachtet man die Mengen
-
Da wohlgeordnet ist, besitzt ein kleinstes Element, das man ohne Einschränkung als annehmen kann. Dann ist es klar, dass das größte Element von ist. Nun betrachtet man die Mengen
-
Wie oben kann man annehmen, dass das kleinste Element von ist. Dies folgt, dass das größte Element von ist. Wenn man diesen Prozess fortsetzt, kann man davon ausgehen, dass
-
Die zweite Bedingung impliziert jedoch, dass die Menge kein kleinstes Element besitzt, ein Widerspruch.
Das Lemma von Dickson spielt eine Rolle beim Beweis des Hilbertschen Basissatzes, der besagt, dass der Polynomring
über einem Körper
noethersch ist, d.h. jedes Ideal von
ein endliches Erzeugendensystem besitzt.