Prove2Me
Navigate
DiscoverFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Theorem 23 — duals iff bases correspond to base complements

Proved
WhitneyMatroid.Duality.isDualVia_iff_isBase_compl

by mikedeng1 · 1 vote · Oct 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

basesdualitymatroidsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let MMM and M′M'M′ be matroids on finite sets of elements and let σ\sigmaσ be a one-to-one correspondence between their elements. Then M′M'M′ is a dual of MMM via σ\sigmaσ (identity (11.1) for every subset) if and only if bases in one correspond to base complements in the other: for every subset BBB of MMM,

B is a base of M  ⟺  (M′∖σ(B)) is a base of M′.B \text{ is a base of } M \iff (M' \setminus \sigma(B)) \text{ is a base of } M'.B is a base of M⟺(M′∖σ(B)) is a base of M′.

This turns the rank identity (11.1) into a statement about bases only; it is how Whitney proves Theorem 28, and it shows that a matroid's duals are exactly the copies of its usual dual matroid M∗M^*M∗.

Formalization Note Whitney's Theorem 23 reads "MMM and M′M'M′ are duals if and only if there is a 1–1 correspondence such that bases in one correspond to base complements in the other." It is stated here for a fixed correspondence σ\sigmaσ, as in Whitney's proof; the existential version follows by quantifying over σ\sigmaσ on both sides. Since σ\sigmaσ is a bijection, the displayed equivalence for all BBB covers both directions of "bases in one correspond to base complements in the other". Both ground sets are the whole finite types.

Preamble
import Mathlib
import Definitions.Def_WhitneyMatroid_Duality_IsDual
Formal statement
namespace WhitneyMatroid.Duality

/-- Whitney, Theorem 23 (p. 522), for a fixed correspondence `σ`: `M` and `M′` (each with the whole
finite type as ground set) are duals via `σ` if and only if bases in one correspond to base
complements in the other: `B` is a base of `M` exactly when the complement of `σ(B)` is a base of
`M′`. -/
theorem isDualVia_iff_isBase_compl {α β : Type*} [Finite α] [Finite β] (M : Matroid α)
    (M' : Matroid β) (σ : α ≃ β) (hE : M.E = Set.univ) (hE' : M'.E = Set.univ) :
    IsDualVia M M' σ ↔ ∀ B : Set α, M.IsBase B ↔ M'.IsBase (Set.univ \ σ '' B) := by sorry

end WhitneyMatroid.Duality
Source
Whitney, On the Abstract Properties of Linear Dependence, Amer. J. Math. 57 (1935), pp. 522–523, Theorem 23
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me