zero_forcing_boundary_cl_le
Let G be a simple graph and S a finite subset of vertices. Then the extended cardinality of the boundary of the closure cl(S) is at most the extended cardinality of S.
Statement
theorem zero_forcing_boundary_cl_le {V : Type*} (G : SimpleGraph V) {S : Set V} (hS : S.Finite) : (zero_forcing_boundary G (zero_forcing_cl G S)).encard ≤ S.encard
- Formalizes
- arXiv:2611.13244, Proposition 2.9 -- Stabilization of the zero forcing number of generalized Petersen graphs
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- zero_forcing_boundaryFor a simple graph G and a subset X of vertices, the boundary ∂X is the set of all vertices x in X that have a neighbor outside X.
- zero_forcing_clThe zero forcing closure cl(S) of a subset S of vertices in a simple graph G is the union over all natural numbers i of B_i.
- zero_forcing_boundary_monoLet G be a simple graph and S a finite subset of vertices. Then for every natural number i, the extended cardinality of the boundary…
- zero_forcing_seqThe sequence of vertex subsets B_i in a simple graph G starting with B_0 = S and iteratively defined by adding all unique outside…
- Used by 1
- zero_forcing_boundary_monotonicityLet G be a simple graph, and let S be a finite subset of vertices. In the zero forcing sequence B_0 = S ⊆ B_1 ⊆ ..., the extended…
Read back from the Lean
For any type V, any simple graph G on V, and any finite set of vertices S : Set V (with hS : S.Finite), the extended cardinality (encard) of the zero-forcing boundary of the zero-forcing closure of S with respect to G is less than or equal to the extended cardinality of S.
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 bound the extended cardinality of the boundary of the zero-forcing closure cl(S) by |S| for a finite set S, the proof reduces the goal to bounding the size of every finite subset t ⊆ ∂(cl(S)) by |S|. Because t is finite and cl(S) is the union of the zero-forcing sequence stages S_N, t is contained in some stage S_N, and any boundary point of cl(S) in S_N must also lie in the boundary of S_N. The claim then follows because the boundary size is non-increasing along the sequence, meaning the boundary of S_N has cardinality at most |S_0| ≤ |S|.
If a set s is finite and all its finite subsets have cardinality at most k, then the extended cardinality of s is at most k.
A set has extended cardinality at most k if and only if it is finite and its cardinality is at most k, by Set.encard_le_coe_iff_finite_ncard_le. Under the assumption that s is finite, we view s as a finite set (Finset) and apply the hypothesis that all finite subsets have cardinality at most k. Rewriting with Set.ncard_eq_toFinset_card yields |s| ≤ k.
uses
Set.encard_le_coe_iff_finite_ncard_le,Set.ncard_eq_toFinset_cardlemma zero_forcing_boundary_cl_le_encard_le_coe_of_forall_finset {α : Type*} (s : Set α) (k : ℕ) (h : ∀ (t : Finset α), (t : Set α) ⊆ s → t.card ≤ k) : s.encard ≤ k := by by_cases hfin : s.Finite · rw [Set.encard_le_coe_iff_finite_ncard_le] refine ⟨hfin, ?_⟩ have ht : (hfin.toFinset : Set α) ⊆ s := by rw [hfin.coe_toFinset] have := h hfin.toFinset ht rwa [← Set.ncard_eq_toFinset_card s hfin] at this
A set cannot be infinite if all its finite subsets have cardinality bounded by k. automation
If s were infinite, Set.Infinite.exists_subset_card_eq would yield a finite subset of cardinality k + 1. The hypothesis then gives k + 1 ≤ k, an arithmetic contradiction detected and closed by omega.
uses
Set.Infinite.exists_subset_card_eq· obtain ⟨t, ht_sub, ht_card⟩ := Set.Infinite.exists_subset_card_eq hfin (k + 1) have := h t ht_sub omega
The zero-forcing sequence n ↦ S_n is monotone under set inclusion.
By monotone_nat_of_le_succ, monotonicity on ℕ reduces to showing S_n ⊆ S_{n+1} for all n. By definition, S_{n+1} is the union of S_n and the vertices forced at that step, so the inclusion S_n ⊆ S_{n+1} holds immediately by Set.subset_union_left.
uses
monotone_nat_of_le_succ,Set.subset_union_leftlemma zero_forcing_boundary_cl_le_seq_mono {V : Type*} (G : SimpleGraph V) (S : Set V) : Monotone (zero_forcing_seq G S) := by apply monotone_nat_of_le_succ intro n change zero_forcing_seq G S n ⊆ zero_forcing_seq G S (n + 1) rw [zero_forcing_seq] exact Set.subset_union_left
The empty set is contained in the initial stage of the zero-forcing sequence. automation
To show that any finite subset of the closure is contained in some stage of the sequence, we proceed by induction on finite sets using Finset.induction_on. For the base case t = ∅, choosing N = 0 gives ∅ ⊆ S_0, which simp closes.
uses
Finset.induction_onlemma zero_forcing_boundary_cl_le_exists_seq_subset_of_finset {V : Type*} (G : SimpleGraph V) (S : Set V) (t : Finset V) (ht : (t : Set V) ⊆ zero_forcing_cl G S) : ∃ N : ℕ, (t : Set V) ⊆ zero_forcing_seq G S N := by classical induction t using Finset.induction_on with | empty => refine ⟨0, ?_⟩ simp
Any finite subset t of the zero-forcing closure cl(S) is contained in S_N for some stage N.
For the inductive step t = {a} ∪ s, the induction hypothesis gives s ⊆ S_{N'} for some N'. Since a ∈ cl(S) = ⋃_i S_i, Set.mem_iUnion gives a stage n_a with a ∈ S_{n_a}. Taking N = max(n_a, N'), monotonicity of the sequence (zero_forcing_boundary_cl_le_seq_mono) with le_max_left and le_max_right ensures both a ∈ S_N and s ⊆ S_N, so {a} ∪ s ⊆ S_N.
uses
Finset.coe_insert,Set.insert_subset_iff,Set.mem_iUnion,zero_forcing_boundary_cl_le_seq_mono,le_max_left,le_max_right| insert a s ha ih => rw [Finset.coe_insert, Set.insert_subset_iff] at ht obtain ⟨N', hN'⟩ := ih ht.2 have ha_cl := ht.1 rw [zero_forcing_cl, Set.mem_iUnion] at ha_cl obtain ⟨na, hna⟩ := ha_cl refine ⟨max na N', ?_⟩ rw [Finset.coe_insert, Set.insert_subset_iff] refine ⟨zero_forcing_boundary_cl_le_seq_mono G S (le_max_left na N') hna, ?_⟩ exact hN'.trans (zero_forcing_boundary_cl_le_seq_mono G S (le_max_right na N'))If a subset t of the boundary of cl(S) is contained in S_N, then t is contained in the boundary of S_N.
For any x ∈ t, we have x ∈ S_N. Since x is in the boundary of cl(S), it has a neighbor y ∉ cl(S). If y were in S_N, it would belong to ⋃_i S_i = cl(S) by Set.mem_iUnion.mpr, contradicting y ∉ cl(S). Thus y ∉ S_N, which shows x is in the boundary of S_N.
uses
Set.mem_iUnion.mprlemma zero_forcing_boundary_cl_le_subset_boundary_seq_of_subset_cl {V : Type*} (G : SimpleGraph V) (S : Set V) (N : ℕ) {t : Set V} (ht : t ⊆ zero_forcing_boundary G (zero_forcing_cl G S)) (htN : t ⊆ zero_forcing_seq G S N) : t ⊆ zero_forcing_boundary G (zero_forcing_seq G S N) := by intro x hx have hxb := ht hx rw [zero_forcing_boundary] at hxb ⊢ rcases hxb with ⟨-, y, hy_adj, hy_not⟩ refine ⟨htN hx, y, hy_adj, ?_⟩ intro hy_in apply hy_not rw [zero_forcing_cl] exact Set.mem_iUnion.mpr ⟨N, hy_in⟩
For any N, the boundary of the stage S_N has extended cardinality at most |S|.
By induction on N: at N = 0, S_0 = S and the boundary of S is a subset of S, so its cardinality is at most |S| by Set.encard_le_encard. For the inductive step, zero_forcing_boundary_mono shows the boundary cardinality does not increase from stage n to n + 1, so |∂(S_{n+1})| ≤ |∂(S_n)| ≤ |S| by transitivity with the induction hypothesis.
uses
Set.encard_le_encard,zero_forcing_boundary_monolemma zero_forcing_boundary_cl_le_seq_le {V : Type*} (G : SimpleGraph V) {S : Set V} (hS : S.Finite) (N : ℕ) : (zero_forcing_boundary G (zero_forcing_seq G S N)).encard ≤ S.encard := by induction N with | zero => change (zero_forcing_boundary G S).encard ≤ S.encard apply Set.encard_le_encard intro x hx rw [zero_forcing_boundary] at hx exact hx.1 | succ n ih => exact (zero_forcing_boundary_mono G hS n).trans ih
To bound |∂(cl(S))| ≤ |S|, it suffices to show that every finite subset t ⊆ ∂(cl(S)) satisfies |t| ≤ |S|, and any such t is contained in cl(S).
Because S is finite, its extended cardinality is a natural number k. By zero_forcing_boundary_cl_le_encard_le_coe_of_forall_finset, bounding the extended cardinality of ∂(cl(S)) by k reduces to showing every finite subset t ⊆ ∂(cl(S)) satisfies |t| ≤ k. By definition of the boundary, every vertex in t belongs to cl(S), so t ⊆ cl(S).
uses
zero_forcing_boundary_cl_le_encard_le_coe_of_forall_finset/-- The boundary of the zero forcing closure of a finite set S has cardinality at most |S|. -/ theorem zero_forcing_boundary_cl_le {V : Type*} (G : SimpleGraph V) {S : Set V} (hS : S.Finite) : (zero_forcing_boundary G (zero_forcing_cl G S)).encard ≤ S.encard := by obtain ⟨k, hk⟩ := hS.exists_encard_eq_coe rw [hk] apply zero_forcing_boundary_cl_le_encard_le_coe_of_forall_finset intro t ht have ht_cl : (t : Set V) ⊆ zero_forcing_cl G S := by intro x hx have := ht hx rw [zero_forcing_boundary] at this exact this.1
Every finite subset t ⊆ ∂(cl(S)) has cardinality at most |S|, concluding that |∂(cl(S))| ≤ |S|.
Since t is a finite subset of cl(S), zero_forcing_boundary_cl_le_exists_seq_subset_of_finset gives an index N such that t ⊆ S_N. Then zero_forcing_boundary_cl_le_subset_boundary_seq_of_subset_cl places t in the boundary of S_N, yielding |t| ≤ |∂(S_N)| via Set.encard_le_encard and Set.encard_coe_eq_coe_finsetCard. Since |∂(S_N)| ≤ |S| = k by zero_forcing_boundary_cl_le_seq_le, we conclude |t| ≤ k by Nat.cast_le.
uses
zero_forcing_boundary_cl_le_exists_seq_subset_of_finset,zero_forcing_boundary_cl_le_subset_boundary_seq_of_subset_cl,Set.encard_le_encard,Set.encard_coe_eq_coe_finsetCard,zero_forcing_boundary_cl_le_seq_le,Nat.cast_leobtain ⟨N, hN⟩ := zero_forcing_boundary_cl_le_exists_seq_subset_of_finset G S t ht_cl have ht_seq := zero_forcing_boundary_cl_le_subset_boundary_seq_of_subset_cl G S N ht hN have hle := Set.encard_le_encard ht_seq rw [Set.encard_coe_eq_coe_finsetCard] at hle have h_bound := hle.trans (zero_forcing_boundary_cl_le_seq_le G hS N) rw [hk, Nat.cast_le] at h_bound exact h_bound
Set.encard_le_coe_iff_finite_ncard_le- A set has extended cardinality at most a natural number k if and only if it is finite and its cardinality is at most k.
Set.ncard_eq_toFinset_card- The cardinality of a finite set equals the cardinality of its corresponding finite set representation.
Set.Infinite.exists_subset_card_eq- Every infinite set has a finite subset of any specified cardinality.
monotone_nat_of_le_succ- A sequence indexed by natural numbers is monotone if each term is less than or equal to its successor.
Set.subset_union_left- Every set is a subset of its union with any other set.
Finset.induction_on- Induction principle for finite sets: a property holds for all finite sets if it holds for the empty set and is preserved under adjoining a new element.
Finset.coe_insert- The set coercion of inserting an element into a finite set is the insertion of that element into the coerced set.
Set.insert_subset_iff- Inserting an element into a set yields a subset of t if and only if the element belongs to t and the original set is a subset of t.
Set.mem_iUnion- An element belongs to an indexed union if and only if it belongs to at least one set in the family.
zero_forcing_boundary_cl_le_seq_mono- The sequence of sets produced by zero forcing is monotone under set inclusion.
le_max_left- Any value is less than or equal to the maximum of itself and another value.
le_max_right- Any value is less than or equal to the maximum of another value and itself.
Set.mem_iUnion.mpr- An element belongs to an indexed union if it belongs to a member of the family at some index.
Set.encard_le_encard- If one set is a subset of another, its extended cardinality is at most the extended cardinality of the other.
zero_forcing_boundary_mono- The extended cardinality of the boundary does not increase from any step to the next in the zero-forcing sequence.
zero_forcing_boundary_cl_le_encard_le_coe_of_forall_finset- If every finite subset of a set has cardinality at most k, then the extended cardinality of the set is at most k.
zero_forcing_boundary_cl_le_exists_seq_subset_of_finset- Every finite subset of the zero-forcing closure is contained in the sequence at some finite stage.
zero_forcing_boundary_cl_le_subset_boundary_seq_of_subset_cl- If a subset of the boundary of the closure is contained in a stage S_N, it is also contained in the boundary of S_N.
zero_forcing_boundary_cl_le_seq_le- For a finite initial set S, the boundary of any stage S_N in the zero-forcing sequence has extended cardinality at most |S|.
Set.encard_coe_eq_coe_finsetCard- The extended cardinality of a coerced finite set is equal to its finite cardinality cast to extended natural numbers.
Nat.cast_le- Inequality between natural numbers is preserved and reflected by coercion to extended natural numbers.
- On paper, one typically works directly with set cardinalities, but in Lean, the boundary and closure are subsets of a general vertex type that could be infinite. Thus the proof uses extended natural numbers (encard) and relies on the helper lemma that a set with all finite subsets of size at most k has encard at most k.
- The automation in step 2 (omega) resolves the linear arithmetic contradiction k + 1 ≤ k, and in step 4 (simp) verifies that the empty set is a subset of the initial stage.
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.
lemma zero_forcing_boundary_cl_le_encard_le_coe_of_forall_finset {α : Type*} (s : Set α) (k : ℕ) (h : ∀ (t : Finset α), (t : Set α) ⊆ s → t.card ≤ k) : s.encard ≤ k := by by_cases hfin : s.Finite · rw [Set.encard_le_coe_iff_finite_ncard_le] refine ⟨hfin, ?_⟩ have ht : (hfin.toFinset : Set α) ⊆ s := by rw [hfin.coe_toFinset] have := h hfin.toFinset ht rwa [← Set.ncard_eq_toFinset_card s hfin] at this · obtain ⟨t, ht_sub, ht_card⟩ := Set.Infinite.exists_subset_card_eq hfin (k + 1) have := h t ht_sub omegalemma zero_forcing_boundary_cl_le_seq_mono {V : Type*} (G : SimpleGraph V) (S : Set V) : Monotone (zero_forcing_seq G S) := by apply monotone_nat_of_le_succ intro n change zero_forcing_seq G S n ⊆ zero_forcing_seq G S (n + 1) rw [zero_forcing_seq] exact Set.subset_union_leftlemma zero_forcing_boundary_cl_le_exists_seq_subset_of_finset {V : Type*} (G : SimpleGraph V) (S : Set V) (t : Finset V) (ht : (t : Set V) ⊆ zero_forcing_cl G S) : ∃ N : ℕ, (t : Set V) ⊆ zero_forcing_seq G S N := by classical induction t using Finset.induction_on with | empty => refine ⟨0, ?_⟩ simp | insert a s ha ih => rw [Finset.coe_insert, Set.insert_subset_iff] at ht obtain ⟨N', hN'⟩ := ih ht.2 have ha_cl := ht.1 rw [zero_forcing_cl, Set.mem_iUnion] at ha_cl obtain ⟨na, hna⟩ := ha_cl refine ⟨max na N', ?_⟩ rw [Finset.coe_insert, Set.insert_subset_iff] refine ⟨zero_forcing_boundary_cl_le_seq_mono G S (le_max_left na N') hna, ?_⟩ exact hN'.trans (zero_forcing_boundary_cl_le_seq_mono G S (le_max_right na N'))lemma zero_forcing_boundary_cl_le_subset_boundary_seq_of_subset_cl {V : Type*} (G : SimpleGraph V) (S : Set V) (N : ℕ) {t : Set V} (ht : t ⊆ zero_forcing_boundary G (zero_forcing_cl G S)) (htN : t ⊆ zero_forcing_seq G S N) : t ⊆ zero_forcing_boundary G (zero_forcing_seq G S N) := by intro x hx have hxb := ht hx rw [zero_forcing_boundary] at hxb ⊢ rcases hxb with ⟨-, y, hy_adj, hy_not⟩ refine ⟨htN hx, y, hy_adj, ?_⟩ intro hy_in apply hy_not rw [zero_forcing_cl] exact Set.mem_iUnion.mpr ⟨N, hy_in⟩lemma zero_forcing_boundary_cl_le_seq_le {V : Type*} (G : SimpleGraph V) {S : Set V} (hS : S.Finite) (N : ℕ) : (zero_forcing_boundary G (zero_forcing_seq G S N)).encard ≤ S.encard := by induction N with | zero => change (zero_forcing_boundary G S).encard ≤ S.encard apply Set.encard_le_encard intro x hx rw [zero_forcing_boundary] at hx exact hx.1 | succ n ih => exact (zero_forcing_boundary_mono G hS n).trans ih/-- The boundary of the zero forcing closure of a finite set S has cardinality at most |S|. -/theorem zero_forcing_boundary_cl_le {V : Type*} (G : SimpleGraph V) {S : Set V} (hS : S.Finite) : (zero_forcing_boundary G (zero_forcing_cl G S)).encard ≤ S.encard := by obtain ⟨k, hk⟩ := hS.exists_encard_eq_coe rw [hk] apply zero_forcing_boundary_cl_le_encard_le_coe_of_forall_finset intro t ht have ht_cl : (t : Set V) ⊆ zero_forcing_cl G S := by intro x hx have := ht hx rw [zero_forcing_boundary] at this exact this.1 obtain ⟨N, hN⟩ := zero_forcing_boundary_cl_le_exists_seq_subset_of_finset G S t ht_cl have ht_seq := zero_forcing_boundary_cl_le_subset_boundary_seq_of_subset_cl G S N ht hN have hle := Set.encard_le_encard ht_seq rw [Set.encard_coe_eq_coe_finsetCard] at hle have h_bound := hle.trans (zero_forcing_boundary_cl_le_seq_le G hS N) rw [hk, Nat.cast_le] at h_bound exact h_bound