AFTD Auto-Formalizing Theoretical Domains

skew_zero_forcing_closure_subset_matroid_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 neighborhood N v is cyclic in M (∀ v : V, Matroid.IsCyclic M (N v)), then for every subset S : Set V, the skew zero forcing closure is contained in the matroid closure: skew_zero_forcing_closure N S ⊆ M.closure S.

Statement

theorem skew_zero_forcing_closure_subset_matroid_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_cyc : ∀ v : V, Matroid.IsCyclic M (N v)) (S : Set V) : skew_zero_forcing_closure N S ⊆ M.closure S
Source
arXiv:2611.15741 Proposition 2.10
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • Matroid.IsCyclicA subset X of the ground set of a matroid M is cyclic if it is a union of circuits of M.
  • 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 on $V$ such that $N$ is symmetric (for all $u, v \in V$, $u \in N(v) \iff v \in N(u)$). Let $M$ be a matroid on ground type $V$ whose ground set $M.E$ is all of $V$ ($M.E = \text{Set.univ}$). Assume that for every vertex $v \in V$, its neighborhood $N(v)$ is a cyclic set in $M$ (Matroid.IsCyclic M (N v)). Then for any subset $S \subseteq V$, the skew zero forcing closure of $S$ with respect to $N$ is a subset of the matroid closure of $S$ in $M$ (M.closure S).

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 proceeds by induction on the derivation showing that a vertex is skew-zero-forced from $S$. Initial vertices in $S$ trivially belong to the matroid closure because the ground set is universal. In the inductive step, when a vertex $w'$ is forced by $u$, the cyclic assumption guarantees that the neighborhood $N(u)$ is a union of circuits, so $w'$ belongs to some circuit $C \subseteq N(u)$; since every other vertex in $C$ is already in the closure by induction, the circuit property $w' \in M.\operatorname{closure}(C \setminus \{w'\})$ together with monotonicity and idempotence of the closure operator forces $w' \in M.\operatorname{closure}(S)$.

  1. To show that the skew zero forcing closure of $S$ is contained in $M.\operatorname{closure}(S)$, it suffices to prove by induction that every vertex forced from $S$ belongs to $M.\operatorname{closure}(S)$.

    We introduce an arbitrary vertex $w$ that is skew-zero-forced from $S$ and proceed by structural induction on the derivation of `SkewZeroForced N S w`.

    lines 3–5

      have _ := h_symm
      rintro w (hw : SkewZeroForced N S w)
      induction hw with
  2. Every element of the initial set $S$ belongs to $M.\operatorname{closure}(S)$.

    In the base case where $v \in S$, since the matroid ground set is the full universe ($M.E = \operatorname{Set.univ}$), $S \subseteq M.E$. Any element of $S$ therefore belongs to the matroid closure $M.\operatorname{closure}(S)$.

    lines 6–7

    uses M.mem_closure_of_mem

      | init v hv =>
        exact M.mem_closure_of_mem hv (by simp [hE])
  3. For a vertex $w'$ forced by $u$, there is a circuit $C \subseteq N(u)$ that contains $w'$.

    In the induction step, $w' \in N(u)$ is forced by $u$, meaning all other neighbors $x \in N(u) \setminus \{w'\}$ satisfy the induction hypothesis and lie in $M.\operatorname{closure}(S)$. Since $N(u)$ is cyclic in $M$, it is a union of circuits $\mathcal{S}$. Because $w' \in N(u)$, there is some circuit $C \in \mathcal{S}$ containing $w'$.

    lines 8–12

      | step u w' hw' h_ih ih =>
        obtain ⟨𝒮, hC, hU⟩ := h_cyc u
        have hw'U : w' ∈ ⋃₀ 𝒮 := by rwa [← hU]
        obtain ⟨C, hCin, hw'C⟩ := hw'U
        have hC_circ : M.IsCircuit C := hC C hCin
  4. The circuit $C$ is contained in the neighborhood $N(u)$.

    Since $N(u)$ is the union of the family $\mathcal{S}$ and $C \in \mathcal{S}$, any element of $C$ belongs to $\bigcup \mathcal{S} = N(u)$.

    lines 13–16

    uses Set.mem_sUnion_of_mem

        have hC_sub : C ⊆ N u := by
          intro x hx
          rw [hU]
          exact Set.mem_sUnion_of_mem hx hCin
  5. The rest of the circuit $C \setminus \{w'\}$ is contained in $M.\operatorname{closure}(S)$.

    Every element $x \in C \setminus \{w'\}$ belongs to $N(u)$ (since $C \subseteq N(u)$) and is distinct from $w'$. By the induction hypothesis, every such neighbor already belongs to $M.\operatorname{closure}(S)$.

    lines 17–19

        have h_diff_sub : C \ {w'} ⊆ M.closure S := by
          intro x hx
          exact ih x (hC_sub hx.1) hx.2
  6. The forced vertex $w'$ belongs to $M.\operatorname{closure}(S)$.

    Because $C$ is a circuit containing $w'$, $w'$ is in the closure of $C \setminus \{w'\}$. By monotonicity of the closure operator applied to $C \setminus \{w'\} \subseteq M.\operatorname{closure}(S)$, we have $M.\operatorname{closure}(C \setminus \{w'\}) \subseteq M.\operatorname{closure}(M.\operatorname{closure}(S))$. Since the closure operator is idempotent, the right-hand side is $M.\operatorname{closure}(S)$, concluding that $w' \in M.\operatorname{closure}(S)$.

    lines 20–24

    uses hC_circ.mem_closure_sdiff_singleton_of_mem, M.closure_mono, M.closure_closure

        have hw'_cl : w' ∈ M.closure (C \ {w'}) :=
          hC_circ.mem_closure_sdiff_singleton_of_mem hw'C
        have h_le := M.closure_mono h_diff_sub
        rw [M.closure_closure S] at h_le
        exact h_le hw'_cl
M.mem_closure_of_mem
An element of a subset $X$ of the ground set belongs to the closure of $X$.
Set.mem_sUnion_of_mem
An element of a set in a collection of sets belongs to the union of that collection.
hC_circ.mem_closure_sdiff_singleton_of_mem
For any circuit $C$ and element $e \in C$, $e$ belongs to the closure of $C \setminus \{e\}$.
M.closure_mono
The matroid closure operator is monotone: if $X \subseteq Y$, then $\operatorname{closure}(X) \subseteq \operatorname{closure}(Y)$.
M.closure_closure
The matroid closure operator is idempotent: $\operatorname{closure}(\operatorname{closure}(X)) = \operatorname{closure}(X)$.

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

/-- Skew zero forcing closure is contained in matroid closure when every neighborhood is cyclic. -/theorem skew_zero_forcing_closure_subset_matroid_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_cyc : ∀ v : V, Matroid.IsCyclic M (N v)) (S : Set V) : skew_zero_forcing_closure N S ⊆ M.closure S := by  have _ := h_symm  rintro w (hw : SkewZeroForced N S w)  induction hw with  | init v hv =>    exact M.mem_closure_of_mem hv (by simp [hE])  | step u w' hw' h_ih ih =>    obtain ⟨𝒮, hC, hU⟩ := h_cyc u    have hw'U : w' ∈ ⋃₀ 𝒮 := by rwa [← hU]    obtain ⟨C, hCin, hw'C⟩ := hw'U    have hC_circ : M.IsCircuit C := hC C hCin    have hC_sub : C ⊆ N u := by      intro x hx      rw [hU]      exact Set.mem_sUnion_of_mem hx hCin    have h_diff_sub : C \ {w'} ⊆ M.closure S := by      intro x hx      exact ih x (hC_sub hx.1) hx.2    have hw'_cl : w' ∈ M.closure (C \ {w'}) :=      hC_circ.mem_closure_sdiff_singleton_of_mem hw'C    have h_le := M.closure_mono h_diff_sub    rw [M.closure_closure S] at h_le    exact h_le hw'_cl
See it in the graphDiscuss this resultChallenge it