PROPOSITION 5, p. 70 — S(A) is the maximal set containing A of the same rank; r(S(I)) = |I| for independent I
ProvedEdmondsPartition.Main.proposition_5Throughout, is a finite matroid: a finite set of elements (the type , with the whole set) together with a family of independent subsets satisfying Axiom 1 (every subset of an independent set is independent) and Axiom 2 (for every subset , all maximal independent subsets of have the same number of elements). For , the rank is the largest cardinality of an independent subset of . The span is the minimal set containing such that no circuit (minimal dependent set) has exactly one element outside it. Then:
- for every , is the unique maximal set containing with the same rank as : , , and every with satisfies ;
- in particular, for every independent set ,
Besides Axioms 1 and 2' and the definitions of circuit and span, the second part is the only fact about matroids used in the proof of THEOREM 1.
Formalization Note Lean also assumes that the empty set is independent (). The paper's rank, "the number of elements in each maximal independent set contained in ", presupposes that every set has an independent subset; with an empty family Axioms 1 and 2 hold vacuously and the statement fails.
import Mathlib import Definitions.Def_WhitneyMatroid_RankIndep_Postulates import Definitions.Def_EdmondsPartition_Main_Basic
namespace EdmondsPartition.Main
open WhitneyMatroid.RankIndep
theorem proposition_5 {α : Type*} [Fintype α] [DecidableEq α] (Indep : Finset α → Prop)
(h1 : IndepI1 Indep) (h2 : Axiom2 Indep) (h0 : Indep ∅) :
(∀ A : Finset α, A ⊆ spanOf Indep A ∧
rankOfIndep Indep (spanOf Indep A) = rankOfIndep Indep A ∧
∀ T : Finset α, A ⊆ T → rankOfIndep Indep T = rankOfIndep Indep A →
T ⊆ spanOf Indep A) ∧
∀ I : Finset α, Indep I → rankOfIndep Indep (spanOf Indep I) = (I.card : ℤ) := by sorry
end EdmondsPartition.Main
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.