AFTD Auto-Formalizing Theoretical Domains

zero_forcing_finset_iter_of_stable

theoremverified

If a finite parallel forcing iteration has stabilized, the original blue set is zero forcing exactly when the stabilized set is all vertices.

Statement

theorem zero_forcing_finset_iter_of_stable {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (S : Finset V) (k : ℕ) (hstable : zero_forcing_finset_step G (zero_forcing_finset_iter G S k) = zero_forcing_finset_iter G S k) : is_zero_forcing_set G (S : Set V) ↔ zero_forcing_finset_iter G S k = Finset.univ
Source
Filed by the prover as a step towards another result
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • zero_forcing_finset_stepOne executable parallel zero forcing step from a finite blue set: include each vertex with a blue neighbor whose other neighbors are blue.
  • zero_forcing_finset_iterThe finite blue set obtained by iterating the executable parallel zero forcing step k times.
  • 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.
Used by 1
  • zero_forcing_finset_iter_decidesA blue set is zero forcing exactly when the executable parallel forcing process colors every vertex after at most the number of vertices…

The proof, explained

Once a parallel zero-forcing process on a finite graph reaches a fixed point, the initial set S is zero-forcing if and only if the fixed point contains all vertices. The backward direction (soundness) holds because every vertex added at any iteration is zero-forced by induction on the number of steps. The forward direction (completeness) holds because any fixed point containing S must contain the entire zero-forcing closure of S, proved by induction on the derivation of zero-forced vertices.

  1. Any vertex added in a single parallel forcing step is zero-forced from S, provided all vertices currently in the set are zero-forced.

    Let x ∈ step(G, B). By definition of union (Finset.mem_union.mp), either x ∈ B or x is newly forced. If x ∈ B, it is zero-forced by hypothesis hB. If x is newly forced, the filter condition (Finset.mem_filter.mp) gives an active neighbor u ∈ B with G.Adj u x whose other neighbors all belong to B. Since u and all other neighbors of u are in B and thus zero-forced by hB, ZeroForced.step applies to show x is zero-forced.

    lines 21–25

    uses Finset.mem_union.mp, Finset.mem_filter.mp, ZeroForced.step

      intro x hx
      rcases Finset.mem_union.mp hx with hx | hx
      · exact hB x hx
      · obtain ⟨u, hu, hux, hother⟩ := (Finset.mem_filter.mp hx).2
        exact ZeroForced.step u x (hB u hu) hux (fun y huy hyx => hB y (hother y huy hyx))
  2. The initial set S is contained in every iterate of the parallel forcing process.

    By induction on k. The base case k = 0 is immediate because iter(G, S, 0) = S. For the inductive step, iter(G, S, k + 1) = step(G, iter(G, S, k)) by Function.iterate_succ_apply'. The induction hypothesis gives S ⊆ iter(G, S, k), and step_extends shows that iter(G, S, k) ⊆ step(G, iter(G, S, k)); transitivity of subset inclusion completes the step.

    lines 29–33

    uses Function.iterate_succ_apply', step_extends

      induction k with
      | zero => simp [iter]
      | succ k ih =>
        rw [iter, Function.iterate_succ_apply']
        exact ih.trans (step_extends G _)
  3. Every vertex in the k-th parallel iterate is zero-forced from S.

    By induction on k. For k = 0, every x ∈ iter(G, S, 0) = S is zero-forced by ZeroForced.init. For the inductive step, iter(G, S, k + 1) = step(G, iter(G, S, k)) by Function.iterate_succ_apply'. Applying step_sound with the inductive hypothesis ih confirms that every vertex in the next iterate remains zero-forced.

    lines 38–44

    uses ZeroForced.init, Function.iterate_succ_apply', step_sound

      induction k with
      | zero =>
        intro x hx
        exact ZeroForced.init x (by simpa [iter] using hx)
      | succ k ih =>
        rw [iter, Function.iterate_succ_apply']
        exact step_sound G S _ ih
  4. Any fixed point B of the parallel step operator that contains S contains every vertex zero-forced from S.

    By induction on the derivation of ZeroForced G S x. If x ∈ S, then x ∈ B because S ⊆ B. If w is forced by a vertex u ∈ B whose other neighbors are already in B, then w belongs to step(G, B) by the forcing condition (via Finset.mem_union_right, Finset.mem_filter.mpr, and Finset.mem_univ). Because B is a fixed point of step (hfix), step(G, B) = B, so w ∈ B.

    lines 49–57

    uses Finset.mem_union_right, Finset.mem_filter.mpr, Finset.mem_univ

      intro x hx
      induction hx with
      | init x hx => exact hSB hx
      | step u w hu huw hother ihu ihother =>
        have hw : w ∈ step G B := by
          apply Finset.mem_union_right
          apply Finset.mem_filter.mpr
          exact ⟨Finset.mem_univ _, u, ihu, huw, fun x hux hxw => ihother x hux hxw⟩
        rwa [hfix] at hw
  5. If S is a zero-forcing set and the k-th iterate has stabilized, then the k-th iterate is the entire vertex set.

    Assume S is zero-forcing, meaning every vertex x is zero-forced from S. The k-th iterate contains S by iter_extends and is a fixed point by hypothesis hstable. By fixed_contains_forced, every vertex x of the graph belongs to iter(G, S, k). Therefore, by Finset.eq_univ_iff_forall.mpr, the iterate is Finset.univ.

    lines 63–67

    uses Finset.eq_univ_iff_forall.mpr, fixed_contains_forced, iter_extends

      constructor
      · intro h
        apply Finset.eq_univ_iff_forall.mpr
        intro x
        exact fixed_contains_forced G S _ (iter_extends G S k) hstable x (h x)
  6. If the k-th iterate is the entire vertex set, then S is a zero-forcing set.

    Assume iter(G, S, k) = Finset.univ. By iter_sound, every vertex in iter(G, S, k) is zero-forced from S. Since every vertex x belongs to Finset.univ (Finset.mem_univ), substituting the assumption shows that every vertex x is in iter(G, S, k) and is thus zero-forced.

    lines 68–71

    uses iter_sound, Finset.mem_univ

      · intro h x
        apply iter_sound G S k x
        rw [h]
        exact Finset.mem_univ x
  7. The original set S is zero-forcing if and only if the stabilized iterate equals the universal set.

    The top-level theorem zero_forcing_finset_iter_of_stable is an immediate consequence of IN800FiniteClosure.certified_iff, since the global definitions zero_forcing_finset_step and zero_forcing_finset_iter are definitionally equal to IN800FiniteClosure.step and IN800FiniteClosure.iter.

    line 76

    uses IN800FiniteClosure.certified_iff

      exact IN800FiniteClosure.certified_iff G S k hstable
Finset.mem_union.mp
If an element belongs to the union of two finite sets, it belongs to the first or to the second.
Finset.mem_filter.mp
If an element belongs to a filtered finite set, it belongs to the set and satisfies the filter predicate.
ZeroForced.step
If u is zero-forced, w is adjacent to u, and every neighbor of u other than w is already zero-forced, then w is zero-forced.
Function.iterate_succ_apply'
Applying a function n + 1 times equals applying the function to the n-fold iterate.
step_extends
A finite set is a subset of its image under one step of the parallel forcing rule.
ZeroForced.init
Every vertex in the initial set S is zero-forced from S.
step_sound
If all vertices in a set B are zero-forced from S, then all vertices in step(B) are also zero-forced from S.
Finset.mem_union_right
If an element belongs to t, then it belongs to s ∪ t.
Finset.mem_filter.mpr
If an element belongs to a finite set and satisfies a predicate, it belongs to the filtered subset.
Finset.mem_univ
Every element of a finite type belongs to the universal finite set of that type.
iter_extends
The initial set S is a subset of the k-th iterate iter(S, k) for any k.
fixed_contains_forced
If a set B contains S and is a fixed point of step, then B contains every vertex zero-forced from S.
Finset.eq_univ_iff_forall.mpr
A finite set equals the universal set if every element of the type belongs to it.
iter_sound
Every vertex in the k-th iterate iter(S, k) is zero-forced from S.
IN800FiniteClosure.certified_iff
If the k-th iterate of the parallel forcing step is a fixed point, then S is a zero-forcing set if and only if that k-th iterate is the universal set.

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

set_option maxRecDepth 8192set_option maxHeartbeats 8000000namespace IN800FiniteClosuredef step {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)    [DecidableRel G.Adj] (S : Finset V) : Finset V :=  S ∪ Finset.univ.filter (fun w => ∃ u ∈ S, G.Adj u w ∧ ∀ x, G.Adj u x → x ≠ w → x ∈ S)def iter {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)    [DecidableRel G.Adj] (S : Finset V) (k : ℕ) : Finset V :=  (step G)^[k] Slemma step_extends {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)    [DecidableRel G.Adj] (S : Finset V) : S ⊆ step G S := Finset.subset_union_leftlemma step_sound {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)    [DecidableRel G.Adj] (S B : Finset V)    (hB : ∀ x ∈ B, ZeroForced G (S : Set V) x) :    ∀ x ∈ step G B, ZeroForced G (S : Set V) x := by  intro x hx  rcases Finset.mem_union.mp hx with hx | hx  · exact hB x hx  · obtain ⟨u, hu, hux, hother⟩ := (Finset.mem_filter.mp hx).2    exact ZeroForced.step u x (hB u hu) hux (fun y huy hyx => hB y (hother y huy hyx))lemma iter_extends {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)    [DecidableRel G.Adj] (S : Finset V) (k : ℕ) : S ⊆ iter G S k := by  induction k with  | zero => simp [iter]  | succ k ih =>    rw [iter, Function.iterate_succ_apply']    exact ih.trans (step_extends G _)lemma iter_sound {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)    [DecidableRel G.Adj] (S : Finset V) (k : ℕ) :    ∀ x ∈ iter G S k, ZeroForced G (S : Set V) x := by  induction k with  | zero =>    intro x hx    exact ZeroForced.init x (by simpa [iter] using hx)  | succ k ih =>    rw [iter, Function.iterate_succ_apply']    exact step_sound G S _ ihlemma fixed_contains_forced {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)    [DecidableRel G.Adj] (S B : Finset V) (hSB : S ⊆ B) (hfix : step G B = B) :    ∀ x, ZeroForced G (S : Set V) x → x ∈ B := by  intro x hx  induction hx with  | init x hx => exact hSB hx  | step u w hu huw hother ihu ihother =>    have hw : w ∈ step G B := by      apply Finset.mem_union_right      apply Finset.mem_filter.mpr      exact ⟨Finset.mem_univ _, u, ihu, huw, fun x hux hxw => ihother x hux hxw⟩    rwa [hfix] at hwtheorem certified_iff {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)    [DecidableRel G.Adj] (S : Finset V) (k : ℕ)    (hstable : step G (iter G S k) = iter G S k) :    is_zero_forcing_set G (S : Set V) ↔ iter G S k = Finset.univ := by  constructor  · intro h    apply Finset.eq_univ_iff_forall.mpr    intro x    exact fixed_contains_forced G S _ (iter_extends G S k) hstable x (h x)  · intro h x    apply iter_sound G S k x    rw [h]    exact Finset.mem_univ xend IN800FiniteClosuretheorem zero_forcing_finset_iter_of_stable {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (S : Finset V) (k : ℕ) (hstable : zero_forcing_finset_step G (zero_forcing_finset_iter G S k) = zero_forcing_finset_iter G S k) : is_zero_forcing_set G (S : Set V) ↔ zero_forcing_finset_iter G S k = Finset.univ := by  exact IN800FiniteClosure.certified_iff G S k hstable
See it in the graphDiscuss this resultChallenge it