AFTD Auto-Formalizing Theoretical Domains

univ_is_zero_forcing_set

theoremverified

The full set of vertices of any graph G is a zero forcing set.

Statement

theorem univ_is_zero_forcing_set {V : Type*} (G : SimpleGraph V) :
    is_zero_forcing_set G Set.univ
Source
arXiv:2611.11352 Section 1
Verified
11 Nov 2026
Axioms
none — Lean reports it depends on no axioms
Built on 2
  • is_zero_forcing_setA set of vertices S is a zero forcing set of G if its zero forcing closure contains all vertices of G.
  • ZeroForcedThe zero forcing closure of an initial set S of blue vertices in G under the color change rule.

Read back from the Lean

For any type V and any simple graph G on V, the universal set Set.univ is a zero forcing set of G.

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

To show that the universal set of vertices is a zero forcing set, it suffices to show that every vertex in the graph is zero forced. Because every vertex trivially belongs to the universal set, each vertex is already forced at the initial step by the base case of the inductive definition of zero forcing.

  1. Every vertex of the graph is zero forced by the universal set.

    To show that the universal set is a zero forcing set, we must show that every vertex v is zero forced. An arbitrary vertex v belongs to the universal set by Set.mem_univ, and any vertex in the set is immediately zero forced by the base case constructor ZeroForced.init.

    lines 4–5

    uses ZeroForced.init, Set.mem_univ

      intro v
      exact ZeroForced.init v (Set.mem_univ v)
ZeroForced.init
Any vertex belonging to the initial set S is zero forced from S.
Set.mem_univ
Every element of a type belongs to the universal set of that type.

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

/-- Sanity lemma: the universal set is always a zero forcing set. -/theorem univ_is_zero_forcing_set {V : Type*} (G : SimpleGraph V) :    is_zero_forcing_set G Set.univ := by  intro v  exact ZeroForced.init v (Set.mem_univ v)
See it in the graphDiscuss this resultChallenge it