szf_multigraph_closure_single_loop
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.
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.
uses
szf_multigraph_closure,Set.mem_univ,iff_trueext ⟨⟩ simp only [szf_multigraph_closure, Set.mem_univ, iff_true]
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.
uses
SzfMultiForced.step,Subsingleton.elimrefine 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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