AFTD Auto-Formalizing Theoretical Domains

matroid_closure_subset_skew_zero_forcing_closure

theoremverified

Let V be a finite type ([Finite V]), let N : V → Set V be a symmetric neighborhood function satisfying u ∈ N v ↔ v ∈ N u for all u, v : V, and let M be a matroid on V with ground set M.E = Set.univ. If every circuit C of M is the neighborhood of some vertex v : V with N v = C (∀ C, M.IsCircuit C → ∃ v : V, N v = C), then for every subset S : Set V, the matroid closure is contained in the skew zero forcing closure: M.closure S ⊆ skew_zero_forcing_closure N S.

Statement

theorem matroid_closure_subset_skew_zero_forcing_closure {V : Type*} [Finite V] (N : V → Set V) (h_symm : ∀ u v : V, u ∈ N v ↔ v ∈ N u) (M : Matroid V) (hE : M.E = Set.univ) (h_circ : ∀ C, M.IsCircuit C → ∃ v : V, N v = C) (S : Set V) : M.closure S ⊆ skew_zero_forcing_closure N S
Source
arXiv:2611.15741 Proposition 2.10
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • skew_zero_forcing_closureThe skew zero forcing closure scl(S) of a subset S of vertices in a graph with neighborhood function N is the set of all vertices forced…
  • SkewZeroForcedThe skew zero forcing closure predicate on vertices V: a vertex is forced from an initial set S under neighborhood function N if it is in…

Read back from the Lean

Let $V$ be a finite type. Let $N : V \to \text{Set } V$ be a neighborhood function such that the relation is symmetric (for all $u, v \in V$, $u \in N(v) \leftrightarrow v \in N(u)$). Let $M$ be a matroid on $V$ whose ground set is all of $V$ ($M.E = \text{Set.univ}$). Assume that every circuit of $M$ is the neighborhood of some vertex (for all $C \subseteq V$, if $C$ is a circuit of $M$, then there exists $v \in V$ such that $N(v) = C$). Then for every subset $S \subseteq V$, the matroid closure of $S$ in $M$ is a subset of the skew zero forcing closure of $S$ with respect to $N$.

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

To show that the matroid closure of S is contained in its skew zero forcing closure, let e belong to the matroid closure of S. If e is already in S, it is forced by definition. Otherwise, by the circuit characterization of matroid closure, there is a circuit C containing e with C ⊆ S ∪ {e}; because every circuit is the neighborhood of some vertex v, all neighbors of v other than e belong to S and are thus already forced, allowing v to force e in a single step.

  1. To prove M.closure S ⊆ skew_zero_forcing_closure N S, it suffices to show that an arbitrary element e ∈ M.closure S is skew-zero-forced.

    We introduce an arbitrary element e and the hypothesis that e belongs to the closure of S. (The assumptions of symmetry and universal ground set are also acknowledged here.)

    lines 3–5

      have _ := h_symm
      have _ := hE
      intro e he
  2. If e ∈ S, then e is in the skew zero forcing closure.

    We perform a case analysis on whether e ∈ S. If e ∈ S, it is forced immediately by the base case of the inductive definition of skew zero forcing (SkewZeroForced.init).

    lines 6–7

    uses SkewZeroForced.init

      by_cases heS : e ∈ S
      · exact SkewZeroForced.init e heS
  3. If e ∉ S, there exists a vertex v such that e ∈ N v and N v ⊆ S ∪ {e}.

    Since e ∉ S and e is in the matroid closure of S, by Matroid.mem_closure_iff_exists_isCircuit there exists a circuit C ⊆ S ∪ {e} containing e. By the hypothesis that every circuit is a neighborhood (h_circ), C = N v for some vertex v. Substituting this neighborhood for C gives e ∈ N v and N v ⊆ S ∪ {e}.

    lines 8–11

    uses Matroid.mem_closure_iff_exists_isCircuit

      · rw [Matroid.mem_closure_iff_exists_isCircuit heS] at he
        obtain ⟨C, hCsub, hC, heC⟩ := he
        obtain ⟨v, hv⟩ := h_circ C hC
        rw [← hv] at heC hCsub
  4. The vertex v forces e, so e belongs to the skew zero forcing closure.

    We apply the forcing step rule at v to force e (SkewZeroForced.step): e is a neighbor of v, and for any other neighbor x ∈ N v with x ≠ e, the inclusion N v ⊆ S ∪ {e} implies that x must be in S (the alternative x = e is ruled out by False.elim). Thus each other neighbor x is initially forced (SkewZeroForced.init). Because all other neighbors of v are forced, v forces e, placing e in the skew zero forcing closure.

    lines 12–21

    uses SkewZeroForced.step, False.elim, SkewZeroForced.init

        have h_step : SkewZeroForced N S e := by
          apply SkewZeroForced.step v e heC
          intro x hx hxne
          have hxS : x ∈ S := by
            have := hCsub hx
            cases this with
            | inl h => exact False.elim (hxne h)
            | inr h => exact h
          exact SkewZeroForced.init x hxS
        exact h_step
SkewZeroForced.init
Any element of the initial set S is skew-zero-forced.
Matroid.mem_closure_iff_exists_isCircuit
For an element e not in X, e belongs to the matroid closure of X if and only if there exists a circuit C ⊆ X ∪ {e} containing e.
SkewZeroForced.step
If w is a neighbor of u and every other neighbor of u is already forced, then w becomes forced.
False.elim
From a contradiction (a proof of False), any proposition follows.

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

/-- Matroid closure is contained in skew zero forcing closure when every circuit is a neighborhood. -/theorem matroid_closure_subset_skew_zero_forcing_closure {V : Type*} [Finite V] (N : V → Set V) (h_symm : ∀ u v : V, u ∈ N v ↔ v ∈ N u) (M : Matroid V) (hE : M.E = Set.univ) (h_circ : ∀ C, M.IsCircuit C → ∃ v : V, N v = C) (S : Set V) : M.closure S ⊆ skew_zero_forcing_closure N S := by  have _ := h_symm  have _ := hE  intro e he  by_cases heS : e ∈ S  · exact SkewZeroForced.init e heS  · rw [Matroid.mem_closure_iff_exists_isCircuit heS] at he    obtain ⟨C, hCsub, hC, heC⟩ := he    obtain ⟨v, hv⟩ := h_circ C hC    rw [← hv] at heC hCsub    have h_step : SkewZeroForced N S e := by      apply SkewZeroForced.step v e heC      intro x hx hxne      have hxS : x ∈ S := by        have := hCsub hx        cases this with        | inl h => exact False.elim (hxne h)        | inr h => exact h      exact SkewZeroForced.init x hxS    exact h_step
See it in the graphDiscuss this resultChallenge it