AFTD Auto-Formalizing Theoretical Domains

matroid_realization_via_circuit_neighborhoods_szf

theoremverifiedformalization

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. Suppose that 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), and 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 equals the matroid closure: skew_zero_forcing_closure N S = M.closure S.

Statement

theorem matroid_realization_via_circuit_neighborhoods_szf {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) (h_cyc : ∀ v : V, Matroid.IsCyclic M (N v)) (S : Set V) : skew_zero_forcing_closure N S = M.closure S
Formalizes
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 that is symmetric (for all $u, v \in V$, $u \in N(v) \iff v \in N(u)$). Let $M$ be a matroid on $V$ whose ground set is the full type ($M.E = \text{Set.univ}$). Suppose that: 1. Every circuit of $M$ is the neighborhood of some element: for every $C \subseteq V$, if $C$ is a circuit of $M$ (M.IsCircuit C), then there exists $v \in V$ such that $N(v) = C$. 2. For every $v \in V$, the neighborhood $N(v)$ is a cyclic set of $M$ (Matroid.IsCyclic M (N v)). Then for any subset $S \subseteq V$, the skew zero forcing closure of $S$ with respect to $N$ (skew_zero_forcing_closure N S) is equal to 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 mutual set inclusion. For the forward inclusion, induction on the definition of skew zero forcing shows that forced elements remain in the matroid closure: the base elements of S are already in the closure, and for any forcing step where u forces w', the cyclicity of N u provides a circuit C ⊆ N u containing w', placing w' in the closure of the remaining circuit elements which already lie in M.closure S. For the reverse inclusion, any element e in M.closure S \ S belongs to a circuit C ⊆ S ∪ {e}, which by hypothesis equals some vertex neighborhood N v; all other vertices of N v belong to S and are thus already forced, allowing v to force e in a single step.

  1. It suffices to show mutual inclusion between the skew zero forcing closure and the matroid closure of S.

    We reduce the set equality to two inclusions using anti-symmetry of subsets: skew_zero_forcing_closure N S ⊆ M.closure S and M.closure S ⊆ skew_zero_forcing_closure N S.

    lines 3–4

    uses Set.Subset.antisymm

      have _ := h_symm
      apply Set.Subset.antisymm
  2. Elements initially in S lie in the matroid closure of S.

    We prove the forward inclusion by induction on the definition of SkewZeroForced. For the base case, if v ∈ S, then v is in M.closure S because S is contained in the matroid ground set M.E, which equals univ.

    lines 5–8

    uses M.mem_closure_of_mem

      · rintro w hw
        induction hw with
        | init v hv =>
          exact M.mem_closure_of_mem hv (by simp [hE])
  3. In the inductive forcing step, there is a circuit contained in the neighborhood of the forcing vertex that contains the newly forced vertex.

    For the induction step, vertex w' ∈ N u is forced because all other neighbors in N u \ {w'} are already forced (and thus in M.closure S by induction hypothesis). By cyclicity of N u, N u is a union of circuits 𝒮. Because w' ∈ N u, there exists a circuit C ∈ 𝒮 containing w', and C ⊆ N u by the definition of set union.

    lines 9–17

    uses Set.mem_sUnion_of_mem

        | 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
  4. The newly forced vertex w' belongs to the matroid closure of S, completing the forward inclusion.

    Every element of C \ {w'} is a neighbor of u distinct from w', hence lies in M.closure S by the induction hypothesis, so C \ {w'} ⊆ M.closure S. Since C is a circuit containing w', w' lies in M.closure (C \ {w'}). Monotonicity and idempotence of the closure operator then imply w' ∈ M.closure (M.closure S) = M.closure S.

    lines 18–25

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

          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
  5. Any element of M.closure S that already belongs to S is in the skew zero forcing closure.

    For the reverse inclusion M.closure S ⊆ skew_zero_forcing_closure N S, we consider an arbitrary e ∈ M.closure S and split into cases on whether e ∈ S. If e ∈ S, it is forced immediately by the base rule.

    lines 26–28

    uses SkewZeroForced.init

      · intro e he
        by_cases heS : e ∈ S
        · exact SkewZeroForced.init e heS
  6. When e ∉ S, there is a vertex v whose neighborhood N v is a circuit containing e and contained in S ∪ {e}.

    By the circuit characterization of matroid closure, e ∈ M.closure S with e ∉ S implies the existence of a circuit C ⊆ S ∪ {e} with e ∈ C. By the circuit-neighborhood hypothesis, C = N v for some vertex v, so N v ⊆ S ∪ {e} and e ∈ N v.

    lines 29–32

    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
  7. The vertex e is skew zero forced by v, completing the reverse inclusion.

    To force e from v using SkewZeroForced.step, we show every other neighbor x ∈ N v \ {e} is already forced. Since N v ⊆ S ∪ {e} and x ≠ e, x must belong to S, so x is initially forced. Hence v forces e in one step, placing e in the skew zero forcing closure.

    lines 33–42

    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
Set.Subset.antisymm
Two sets are equal if each is a subset of the other.
M.mem_closure_of_mem
If X ⊆ M.E, every element of X belongs to the matroid closure of X.
Set.mem_sUnion_of_mem
If an element belongs to a member of a collection of sets, it belongs to the union of the collection.
hC_circ.mem_closure_sdiff_singleton_of_mem
If C is a circuit of a matroid and e ∈ C, then e is in the closure of C \ {e}.
M.closure_mono
The matroid closure operator is monotone: X ⊆ Y implies M.closure X ⊆ M.closure Y.
M.closure_closure
The matroid closure operator is idempotent: M.closure (M.closure X) = M.closure X.
SkewZeroForced.init
Every element of the initial set S is skew zero forced.
Matroid.mem_closure_iff_exists_isCircuit
For an element e ∉ X, e is in 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 skew zero forced, then w is skew zero forced.
False.elim
From a contradiction (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 realization via circuit neighborhoods in skew zero forcing (Proposition 2.10). -/theorem matroid_realization_via_circuit_neighborhoods_szf {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) (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  apply Set.Subset.antisymm  · rintro w hw    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  · 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