matroid_isFlat_inter
In any matroid M, if F₁ and F₂ are flats of M, then their intersection F₁ ∩ F₂ is also a flat of M.
Statement
theorem matroid_isFlat_inter {α : Type*} (M : Matroid α) {F₁ F₂ : Set α} (h₁ : M.IsFlat F₁) (h₂ : M.IsFlat F₂) : M.IsFlat (F₁ ∩ F₂)
- Source
- Mathlib.Combinatorics.Matroid.Closure
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- simple_graph_hop_or_leap_maximal_not_matroid_flatsNeither the collection of hop-closed edge subsets nor the collection of leap-closed edge subsets forms the set of flats of a matroid for…
Read back from the Lean
For any type α, any matroid M on α, and any subsets F₁ and F₂ of α, if F₁ is a flat of M (i.e., M.IsFlat F₁) and F₂ is a flat of M (i.e., M.IsFlat F₂), then their intersection F₁ ∩ F₂ is also a flat of M (i.e., M.IsFlat (F₁ ∩ F₂)).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof reduces the binary intersection F₁ ∩ F₂ to an indexed intersection over the two-element type `Bool`. The general theorem `Matroid.IsFlat.iInter` establishes that any nonempty indexed intersection of flats is a flat, which applies since both F₁ and F₂ are flats. Identifying this indexed intersection with F₁ ∩ F₂ via set extensionality completes the proof.
The intersection of the family consisting of F₁ and F₂ (indexed by `Bool`) is a flat of M.
We define a family of sets indexed by `Bool`, sending `true` to F₁ and `false` to F₂. By `Matroid.IsFlat.iInter`, any nonempty indexed intersection of flats in a matroid is a flat. Checking each boolean case yields F₁ and F₂, which are flats by the hypotheses h₁ and h₂.
uses
Matroid.IsFlat.iInterhave h := Matroid.IsFlat.iInter (ι := Bool) (Fs := fun b => bif b then F₁ else F₂) (fun b => by cases b <;> assumption)
The indexed intersection over `Bool` is equal to the binary intersection F₁ ∩ F₂.
By set extensionality, an element belongs to the indexed intersection if and only if it belongs to the set for both boolean values (F₂ and F₁). The simplifier evaluates this condition and commutes the conjunction with `and_comm` to obtain membership in F₁ ∩ F₂.
uses
and_commhave heq : (⋂ i, (bif i then F₁ else F₂ : Set α)) = F₁ ∩ F₂ := by ext x simp [and_comm]
The intersection F₁ ∩ F₂ is a flat of M.
Rewriting the flat indexed intersection using the set equality just proven gives that F₁ ∩ F₂ is a flat of M.
simpa [heq] using h
Matroid.IsFlat.iInter- In any matroid, a nonempty indexed intersection of flats is also a flat.
and_comm- Conjunction is commutative: for propositions a and b, a ∧ b is equivalent to b ∧ a.
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.
/-- The intersection of two flats in a matroid is a flat. -/theorem matroid_isFlat_inter {α : Type*} (M : Matroid α) {F₁ F₂ : Set α} (h₁ : M.IsFlat F₁) (h₂ : M.IsFlat F₂) : M.IsFlat (F₁ ∩ F₂) := by have h := Matroid.IsFlat.iInter (ι := Bool) (Fs := fun b => bif b then F₁ else F₂) (fun b => by cases b <;> assumption) have heq : (⋂ i, (bif i then F₁ else F₂ : Set α)) = F₁ ∩ F₂ := by ext x simp [and_comm] simpa [heq] using h