not_matroid_common_colorable_loopyOn_zero
A nonempty ground set has no common coloring with zero colors.
Statement
theorem not_matroid_common_colorable_loopyOn_zero {α : Type*} (a : α) : ¬ matroid_common_colorable (Matroid.loopyOn {a}) (Matroid.loopyOn {a}) 0
- Source
- sanity check of matroid_common_colorable
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- matroid_common_colorableTwo matroids M₁, M₂ on a common ground set E have a common coloring with k colors: a map c : E → {0, …, k−1} each of whose color classes…
The proof, explained
The proof argues by contradiction. If a common 0-coloring existed for the loopy matroid on {a}, each element in its ground set would be assigned a natural number color strictly less than 0. But a belongs to the ground set {a}, and no natural number is strictly less than 0.
Assume for contradiction that a common 0-coloring exists.
By the definition of a common matroid coloring with 0 colors, there would exist a coloring function c : α → ℕ such that every element e in the ground set of the first matroid satisfies c(e) < 0.
intro ⟨c, hc, _⟩The element a belongs to the ground set of the loopy matroid on {a}.
By Matroid.loopyOn_ground, the ground set of Matroid.loopyOn {a} is the set {a}, which contains a by Set.mem_singleton.
uses
Matroid.loopyOn_ground,Set.mem_singletonhave ha : a ∈ (Matroid.loopyOn ({a} : Set α)).E := by rw [Matroid.loopyOn_ground] exact Set.mem_singleton a
This leads to a contradiction.
Applying the coloring property to the element a gives c(a) < 0. However, Nat.not_lt_zero states that no natural number is strictly less than 0, yielding a contradiction.
uses
Nat.not_lt_zeroexact Nat.not_lt_zero _ (hc a ha)
Matroid.loopyOn_ground- The ground set of a loopy matroid on E is E itself.
Set.mem_singleton- For any element a, a is in the singleton set {a}.
Nat.not_lt_zero- No natural number is strictly less than zero.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem not_matroid_common_colorable_loopyOn_zero {α : Type*} (a : α) : ¬ matroid_common_colorable (Matroid.loopyOn {a}) (Matroid.loopyOn {a}) 0 := by intro ⟨c, hc, _⟩ have ha : a ∈ (Matroid.loopyOn ({a} : Set α)).E := by rw [Matroid.loopyOn_ground] exact Set.mem_singleton a exact Nat.not_lt_zero _ (hc a ha)