matroid_strongly_base_orderable_freeOn
A free matroid (every subset of the ground set independent) is strongly base-orderable.
Statement
theorem matroid_strongly_base_orderable_freeOn {α : Type*} (E : Set α) : matroid_strongly_base_orderable (Matroid.freeOn E)
- Source
- sanity check of matroid_strongly_base_orderable
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- matroid_strongly_base_orderableA matroid M is strongly base-orderable if for every two bases B₁, B₂ there is a bijection φ : B₁ → B₂ such that (B₁ \ X) ∪ φ(X) is a base…
The proof, explained
In the free matroid on ground set E, every subset is independent, so the ground set E is the unique base. Consequently, any two bases B₁ and B₂ are identical to E. Choosing the bijection between them to be the identity map, exchanging any subset X ⊆ B₁ with its image leaves the set unchanged, (B₁ \ X) ∪ X = B₁ = E, which is a base.
Any two bases B₁ and B₂ of the free matroid on E are equal to E.
We introduce arbitrary bases B₁ and B₂ of the free matroid on E. By Matroid.freeOn_isBase_iff, the only base of a free matroid on E is the ground set E itself. Thus B₁ = E and B₂ = E, allowing us to substitute and identify all three sets.
uses
Matroid.freeOn_isBase_iffintro B₁ B₂ h₁ h₂ rw [Matroid.freeOn_isBase_iff] at h₁ h₂ subst h₁; subst h₂
Using the identity bijection, it suffices to show (B₂ \ X) ∪ X = B₂ for any subset X ⊆ B₂.
To establish strong base-orderability, we choose the bijection φ : B₂ ≃ B₂ to be the identity equivalence Equiv.refl. For an arbitrary subset X ⊆ B₂, rewriting with Matroid.freeOn_isBase_iff reduces showing that the exchanged set (B₂ \ X) ∪ φ(X) is a base to showing that it equals B₂.
uses
Equiv.refl,Matroid.freeOn_isBase_iffrefine ⟨Equiv.refl _, fun X => ?_⟩ rw [Matroid.freeOn_isBase_iff]
The exchanged set (B₂ \ X) ∪ X is contained in B₂.
We establish set equality by double containment. For the forward direction, an element x in (B₂ \ X) ∪ X either comes from B₂ \ X (in which case x ∈ B₂ directly) or is the image of some y ∈ X ⊆ B₂ under the identity map (in which case x = y ∈ B₂).
ext x; constructor · rintro (⟨hx, -⟩ | ⟨y, -, rfl⟩) · exact hx · exact y.2
The base B₂ is contained in (B₂ \ X) ∪ X.
For the reverse direction, take any x ∈ B₂ and consider whether x ∈ X. If x ∈ X, then x belongs to the right-hand component of the union (via Or.inr). If x ∉ X, then x ∈ B₂ \ X, placing it in the left-hand component (via Or.inl).
uses
Or.inr,Or.inl· intro hx by_cases h : x ∈ ((↑) '' X : Set α) · obtain ⟨y, hy, rfl⟩ := h exact Or.inr ⟨y, hy, rfl⟩ · exact Or.inl ⟨hx, h⟩
Matroid.freeOn_isBase_iff- A subset is a base of the free matroid on E if and only if it equals E.
Equiv.refl- The identity bijection from a type to itself.
Or.inr- From a proof of B, infers the disjunction A ∨ B.
Or.inl- From a proof of A, infers the disjunction A ∨ B.
- In the formal definition of strong base-orderability, the subset X is typed as a set on the subtype of elements in B₁, so set operations formally involve coercing subtype elements into the ambient type α.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem matroid_strongly_base_orderable_freeOn {α : Type*} (E : Set α) : matroid_strongly_base_orderable (Matroid.freeOn E) := by intro B₁ B₂ h₁ h₂ rw [Matroid.freeOn_isBase_iff] at h₁ h₂ subst h₁; subst h₂ refine ⟨Equiv.refl _, fun X => ?_⟩ rw [Matroid.freeOn_isBase_iff] ext x; constructor · rintro (⟨hx, -⟩ | ⟨y, -, rfl⟩) · exact hx · exact y.2 · intro hx by_cases h : x ∈ ((↑) '' X : Set α) · obtain ⟨y, hy, rfl⟩ := h exact Or.inr ⟨y, hy, rfl⟩ · exact Or.inl ⟨hx, h⟩