matroid_contract_singleton_coloopless_and_loopless_iff
Let M be a finite loopless and coloopless matroid on α and e ∈ M.E. Then the single-element contraction M.contract {e} is coloopless (i.e. (M.contract {e})✶.Loopless), and (M.contract {e}) is loopless if and only if e belongs to no two-element circuit of M (¬ ∃ C, M.IsCircuit C ∧ e ∈ C ∧ C.ncard = 2).
Statement
theorem matroid_contract_singleton_coloopless_and_loopless_iff {α : Type*} (M : Matroid α) [M.Finite] [M.Loopless] [M✶.Loopless] (e : α) (he : e ∈ M.E) : (M.contract {e})✶.Loopless ∧ ((M.contract {e}).Loopless ↔ ¬ ∃ C, M.IsCircuit C ∧ e ∈ C ∧ C.ncard = 2)
- Formalizes
- arXiv:2610.27706 Lemma 2.1(ii)
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
Let $α$ be a type, and let $M$ be a finite, loopless matroid on $α$ whose dual $M^*$ is also loopless (i.e., $M$ has no coloops). Let $e \in M.E$ be an element of the ground set of $M$. Then: 1. The dual of the contraction $(M / \{e\})^*$ is loopless (i.e., the contraction $M / \{e\}$ has no coloops), and 2. The contraction $M / \{e\}$ is loopless if and only if there does not exist a circuit $C$ of $M$ such that $e \in C$ and the cardinality of $C$ is 2.
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 first establishes that contracting an element e from a coloopless matroid preserves colooplessness: by duality, (M / {e})✶ = M✶ \ {e}, and deleting an element from the dual loopless matroid M✶ produces no loops. Second, the contraction M / {e} is loopless if and only if its loop set cl({e}) \ {e} is empty, meaning every element in the closure of {e} equals e. If e belonged to a 2-element circuit {e, y}, then y would be in cl({e}), creating a loop in the contraction. Conversely, if some f ≠ e belongs to cl({e}), there is a circuit C ⊆ {f, e} containing f; since M is loopless, C cannot be a singleton loop {f}, forcing C = {f, e} to be a 2-element circuit containing e.
The contracted matroid M / {e} is coloopless (its dual is loopless).
We split the conjunction into its two goals. For the first conjunct, by matroid duality, contracting {e} in M is dual to deleting {e} from M✶. Since M is coloopless, M✶ has no loops. Deleting an element from a loopless matroid leaves no loops (the loops of M✶ \ {e} are M✶.loops \ {e} = ∅ \ {e} = ∅). Hence (M / {e})✶ is loopless.
uses
Matroid.dual_contract,Matroid.loopless_iff,Matroid.delete_loops_eq,Matroid.loops_eq_empty,Set.empty_sdiffrefine ⟨?_, ?_⟩ · rw [Matroid.dual_contract, Matroid.loopless_iff, Matroid.delete_loops_eq, Matroid.loops_eq_empty, Set.empty_sdiff]
The contraction M / {e} is loopless if and only if cl({e}) = {e} (every element in cl({e}) equals e).
By definition, M / {e} is loopless if and only if its loop set is empty. The loops of M / {e} are given by cl({e}) \ {e}. This difference is empty precisely when no element belongs to it, which simplifies logically to: every element x ∈ cl({e}) must satisfy x = e. We split this bi-implication into its two directions.
uses
Matroid.loopless_iff,Matroid.contract_loops_eq,Set.eq_empty_iff_forall_notMem,Set.mem_sdiff,Set.mem_singleton_iff,not_and,not_not· rw [Matroid.loopless_iff, Matroid.contract_loops_eq, Set.eq_empty_iff_forall_notMem] simp only [Set.mem_sdiff, Set.mem_singleton_iff, not_and, not_not] constructor
If cl({e}) = {e}, then e belongs to no two-element circuit of M.
Assume every element in cl({e}) equals e. Suppose for contradiction that there exists a circuit C containing e with |C| = 2. Writing C = {x, y} with x ≠ y, the condition e ∈ C implies either e = x or e = y. If e = x, then C = {e, y} with e ≠ y; since C is a circuit containing y, removing y places y in the closure of the remainder, so y ∈ cl({e}), which forces y = e, a contradiction. Symmetrically, if e = y, then x ∈ cl({e}) forces x = e, contradicting x ≠ e.
uses
Set.ncard_eq_two.1,Set.mem_insert_iff,Set.mem_singleton_iff,Ne.symm· intro h ⟨C, hC, heC, hcard⟩ obtain ⟨x, y, hxy, rfl⟩ := Set.ncard_eq_two.1 hcard simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at heC rcases heC with rfl | rfl · have hyC : y ∈ ({e, y} : Set α) := by simp have hcl := hC.mem_closure_sdiff_singleton_of_mem hyC have : ({e, y} : Set α) \ {y} = {e} := by simp [hxy] rw [this] at hcl exact hxy.symm (h y hcl) · have hxC : x ∈ ({x, e} : Set α) := by simp have hcl := hC.mem_closure_sdiff_singleton_of_mem hxC have : ({x, e} : Set α) \ {x} = {e} := by simp [Ne.symm hxy] rw [this] at hcl exact hxy (h x hcl)
Assuming e belongs to no 2-element circuit, any element f ∈ cl({e}) distinct from e gives a circuit C ⊆ {f, e} containing f.
For the converse implication, assume e belongs to no 2-element circuit, let f ∈ cl({e}), and suppose for contradiction that f ≠ e. Then f ∉ {e}. By the characterization of matroid closure via circuits, f ∈ cl({e}) implies there exists a circuit C ⊆ {f, e} such that f ∈ C.
uses
Matroid.mem_closure_iff_exists_isCircuit· intro h f hf by_contra hfe apply h have hf_not : f ∉ ({e} : Set α) := by simpa obtain ⟨C, hCsub, hC, hfC⟩ := (Matroid.mem_closure_iff_exists_isCircuit hf_not).1 hf
The circuit C must contain e.
We prove e ∈ C by contradiction: if e ∉ C, then since C ⊆ {f, e}, the only element C can contain is f, so C = {f}. But a singleton circuit is a loop of M, which contradicts the hypothesis that M is loopless. Hence e must belong to C.
uses
Set.mem_singleton_iff,Set.mem_insert_iff,Matroid.singleton_isCircuit.1have heC : e ∈ C := by by_contra heC have : C = {f} := by ext x simp only [Set.mem_singleton_iff] constructor · intro hxC have := hCsub hxC simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at this obtain rfl | rfl := this · rfl · exact (heC hxC).elim · rintro rfl exact hfC subst this have hloop := Matroid.singleton_isCircuit.1 hC exact M.not_isLoop f hloop
The circuit C equals {f, e}, forming a 2-element circuit containing e, which contradicts the hypothesis.
Since C ⊆ {f, e} and both f ∈ C and e ∈ C, we have C = {f, e}. Because f ≠ e, this pair has cardinality 2. Thus C is a 2-element circuit containing e, contradicting the assumption that no such circuit exists. This completes the contradiction, proving f = e and hence that M / {e} is loopless.
uses
Set.mem_insert_iff,Set.mem_singleton_iff,Set.ncard_pairhave hCeq : C = {f, e} := by ext x simp only [Set.mem_insert_iff, Set.mem_singleton_iff] refine ⟨fun hx ↦ hCsub hx, fun hx ↦ ?_⟩ obtain rfl | rfl := hx · exact hfC · exact heC refine ⟨C, hC, heC, ?_⟩ rw [hCeq, Set.ncard_pair hfe]
Matroid.dual_contract- The dual of contracting a set X equals deleting X from the dual matroid: (M / X)✶ = M✶ \ X.
Matroid.loopless_iff- A matroid is loopless if and only if its set of loops is empty.
Matroid.delete_loops_eq- The loops of a deletion M \ D are the loops of M minus D: (M \ D).loops = M.loops \ D.
Matroid.loops_eq_empty- In any loopless matroid, the set of loops is empty.
Set.empty_sdiff- Removing any set from the empty set leaves the empty set: ∅ \ s = ∅.
Matroid.contract_loops_eq- The loops of a contraction M / C are the elements in the closure of C outside C: (M / C).loops = cl(C) \ C.
Set.eq_empty_iff_forall_notMem- A set is empty if and only if no element belongs to it.
Set.mem_sdiff- An element belongs to s \ t if and only if it belongs to s and not to t.
Set.mem_singleton_iff- An element belongs to a singleton {b} if and only if it equals b.
not_and- The negation ¬(a ∧ b) is equivalent to a → ¬b.
not_not- Double negation elimination: ¬¬a ↔ a.
Set.ncard_eq_two.1- If a set has cardinality 2, it is of the form {x, y} for two distinct elements x ≠ y.
Set.mem_insert_iff- An element belongs to insert a s if and only if it equals a or belongs to s.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
Matroid.mem_closure_iff_exists_isCircuit- For an element e ∉ X, e belongs to cl(X) if and only if there exists a circuit C ⊆ X ∪ {e} containing e.
Matroid.singleton_isCircuit.1- If a singleton {x} is a circuit, then x is a loop.
Set.ncard_pair- If a ≠ b, the unordered pair {a, b} has cardinality 2.
- Elementary set manipulations (such as showing that {e, y} \ {y} = {e} when e ≠ y) are handled inline by simp.
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.
/-- Contracting an element from a loopless and coloopless matroid produces a coloopless matroid, which is loopless if and only if the element belongs to no 2-element circuit. -/theorem matroid_contract_singleton_coloopless_and_loopless_iff {α : Type*} (M : Matroid α) [M.Finite] [M.Loopless] [M✶.Loopless] (e : α) (he : e ∈ M.E) : (M.contract {e})✶.Loopless ∧ ((M.contract {e}).Loopless ↔ ¬ ∃ C, M.IsCircuit C ∧ e ∈ C ∧ C.ncard = 2) := by refine ⟨?_, ?_⟩ · rw [Matroid.dual_contract, Matroid.loopless_iff, Matroid.delete_loops_eq, Matroid.loops_eq_empty, Set.empty_sdiff] · rw [Matroid.loopless_iff, Matroid.contract_loops_eq, Set.eq_empty_iff_forall_notMem] simp only [Set.mem_sdiff, Set.mem_singleton_iff, not_and, not_not] constructor · intro h ⟨C, hC, heC, hcard⟩ obtain ⟨x, y, hxy, rfl⟩ := Set.ncard_eq_two.1 hcard simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at heC rcases heC with rfl | rfl · have hyC : y ∈ ({e, y} : Set α) := by simp have hcl := hC.mem_closure_sdiff_singleton_of_mem hyC have : ({e, y} : Set α) \ {y} = {e} := by simp [hxy] rw [this] at hcl exact hxy.symm (h y hcl) · have hxC : x ∈ ({x, e} : Set α) := by simp have hcl := hC.mem_closure_sdiff_singleton_of_mem hxC have : ({x, e} : Set α) \ {x} = {e} := by simp [Ne.symm hxy] rw [this] at hcl exact hxy (h x hcl) · intro h f hf by_contra hfe apply h have hf_not : f ∉ ({e} : Set α) := by simpa obtain ⟨C, hCsub, hC, hfC⟩ := (Matroid.mem_closure_iff_exists_isCircuit hf_not).1 hf have heC : e ∈ C := by by_contra heC have : C = {f} := by ext x simp only [Set.mem_singleton_iff] constructor · intro hxC have := hCsub hxC simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at this obtain rfl | rfl := this · rfl · exact (heC hxC).elim · rintro rfl exact hfC subst this have hloop := Matroid.singleton_isCircuit.1 hC exact M.not_isLoop f hloop have hCeq : C = {f, e} := by ext x simp only [Set.mem_insert_iff, Set.mem_singleton_iff] refine ⟨fun hx ↦ hCsub hx, fun hx ↦ ?_⟩ obtain rfl | rfl := hx · exact hfC · exact heC refine ⟨C, hC, heC, ?_⟩ rw [hCeq, Set.ncard_pair hfe]