Dickson's lemma
ProvedFamousTheorems.dickson_lemmaDickson's lemma. For every , every infinite sequence in has indices with componentwise.
Equivalently, with the product order is a well-quasi-order. Every set of monomials therefore has finitely many minimal elements, and every monomial ideal is finitely generated. This is a combinatorial form of Hilbert's basis theorem and is the reason Buchberger's algorithm for Gröbner bases terminates.
Formalization note. Mathlib's instance Pi.wellQuasiOrderedLE, which makes a finite product of well-quasi-ordered types well-quasi-ordered, used through wellQuasiOrdered_le. The order on Fin k → ℕ is the pointwise order.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems theorem dickson_lemma (k : ℕ) (f : ℕ → (Fin k → ℕ)) : ∃ i j, i < j ∧ f i ≤ f j := by sorry end FamousTheorems
Source
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Pi.wellQuasiOrderedLE`. Proof here reduces to that Mathlib result.