AFTD Auto-Formalizing Theoretical Domains

matroid_common_colorable_freeOn_one

theoremverified

A free matroid paired with itself has a common coloring with one color.

Statement

theorem matroid_common_colorable_freeOn_one {α : Type*} (E : Set α) :
    matroid_common_colorable (Matroid.freeOn E) (Matroid.freeOn E) 1
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

To show that the free matroid on E is common 1-colorable with itself, we assign every element the color 0. The color constraint 0 < 1 is satisfied by Nat.zero_lt_one, and each monochromatic subset is automatically a subset of the ground set E, hence independent in the free matroid by Matroid.freeOn_indep_iff.

  1. The constant coloring c(e) = 0 exhibits a valid 1-coloring for the pair of free matroids on E.

    We witness the existential definition of common 1-colorability with the constant function c(e) = 0. The color bound holds because every element has color 0, which is strictly less than 1 by Nat.zero_lt_one. For any color γ, the monochromatic subset {e ∈ E | c(e) = γ} is contained in the ground set E by definition (extracted by h.1). By Matroid.freeOn_indep_iff, every subset of E is independent in Matroid.freeOn E, so this set is independent in both copies of the matroid.

    lines 3–4

    uses Nat.zero_lt_one, Matroid.freeOn_indep_iff

      ⟨fun _ => 0, fun _ _ => Nat.zero_lt_one, fun _ => ⟨(Matroid.freeOn_indep_iff).2 fun _ h => h.1,
        (Matroid.freeOn_indep_iff).2 fun _ h => h.1⟩⟩
Nat.zero_lt_one
Zero is strictly less than one.
Matroid.freeOn_indep_iff
A subset I is independent in the free matroid on ground set E if and only if I ⊆ E.

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem matroid_common_colorable_freeOn_one {α : Type*} (E : Set α) :    matroid_common_colorable (Matroid.freeOn E) (Matroid.freeOn E) 1 :=  ⟨fun _ => 0, fun _ _ => Nat.zero_lt_one, fun _ => ⟨(Matroid.freeOn_indep_iff).2 fun _ h => h.1,    (Matroid.freeOn_indep_iff).2 fun _ h => h.1⟩⟩
See it in the graphDiscuss this resultChallenge it