AFTD Auto-Formalizing Theoretical Domains

szf_multigraph_closure_double_loop

theoremverified

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.

  1. 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.

    lines 3–4

      ext v
      constructor
  2. 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`).

    lines 5–8

      · intro h
        induction h with
        | init v hv => simpa using hv
        | step u w huw _ _ => simp at huw
  3. 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`).

    lines 9–10

      · 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

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
See it in the graphDiscuss this resultChallenge it