Gordan's lemma
ProvedFamousTheorems.gordan_lemmaGordan's lemma. Let be a commutative monoid whose natural order is a well-quasi-order and which is cancellative, for example , and let be monoid homomorphisms into a cancellative monoid. Then the submonoid is finitely generated.
With and given by integer matrices with nonnegative entries, this says that the nonnegative integer solutions of a homogeneous linear system form a finitely generated monoid. This is the classical form of Gordan's lemma, which is basic in toric geometry, invariant theory and integer programming.
Formalization note. Mathlib's Submonoid.fg_eqLocusM. f.eqLocusM g is the submonoid where and agree. The hypotheses on are expressed by WellQuasiOrderedLE, IsOrderedCancelMonoid and CanonicallyOrderedMul.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem gordan_lemma {M N : Type*} [CommMonoid M] [PartialOrder M] [WellQuasiOrderedLE M] [IsOrderedCancelMonoid M]
[CanonicallyOrderedMul M] [Monoid N] [IsCancelMul N] (f g : M →* N) : (f.eqLocusM g).FG := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Submonoid.fg_eqLocusM`. Proof here reduces to that Mathlib result.