zero_forcing_finset_iter_of_stable
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.
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.
uses
Finset.mem_union.mp,Finset.mem_filter.mp,ZeroForced.stepintro 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))
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.
uses
Function.iterate_succ_apply',step_extendsinduction k with | zero => simp [iter] | succ k ih => rw [iter, Function.iterate_succ_apply'] exact ih.trans (step_extends G _)
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.
uses
ZeroForced.init,Function.iterate_succ_apply',step_soundinduction 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
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.
uses
Finset.mem_union_right,Finset.mem_filter.mpr,Finset.mem_univintro 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
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.
uses
Finset.eq_univ_iff_forall.mpr,fixed_contains_forced,iter_extendsconstructor · 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)
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.
uses
iter_sound,Finset.mem_univ· intro h x apply iter_sound G S k x rw [h] exact Finset.mem_univ x
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.
uses
IN800FiniteClosure.certified_iffexact 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.
- The proof develops the theory inside a helper namespace IN800FiniteClosure using local names (step, iter, and certified_iff), and then establishes the main theorem zero_forcing_finset_iter_of_stable in one line by delegating to certified_iff, relying on the definitional equality between the local definitions and the global ones (zero_forcing_finset_step and zero_forcing_finset_iter).
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.
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