AFTD Auto-Formalizing Theoretical Domains

three_k4_partition_matroid_indep

theoremverified

A set is independent in the partition matroid M₂ exactly when the class map is injective on it.

Statement

theorem three_k4_partition_matroid_indep (S : Set (Fin 3 × Fin 6)) :
    three_k4_partition_matroid.Indep S ↔ Set.InjOn three_k4_partition_class S
Source
step towards matroid_common_list_colorable_two_not_of_colorable_two (arXiv:2610.07318 (A note on the list chromatic number of two matroids), Theorem 1.1)
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • three_k4_partition_matroidThe unit-capacity partition matroid M₂ whose independent sets meet every class of three_k4_partition_class at most once.
  • three_k4_partition_classThe nine classes of the partition matroid M₂: in copy i the opposite pair a_i (edges 01, 23) is a class, and the classes {b_i⁺, c_{i+1}⁻}…
Used by 1

The proof, explained

The partition matroid `three_k4_partition_matroid` is defined as the pullback (via `Matroid.comap`) of the free matroid on `Fin 9` along `three_k4_partition_class`. Independence in a pullback matroid requires that the image be independent in the base matroid and that the pullback map be injective on the subset. Because every subset of the universe is independent in the free matroid, the first condition is trivially satisfied, leaving injectivity of the map as the exact condition for independence.

  1. A subset S ⊆ Fin 3 × Fin 6 is independent in three_k4_partition_matroid if and only if three_k4_partition_class is injective on S. automation

    By definition, three_k4_partition_matroid is the pullback of the free matroid on the universal set of Fin 9 under the map three_k4_partition_class. A set S is independent in such a pullback matroid if and only if its image is independent in the base matroid and the map is injective on S. Since every subset of the universal set is independent in the free matroid, the image condition holds trivially, so independence is equivalent to injectivity of three_k4_partition_class on S. The simp tactic unfolds the definition and evaluates these equivalences automatically.

    line 3

    uses three_k4_partition_matroid

      simp [three_k4_partition_matroid]
three_k4_partition_matroid
the partition matroid on Fin 3 × Fin 6, defined by pulling back (comap) the free matroid on the universal set of Fin 9 along three_k4_partition_class

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 three_k4_partition_matroid_indep (S : Set (Fin 3 × Fin 6)) :    three_k4_partition_matroid.Indep S ↔ Set.InjOn three_k4_partition_class S := by  simp [three_k4_partition_matroid]
See it in the graphDiscuss this resultChallenge it