AFTD Auto-Formalizing Theoretical Domains

zero_forcing_boundary_cl_le

theoremverifiedformalization

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

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

    lines 1–8

    uses Set.encard_le_coe_iff_finite_ncard_le, Set.ncard_eq_toFinset_card

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

    lines 9–12

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

    lines 13–20

    uses monotone_nat_of_le_succ, Set.subset_union_left

    lemma 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
    
  4. 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.

    lines 21–28

    uses Finset.induction_on

    lemma 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
  5. 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.

    lines 29–39

    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'))
    
  6. 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.

    lines 40–53

    uses Set.mem_iUnion.mpr

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

    lines 54–66

    uses Set.encard_le_encard, zero_forcing_boundary_mono

    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
    
  8. 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).

    lines 67–77

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

    lines 78–84

    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_le

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

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

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