PROPOSITION 1, p. 70 — Axioms 1 and 2' are equivalent to Axioms 1 and 2
ProvedEdmondsPartition.Main.proposition_1circuitmatroidmatroid-axiomsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite set and let a family of subsets of be called independent. Axiom 1 says that every subset of an independent set is independent; Axiom 2 says that for every all maximal independent subsets of have the same cardinality; Axiom 2' says that for every independent set and element , the set contains at most one circuit (minimal dependent set). Then
This lets the proof of THEOREM 1 work with Axiom 2', a statement about circuits, instead of the cardinality axiom that defines a matroid.
Formalization Note No other hypothesis is assumed: the statement is for an arbitrary family of subsets of a finite type, including the empty family (for which both sides hold).
Preamble
import Mathlib import Definitions.Def_WhitneyMatroid_RankIndep_Postulates import Definitions.Def_EdmondsPartition_Main_Basic
Formal statement
namespace EdmondsPartition.Main
open WhitneyMatroid.RankIndep
theorem proposition_1 {α : Type*} [Fintype α] [DecidableEq α]
(Indep : Finset α → Prop) :
(IndepI1 Indep ∧ Axiom2 Indep) ↔ (IndepI1 Indep ∧ Axiom2' Indep) := by sorry
end EdmondsPartition.Main
Source
Edmonds, Minimum partition of a matroid into independent subsets, J. Res. NBS 69B (1965), p. 70, PROPOSITION 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.