AFTD Auto-Formalizing Theoretical Domains

matroid_delete_singleton_loopless_and_coloopless_iff

theoremverifiedformalization

Let M be a finite loopless and coloopless matroid on α and e ∈ M.E. Then the single-element deletion M.delete {e} is loopless; moreover, it is coloopless ((M.delete {e})✶.Loopless) if and only if e belongs to no two-element cocircuit of M (¬ ∃ C, M.IsCocircuit C ∧ e ∈ C ∧ C.ncard = 2).

Statement

theorem matroid_delete_singleton_loopless_and_coloopless_iff
    {α : Type*} (M : Matroid α) [M.Finite] [M.Loopless] [M✶.Loopless]
    (e : α) (he : e ∈ M.E) :
    (M.delete {e}).Loopless ∧
    ((M.delete {e})✶.Loopless ↔ ¬ ∃ C, M.IsCocircuit C ∧ e ∈ C ∧ C.ncard = 2)
Formalizes
arXiv:2610.27706 Lemma 2.1(i)
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

Read back from the Lean

For any type α, any finite matroid M on α such that both M and its dual M✶ are loopless (i.e., M is loopless and coloopless), and any element e in the ground set M.E of M: 1. The deletion M.delete {e} is loopless; and 2. The dual of M.delete {e} is loopless (i.e., M.delete {e} has no coloops) if and only if there does not exist a cocircuit C of M such that e ∈ C and the cardinality of C (Set.ncard 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

Deleting an element e from a loopless matroid preserves looplessness because deletion is a restriction. By duality, the dual deletion (M \ {e})✶ is the contraction M✶ / {e}, whose loops are precisely the elements of M✶.closure({e}) \ {e}, so colooplessness of the deletion is equivalent to having no other element in the dual closure of {e}. This in turn holds if and only if {e} cannot be extended by an element f ≠ e to a circuit of M✶, meaning M has no 2-element cocircuit containing e.

  1. The deletion M.delete {e} is loopless.

    A deletion is a restriction of the original matroid. Since M is loopless by assumption, any restriction of M is also loopless.

    line 7

    uses Matroid.delete_isRestriction

      refine ⟨(Matroid.delete_isRestriction M {e}).loopless, ?_⟩
  2. Colooplessness of M.delete {e} is equivalent to no element x ≠ e lying in the dual closure M✶.closure {e}.

    By duality, (M.delete {e})✶ = M✶.contract {e}. A matroid is loopless if and only if its set of loops is empty, and the loops of M✶.contract {e} are precisely the elements in M✶.closure {e} \ {e}. Hence (M.delete {e})✶ is loopless if and only if no element distinct from e belongs to M✶.closure {e}. In addition, e belongs to the dual ground set M✶.E because M✶.E = M.E.

    lines 8–10

    uses Matroid.dual_delete, Matroid.loopless_iff, Matroid.contract_loops_eq, Set.eq_empty_iff_forall_notMem, M.dual_ground

      rw [Matroid.dual_delete, Matroid.loopless_iff, Matroid.contract_loops_eq, Set.eq_empty_iff_forall_notMem]
      simp only [Set.mem_sdiff, Set.mem_singleton_iff]
      have he_dual : e ∈ M✶.E := by rw [M.dual_ground]; exact he
  3. In the forward direction, if a 2-element cocircuit C contains e, then C = {e, f} for some f ≠ e.

    We proceed by contradiction: assuming no x ≠ e belongs to M✶.closure {e}, suppose there exists a cocircuit C containing e with |C| = 2. A 2-element set can be written as {x, y} with x ≠ y. Since e ∈ C, either e = x or e = y, so C can be written as {e, f} with f ≠ e.

    lines 11–18

    uses Set.ncard_eq_two, Set.pair_comm

      constructor
      · intro h ⟨C, hC, heC, hCcard⟩
        obtain ⟨f, hfe, rfl⟩ : ∃ f, f ≠ e ∧ C = {e, f} := by
          obtain ⟨x, y, hxy, rfl⟩ := Set.ncard_eq_two.mp hCcard
          simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at heC
          rcases heC with rfl | rfl
          · exact ⟨y, hxy.symm, rfl⟩
          · exact ⟨x, hxy, by rw [Set.pair_comm]⟩
  4. The existence of the cocircuit {e, f} implies f ∈ M✶.closure {e}, contradicting the assumption.

    Since C = {e, f} is a cocircuit of M, it is a circuit of M✶. Removing any element from a circuit leaves a basis, so {e, f} \ {f} is a basis of {e, f} in M✶. Since f ≠ e, {e, f} \ {f} = {e}. Because any set is contained in the closure of its basis, {e, f} ⊆ M✶.closure {e}, which implies f ∈ M✶.closure {e}. This contradicts the assumption that no element other than e belongs to M✶.closure {e}.

    lines 19–32

    uses Set.mem_insert_of_mem, Or.inl

        have hmem : f ∈ ({e, f} : Set α) := Set.mem_insert_of_mem e rfl
        have hbas := hC.sdiff_singleton_isBasis hmem
        have hdiff : ({e, f} : Set α) \ {f} = {e} := by
          ext x
          simp only [Set.mem_sdiff, Set.mem_insert_iff, Set.mem_singleton_iff]
          constructor
          · rintro ⟨rfl | rfl, hne⟩
            · rfl
            · contradiction
          · rintro rfl
            exact ⟨Or.inl rfl, hfe.symm⟩
        rw [hdiff] at hbas
        have hcl : f ∈ M✶.closure {e} := hbas.subset_closure (Set.mem_insert_of_mem e rfl)
        exact h f ⟨hcl, hfe⟩
  5. In the backward direction, assuming for contradiction that some f ≠ e lies in M✶.closure {e}, the singleton {e} is independent in M✶ and f ∉ {e}.

    Assuming M has no 2-element cocircuit containing e, suppose for contradiction that some f ≠ e satisfies f ∈ M✶.closure {e}. Since M is coloopless, the dual M✶ is loopless; as e ∈ M✶.E, e is a nonloop, so the singleton {e} is independent in M✶. Also, f ∉ {e} because f ≠ e.

    lines 33–36

    uses Matroid.isNonloop_of_loopless

      · intro h f ⟨hfcl, hfe⟩
        apply h
        have hI : M✶.Indep {e} := (Matroid.isNonloop_of_loopless he_dual).indep
        have heI : f ∉ ({e} : Set α) := by simp [hfe]
  6. The pair {e, f} forms a 2-element cocircuit containing e, which is a contradiction.

    For the single element x ∈ {e}, we have {e} \ {x} = ∅. The closure of the empty set in M✶ is the set of loops, which is empty because M✶ is loopless. Hence f ∉ M✶.closure ({e} \ {x}). Because {e} is independent in M✶, f ∉ {e}, f ∈ M✶.closure {e}, and f is not in the closure of any proper subset of {e}, the circuit extension criterion ensures that {f, e} = {e, f} is a circuit of M✶ (a cocircuit of M). Since f ≠ e, it has size 2 and contains e, contradicting the assumption that no such cocircuit exists.

    lines 37–47

    uses Set.sdiff_self, Matroid.closure_empty, Matroid.loops_eq_empty, Set.notMem_empty, Set.pair_comm, Set.mem_insert, Set.ncard_eq_two

        have h_min : ∀ x ∈ ({e} : Set α), f ∉ M✶.closure ({e} \ {x}) := by
          intro x hx
          simp only [Set.mem_singleton_iff] at hx
          subst hx
          rw [Set.sdiff_self, Matroid.closure_empty, Matroid.loops_eq_empty]
          exact Set.notMem_empty f
        have hcirc := hI.insert_isCircuit_of_forall heI hfcl h_min
        rw [Set.pair_comm] at hcirc
        refine ⟨{e, f}, hcirc, Set.mem_insert _ _, ?_⟩
        rw [Set.ncard_eq_two]
        exact ⟨e, f, fun h => hfe h.symm, rfl⟩
Matroid.delete_isRestriction
Deleting a set of elements from a matroid produces a restriction of that matroid.
Matroid.dual_delete
The dual of a matroid deletion is the contraction by the same set in 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.contract_loops_eq
The loops of a contraction M / C are the elements in the closure of C outside C, i.e., M.closure(C) \ C.
Set.eq_empty_iff_forall_notMem
A set is empty if and only if it contains no elements.
M.dual_ground
The ground set of the dual matroid M✶ is equal to the ground set of M.
Set.ncard_eq_two
A set has cardinality 2 if and only if it is an unordered pair of two distinct elements.
Set.pair_comm
Unordered pairs are commutative: {a, b} = {b, a}.
Set.mem_insert_of_mem
If an element belongs to a set s, it also belongs to {y} ∪ s.
Or.inl
A disjunction a ∨ b holds if its left disjunct a holds.
Matroid.isNonloop_of_loopless
Every element of the ground set of a loopless matroid is a nonloop.
Set.sdiff_self
The difference of any set with itself is empty: s \ s = ∅.
Matroid.closure_empty
The closure of the empty set in a matroid is its set of loops.
Matroid.loops_eq_empty
In a loopless matroid, the set of loops is empty.
Set.notMem_empty
No element belongs to the empty set.
Set.mem_insert
An element x belongs to {x} ∪ s.

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

/-- Deleting an element from a loopless and coloopless matroid produces a loopless matroid; moreover, it is coloopless if and only if the element belongs to no 2-element cocircuit. -/theorem matroid_delete_singleton_loopless_and_coloopless_iff    {α : Type*} (M : Matroid α) [M.Finite] [M.Loopless] [M✶.Loopless]    (e : α) (he : e ∈ M.E) :    (M.delete {e}).Loopless ∧    ((M.delete {e})✶.Loopless ↔ ¬ ∃ C, M.IsCocircuit C ∧ e ∈ C ∧ C.ncard = 2) := by  refine ⟨(Matroid.delete_isRestriction M {e}).loopless, ?_⟩  rw [Matroid.dual_delete, Matroid.loopless_iff, Matroid.contract_loops_eq, Set.eq_empty_iff_forall_notMem]  simp only [Set.mem_sdiff, Set.mem_singleton_iff]  have he_dual : e ∈ M✶.E := by rw [M.dual_ground]; exact he  constructor  · intro h ⟨C, hC, heC, hCcard⟩    obtain ⟨f, hfe, rfl⟩ : ∃ f, f ≠ e ∧ C = {e, f} := by      obtain ⟨x, y, hxy, rfl⟩ := Set.ncard_eq_two.mp hCcard      simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at heC      rcases heC with rfl | rfl      · exact ⟨y, hxy.symm, rfl⟩      · exact ⟨x, hxy, by rw [Set.pair_comm]⟩    have hmem : f ∈ ({e, f} : Set α) := Set.mem_insert_of_mem e rfl    have hbas := hC.sdiff_singleton_isBasis hmem    have hdiff : ({e, f} : Set α) \ {f} = {e} := by      ext x      simp only [Set.mem_sdiff, Set.mem_insert_iff, Set.mem_singleton_iff]      constructor      · rintro ⟨rfl | rfl, hne⟩        · rfl        · contradiction      · rintro rfl        exact ⟨Or.inl rfl, hfe.symm⟩    rw [hdiff] at hbas    have hcl : f ∈ M✶.closure {e} := hbas.subset_closure (Set.mem_insert_of_mem e rfl)    exact h f ⟨hcl, hfe⟩  · intro h f ⟨hfcl, hfe⟩    apply h    have hI : M✶.Indep {e} := (Matroid.isNonloop_of_loopless he_dual).indep    have heI : f ∉ ({e} : Set α) := by simp [hfe]    have h_min : ∀ x ∈ ({e} : Set α), f ∉ M✶.closure ({e} \ {x}) := by      intro x hx      simp only [Set.mem_singleton_iff] at hx      subst hx      rw [Set.sdiff_self, Matroid.closure_empty, Matroid.loops_eq_empty]      exact Set.notMem_empty f    have hcirc := hI.insert_isCircuit_of_forall heI hfcl h_min    rw [Set.pair_comm] at hcirc    refine ⟨{e, f}, hcirc, Set.mem_insert _ _, ?_⟩    rw [Set.ncard_eq_two]    exact ⟨e, f, fun h => hfe h.symm, rfl⟩
See it in the graphDiscuss this resultChallenge it