AFTD Auto-Formalizing Theoretical Domains

not_matroid_common_colorable_loopyOn_zero

theoremverified

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.

  1. 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.

    line 3

      intro ⟨c, hc, _⟩
  2. 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.

    lines 4–6

    uses Matroid.loopyOn_ground, Set.mem_singleton

      have ha : a ∈ (Matroid.loopyOn ({a} : Set α)).E := by
        rw [Matroid.loopyOn_ground]
        exact Set.mem_singleton a
  3. 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.

    line 7

    uses Nat.not_lt_zero

      exact 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

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)
See it in the graphDiscuss this resultChallenge it