AFTD Auto-Formalizing Theoretical Domains

szf_multigraph_closure_single_loop

theoremverified

A vertex with a single loop and no other edges forces itself from the empty filled set.

Statement

theorem szf_multigraph_closure_single_loop :
    szf_multigraph_closure (fun (_ : Unit) (_ : Unit) => 1) ∅ = Set.univ
Source
sanity lemma for szf_multigraph_closure (arXiv:2611.15741 Section 1: a single loop lets a vertex self-force)
Verified
15 Nov 2026
Axioms
Quot.soundpropext
Built on 2
  • szf_multigraph_closureThe skew zero forcing closure scl(S) of a vertex set S in the multigraph with adjacency multiplicities μ: the set of vertices forced from…
  • SzfMultiForcedSkew zero forcing on a multigraph with adjacency multiplicities μ (μ u v = number of edges between u and v, μ u u = number of loops at u):…

The proof, explained

To show that the zero forcing closure of the empty set on a single-vertex multigraph with a single loop is the entire vertex set, it suffices by extensionality to show that the unique vertex is forced. The vertex forces itself via its single loop of multiplicity 1, as the requirement that all other neighbors be already forced holds vacuously because the vertex set has no other elements.

  1. To show that the closure is the universal set, it suffices to show that the unique vertex of Unit is forced from ∅.

    By set extensionality (`ext ⟨⟩`), two sets are equal if they contain the same elements. Since the vertex type is `Unit`, there is only the unique vertex `()` to consider. Simplifying with the definition of membership in the universal set (`Set.mem_univ`), the simplification rule `iff_true`, and unfolding the definition of `szf_multigraph_closure`, the goal reduces to showing that `()` is forced from the empty set.

    lines 3–4

    uses szf_multigraph_closure, Set.mem_univ, iff_true

      ext ⟨⟩
      simp only [szf_multigraph_closure, Set.mem_univ, iff_true]
  2. The unique vertex () is forced from the empty set in a single forcing step.

    We apply the forcing rule `SzfMultiForced.step` with u = () and w = (). The loop has multiplicity μ((), ()) = 1, which holds by reflexivity (`rfl`). For any other neighbor x, we must have x ≠ () and μ((), x) ≠ 0; but because `Unit` is a subsingleton, x = () by `Subsingleton.elim x ()`, contradicting x ≠ (). Thus the requirement on other neighbors holds vacuously, and () is forced.

    line 5

    uses SzfMultiForced.step, Subsingleton.elim

      refine SzfMultiForced.step () () rfl fun x hx => (hx (Subsingleton.elim x ())).elim
szf_multigraph_closure
The zero forcing closure of a set S in a multigraph with edge multiplicity function μ is the set of all vertices forced by S.
Set.mem_univ
Every element x of a type belongs to the universal set Set.univ.
iff_true
The proposition (p ↔ True) simplifies to p.
SzfMultiForced.step
A vertex u forces a vertex w if the edge multiplicity μ(u, w) is 1 and every other neighbor x ≠ w with μ(u, x) ≠ 0 is already forced.
Subsingleton.elim
In a subsingleton type, any two elements are equal: a = b.

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

theorem szf_multigraph_closure_single_loop :    szf_multigraph_closure (fun (_ : Unit) (_ : Unit) => 1) ∅ = Set.univ := by  ext ⟨⟩  simp only [szf_multigraph_closure, Set.mem_univ, iff_true]  refine SzfMultiForced.step () () rfl fun x hx => (hx (Subsingleton.elim x ())).elim
See it in the graphDiscuss this resultChallenge it