szf_multigraph_closure_double_loop
A vertex with a double loop and no other edges is not forced from the empty filled set.
Statement
theorem szf_multigraph_closure_double_loop : szf_multigraph_closure (fun (_ : Unit) (_ : Unit) => 2) ∅ = ∅
- Source
- sanity lemma for szf_multigraph_closure (arXiv:2611.15741 Section 1: a double loop blocks self-forcing)
- 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
We show by set extensionality that the zero forcing closure of the empty set on a single vertex with a double loop is empty. For the forward inclusion, any vertex in the closure must either start in the initial set or be forced along an edge of multiplicity 1 by induction on the forcing relation. Neither case can occur because the initial set is empty and the edge has multiplicity 2 (contradicting $2 = 1$). The reverse inclusion holds vacuously as the empty set has no elements.
It suffices to show that an arbitrary vertex $v$ is in the closure if and only if $v \in \emptyset$.
Set extensionality (`ext v`) reduces equality of the closure with the empty set to showing that both sets have the same elements. Splitting the biconditional (`constructor`) separates this into two inclusions: showing that any forced vertex must belong to $\emptyset$, and conversely that any element of $\emptyset$ is forced.
ext v constructor
No vertex is forced from $\emptyset$, establishing the forward inclusion.
We assume $v$ belongs to the closure (`intro h`) and proceed by induction on the definition of `SzfMultiForced` (`induction h with`). In the base case (`init`), $v$ must belong to the initial set $\emptyset$ (`hv`), which is impossible (`simpa using hv`). In the inductive step (`step`), forcing $w$ via $u$ requires the edge between them to have multiplicity 1 (`huw : 2 = 1`). Since the graph has edge multiplicity 2 everywhere, this yields $2 = 1$, which is an immediate numerical contradiction (`simp at huw`).
· intro h induction h with | init v hv => simpa using hv | step u w huw _ _ => simp at huw
The reverse inclusion holds: any element of $\emptyset$ belongs to the closure.
Assuming $v \in \emptyset$ (`intro h`), the premise is contradictory because the empty set has no elements, so the goal is solved vacuously (`simpa using h`).
· intro h simpa using h
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_double_loop : szf_multigraph_closure (fun (_ : Unit) (_ : Unit) => 2) ∅ = ∅ := by ext v constructor · intro h induction h with | init v hv => simpa using hv | step u w huw _ _ => simp at huw · intro h simpa using h