AFTD Auto-Formalizing Theoretical Domains

k4_cycle_matroid_indep

theoremverified

A set of edges is independent in M(K₄) exactly when it is a forest.

Statement

theorem k4_cycle_matroid_indep (S : Set (Fin 6)) [DecidablePred (· ∈ S)] :
    k4_cycle_matroid.Indep S ↔ k4_forest (Finset.univ.filter (· ∈ 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 4
  • k4_cycle_matroidThe cycle matroid M(K₄) on the six edges of K₄.
  • k4_forestThe independent sets of the cycle matroid of K₄, with the six edges numbered 01, 23, 02, 13, 03, 12 (so {0,1}, {2,3}, {4,5} are the pairs…
  • k4_forest_subsetSubsets of forests of K₄ are forests.
  • k4_forest_augThe forests of K₄ satisfy the matroid augmentation axiom.
Used by 1

The proof, explained

The cycle matroid M(K₄) is constructed from finite independent sets using the forest predicate `k4_forest`. The general characterization lemma `IndepMatroid.ofFinset_indep` shows that a finset of edges is independent in the matroid if and only if it is a forest. Extensionality identifies the coerced finset of edges in S with S itself, yielding the claimed equivalence.

  1. The finset of elements of S, regarded as a set, is independent in M(K₄) if and only if it is a K₄-forest.

    The cycle matroid M(K₄) is defined via `IndepMatroid.ofFinset` with independence given by `k4_forest`. Instantiating the general characterization `IndepMatroid.ofFinset_indep` for the finset I = {x ∈ Fin 6 | x ∈ S} gives the equivalence between matroid independence of ↑I and the forest predicate `k4_forest I`. The four required matroid conditions are supplied: the empty set is a forest (verified computationally by `decide`), forests are closed under taking subsets (`k4_forest_subset`), forests satisfy the augmentation axiom (`k4_forest_aug`), and every finset is contained in the universal ground set (`Set.subset_univ`).

    lines 3–5

    uses IndepMatroid.ofFinset_indep, k4_forest_subset, k4_forest_aug, Set.subset_univ

      have h := IndepMatroid.ofFinset_indep (α := Fin 6) Set.univ k4_forest (by decide)
        k4_forest_subset k4_forest_aug (fun _ _ => Set.subset_univ _)
        (I := Finset.univ.filter (· ∈ S))
  2. The finset of elements of S, coerced to a set, equals S.

    By set extensionality (`ext x`), an edge x belongs to the finset filter {x ∈ Fin 6 | x ∈ S} if and only if x ∈ S, which simplifies directly to an identity.

    lines 6–7

      have hS : ((Finset.univ.filter (· ∈ S) : Finset (Fin 6)) : Set (Fin 6)) = S := by
        ext x; simp
  3. S is independent in M(K₄) if and only if the finset of elements of S is a K₄-forest.

    Substituting the set equality hS into the equivalence h replaces the coerced finset with S, completing the proof.

    lines 8–9

      rw [hS] at h
      exact h
IndepMatroid.ofFinset_indep
For a matroid constructed from finite sets via `IndepMatroid.ofFinset`, a subset coerced from a finset I is independent in the matroid if and only if I satisfies the independence predicate.
k4_forest_subset
If J is a K₄-forest and I ⊆ J, then I is also a K₄-forest.
k4_forest_aug
If I and J are K₄-forests with |I| < |J|, then there exists an edge e ∈ J \ I such that I ∪ {e} is also a K₄-forest.
Set.subset_univ
Every set is a subset of the universal set.

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 k4_cycle_matroid_indep (S : Set (Fin 6)) [DecidablePred (· ∈ S)] :    k4_cycle_matroid.Indep S ↔ k4_forest (Finset.univ.filter (· ∈ S)) := by  have h := IndepMatroid.ofFinset_indep (α := Fin 6) Set.univ k4_forest (by decide)    k4_forest_subset k4_forest_aug (fun _ _ => Set.subset_univ _)    (I := Finset.univ.filter (· ∈ S))  have hS : ((Finset.univ.filter (· ∈ S) : Finset (Fin 6)) : Set (Fin 6)) = S := by    ext x; simp  rw [hS] at h  exact h
See it in the graphDiscuss this resultChallenge it