AFTD Auto-Formalizing Theoretical Domains

matroid_strongly_base_orderable_freeOn

theoremverified

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.

  1. 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.

    lines 3–5

    uses Matroid.freeOn_isBase_iff

      intro B₁ B₂ h₁ h₂
      rw [Matroid.freeOn_isBase_iff] at h₁ h₂
      subst h₁; subst h₂
  2. 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₂.

    lines 6–7

    uses Equiv.refl, Matroid.freeOn_isBase_iff

      refine ⟨Equiv.refl _, fun X => ?_⟩
      rw [Matroid.freeOn_isBase_iff]
  3. 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₂).

    lines 8–11

      ext x; constructor
      · rintro (⟨hx, -⟩ | ⟨y, -, rfl⟩)
        · exact hx
        · exact y.2
  4. 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).

    lines 12–16

    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.

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

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⟩
See it in the graphDiscuss this resultChallenge it