Theorem 2.29 -- the matroid base-family / rank-function correspondence
ProvedDiscreteConvex.Combinatorial.matroid_axiom_correspondenceTheorem 2.29 (p.70). The class of set functions satisfying the rank axioms (R1)-(R3) and the class of nonempty families satisfying the simultaneous exchange axiom (B) are in one-to-one correspondence through the mutually inverse maps
Concretely, the theorem asserts two things. First, starting from a nonempty exchange family , the induced rank function satisfies (R1)-(R3), and recovering the family from returns again. Second, starting from a rank function satisfying (R1)-(R3), the recovered family is nonempty, satisfies (B), and its own induced rank function is again.
This one-to-one correspondence is the finite-ground-set instance of the equivalence between exchangeability and submodularity that underlies matroid theory, and its generalization to functions on the integer lattice (M-convex functions) is the subject of later chapters of the book.
Formalization Note. The ground set is a Fintype with DecidableEq; is represented as Finset (Finset V).
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.70, Theorem 2.29.)
import Mathlib import Definitions.Def_DiscreteConvex_Combinatorial_ExchangeFamily import Definitions.Def_DiscreteConvex_Combinatorial_RankAxioms import Definitions.Def_DiscreteConvex_Combinatorial_RankOfFamily import Definitions.Def_DiscreteConvex_Combinatorial_FamilyOfRank
namespace DiscreteConvex.Combinatorial
/-- Theorem 2.29 (Murota, *Discrete Convex Analysis*, SIAM 2003, p.70). The class of set
functions `ρ : Finset V → ℤ` satisfying the rank axioms (R1)-(R3) and the class of nonempty
families `𝓑 : Finset (Finset V)` satisfying the simultaneous exchange axiom (B) are in
one-to-one correspondence through the mutually inverse maps `RankOfFamily` (Eq. 2.71) and
`FamilyOfRank` (Eq. 2.72). -/
theorem matroid_axiom_correspondence {V : Type*} [Fintype V] [DecidableEq V] :
(∀ 𝓑 : Finset (Finset V), 𝓑.Nonempty → ExchangeFamily 𝓑 →
RankAxioms (RankOfFamily 𝓑) ∧ FamilyOfRank (RankOfFamily 𝓑) = 𝓑) ∧
(∀ ρ : Finset V → ℤ, RankAxioms ρ →
(FamilyOfRank ρ).Nonempty ∧ ExchangeFamily (FamilyOfRank ρ) ∧
RankOfFamily (FamilyOfRank ρ) = ρ) := by sorry
end DiscreteConvex.Combinatorial
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.