AFTD Auto-Formalizing Theoretical Domains

tree_zf_white_rank_pair_positive_correlation

theoremverified

There is a six-vertex tree and two vertices such that, among the four-element white sets whose complements are zero forcing, the events that these vertices are white have positive correlation.

Statement

theorem tree_zf_white_rank_pair_positive_correlation : ∃ (T : SimpleGraph (Fin 6)) (i j : Fin 6), T.IsTree ∧ i ≠ j ∧ (let family : Set (Finset (Fin 6)) := {W | W.card = 4 ∧ is_zero_forcing_set T ((Finset.univ \ W : Finset (Fin 6)) : Set (Fin 6))}; {W ∈ family | i ∈ W ∧ j ∈ W}.ncard * family.ncard > {W ∈ family | i ∈ W}.ncard * {W ∈ family | j ∈ W}.ncard)
Source
Filed by the prover as a step towards another result
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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.
  • zfs_compl_iff_no_stuckFor any finite graph G and finite T, the complement V\T is a zero forcing set precisely when T contains no nonempty "stuck" subset W, i.e.…
  • Arena.Reachable.transReachability is transitive.

The proof, explained

The theorem is established by an explicit witness: the graph G on six vertices {0, 1, 2, 3, 4, 5} with edges {0,1}, {1,2}, {0,3}, {0,5}, {3,4}, together with vertices 1 and 4. First, G is verified to be a tree by showing all vertices are reachable from 0 and checking that |E| + 1 = |V| = 6. Next, complement zero forcing sets of size 2 (corresponding to 4-element white sets) are characterized by avoiding forts, which makes membership decidable by finite exhaustive search. Exhaustive computation determines that the family contains 7 sets, with 5 containing vertex 1, 4 containing vertex 4, and 3 containing both. Finally, positive correlation is verified by the numerical inequality 3 * 7 = 21 > 20 = 5 * 4.

  1. The graph G on vertex set {0, 1, 2, 3, 4, 5} with edges {0,1}, {1,2}, {0,3}, {0,5}, and {3,4} is a well-defined simple graph with decidable adjacency.

    The edge relation is defined symmetrically from the explicit list of five pairs. Symmetry is proved by commuting the disjunction, looplessness is verified by exhaustive check over all six vertices using `decide`, and decidability of adjacency follows by typeclass inference.

    lines 6–14

    def edges : List (Fin 6 × Fin 6) := [(0,1),(1,2),(0,3),(0,5),(3,4)]
    def G : SimpleGraph (Fin 6) where
      Adj u v := (u,v) ∈ edges ∨ (v,u) ∈ edges
      symm := ⟨by intro u v h; exact h.symm⟩
      loopless := ⟨by intro v; fin_cases v <;> decide⟩
    instance : DecidableRel G.Adj := by
      intro u v
      change Decidable ((u,v) ∈ edges ∨ (v,u) ∈ edges)
      infer_instance
  2. Whether a subset W ⊆ {0, 1, 2, 3, 4, 5} contains no fort is decidable.

    The property `noFort W` asserts the non-existence of a nonempty subset F ⊆ W where every vertex outside F has either zero or at least two neighbors in F. Because the vertex set and the powerset are finite, unfolding `noFort` yields a bounded first-order statement, allowing typeclass resolution to synthesize a decision procedure via `infer_instance`.

    lines 16–22

    def noFort (W : Finset (Fin 6)) : Prop :=
      ¬ ∃ fortSet : Finset (Fin 6), fortSet.Nonempty ∧ fortSet ⊆ W ∧
        ∀ u : Fin 6, u ∉ fortSet → ∀ w : Fin 6, w ∈ fortSet → G.Adj u w →
          ∃ x : Fin 6, x ∈ fortSet ∧ G.Adj u x ∧ x ≠ w
    instance (W : Finset (Fin 6)) : Decidable (noFort W) := by
      unfold noFort
      infer_instance
  3. There are 7 fort-free 4-element subsets of vertices in total, with 5 containing vertex 1, 4 containing vertex 4, and 3 containing both. automation

    The set `level 4` collects all 4-element subsets W satisfying `noFort W`. For each count—the total (`level_four`), those containing vertex 1 (`level_four_one`), those containing vertex 4 (`level_four_four`), and those containing both (`level_four_both`)—the `decide` tactic checks every subset among the 15 four-element subsets of `Fin 6` by computation.

    lines 28–34

    def level (k : ℕ) : Finset (Finset (Fin 6)) :=
      Finset.univ.filter fun W => W.card = k ∧ noFort W
    
    theorem level_four : (level 4).card = 7 := by decide
    theorem level_four_one : (level 4 |>.filter (fun W => (1 : Fin 6) ∈ W)).card = 5 := by decide
    theorem level_four_four : (level 4 |>.filter (fun W => (4 : Fin 6) ∈ W)).card = 4 := by decide
    theorem level_four_both : (level 4 |>.filter (fun W => (1 : Fin 6) ∈ W ∧ (4 : Fin 6) ∈ W)).card = 3 := by decide
  4. The graph G is a tree.

    By `SimpleGraph.isTree_iff_connected_and_card.mpr`, a finite graph is a tree if it is connected and its number of edges plus 1 equals its number of vertices. Connectivity is proved by showing that every vertex is reachable from 0: vertices 1, 3, and 5 are direct neighbors, vertex 2 is reached via 1, vertex 4 via 3, and 0 is reachable to itself by `SimpleGraph.Reachable.rfl`. An exhaustive case split (`fin_cases`) covers all six vertices. Finally, `Nat.card_eq_fintype_card` converts set cardinalities to finite type sizes, and `decide` confirms that 5 + 1 = 6.

    lines 37–56

    uses SimpleGraph.isTree_iff_connected_and_card.mpr, SimpleGraph.Reachable.rfl, Nat.card_eq_fintype_card

    theorem tree : G.IsTree := by
      apply SimpleGraph.isTree_iff_connected_and_card.mpr
      constructor
      · apply (G.connected_iff_exists_forall_reachable).mpr
        refine ⟨0, ?_⟩
        have h01 : G.Reachable 0 1 := (show G.Adj 0 1 by decide).reachable
        have h02 : G.Reachable 0 2 := h01.trans (show G.Adj 1 2 by decide).reachable
        have h03 : G.Reachable 0 3 := (show G.Adj 0 3 by decide).reachable
        have h04 : G.Reachable 0 4 := h03.trans (show G.Adj 3 4 by decide).reachable
        have h05 : G.Reachable 0 5 := (show G.Adj 0 5 by decide).reachable
        intro v
        fin_cases v
        · exact SimpleGraph.Reachable.rfl
        · exact h01
        · exact h02
        · exact h03
        · exact h04
        · exact h05
      · rw [Nat.card_eq_fintype_card, Nat.card_eq_fintype_card]
        decide
  5. For any predicate P, the number of sets in `family` satisfying P equals the number in `level 4` satisfying P.

    The set `family` consists of 4-element sets W whose complement is a zero forcing set. By `Set.ncard_eq_toFinset_card'`, the set cardinality equals the finset cardinality. Extensionality and simplification using `noFort_iff` (which equates the zero forcing complement property to `noFort W`) show that W ∈ family if and only if W ∈ level 4, matching the filtered counts.

    lines 58–67

    uses Set.ncard_eq_toFinset_card', noFort_iff

    def family : Set (Finset (Fin 6)) := {W | W.card = 4 ∧
      is_zero_forcing_set G ((Finset.univ \ W : Finset (Fin 6)) : Set (Fin 6))}
    
    theorem family_count (P : Finset (Fin 6) → Prop) [DecidablePred P] :
        {W ∈ family | P W}.ncard = ((level 4).filter P).card := by
      classical
      rw [Set.ncard_eq_toFinset_card']
      congr 1
      ext W
      simp [family, level, noFort_iff]
  6. The total number of sets in `family` is 7.

    Specializing `family_count` to the trivial predicate `fun _ => True` equates `family.ncard` to `(level 4).card`, which was evaluated to be 7 in `level_four`.

    lines 69–74

    uses family_count, level_four

    theorem total_count : family.ncard = 7 := by
      have h := family_count (fun _ => True)
      have hfamily : {W ∈ family | True} = family := by ext W; simp
      have hfilter : (level 4).filter (fun _ => True) = level 4 := by simp
      rw [hfamily, hfilter, level_four] at h
      exact h
  7. In the tree G, the events that vertices 1 and 4 belong to a 4-element white set with zero forcing complement are positively correlated.

    We instantiate the existential claim with G, vertex 1, and vertex 4. G is a tree by `tree`, and 1 ≠ 4 is verified by `decide`. The positive correlation condition asserts that the joint count times the total count exceeds the product of the marginal counts. Rewriting the set cardinalities using `family_count`, `total_count`, `level_four_both`, `level_four_one`, and `level_four_four` transforms the inequality into 3 * 7 > 5 * 4, which holds since 21 > 20 (verified by `decide`).

    lines 76–86

    uses tree, family_count, total_count, level_four_both, level_four_one, level_four_four

    theorem positive_corr :
        ∃ (T : SimpleGraph (Fin 6)) (i j : Fin 6), T.IsTree ∧ i ≠ j ∧
          (let fortSet : Set (Finset (Fin 6)) := {W | W.card = 4 ∧
            is_zero_forcing_set T ((Finset.univ \ W : Finset (Fin 6)) : Set (Fin 6))};
            {W ∈ fortSet | i ∈ W ∧ j ∈ W}.ncard * fortSet.ncard >
            {W ∈ fortSet | i ∈ W}.ncard * {W ∈ fortSet | j ∈ W}.ncard) := by
      refine ⟨G, 1, 4, tree, by decide, ?_⟩
      change {W ∈ family | (1 : Fin 6) ∈ W ∧ (4 : Fin 6) ∈ W}.ncard * family.ncard >
        {W ∈ family | (1 : Fin 6) ∈ W}.ncard * {W ∈ family | (4 : Fin 6) ∈ W}.ncard
      rw [family_count, family_count, family_count, total_count, level_four_both, level_four_one, level_four_four]
      decide
  8. There exists a six-vertex tree and two vertices whose events of being white in 4-element sets with zero forcing complements have positive correlation.

    This concludes the main theorem directly from `In800.positive_corr`.

    lines 90–91

    uses In800.positive_corr

    theorem tree_zf_white_rank_pair_positive_correlation : ∃ (T : SimpleGraph (Fin 6)) (i j : Fin 6), T.IsTree ∧ i ≠ j ∧ (let family : Set (Finset (Fin 6)) := {W | W.card = 4 ∧ is_zero_forcing_set T ((Finset.univ \ W : Finset (Fin 6)) : Set (Fin 6))}; {W ∈ family | i ∈ W ∧ j ∈ W}.ncard * family.ncard > {W ∈ family | i ∈ W}.ncard * {W ∈ family | j ∈ W}.ncard) := by
      exact In800.positive_corr
In800.positive_corr
There exists a tree on 6 vertices and two distinct vertices with positive correlation between their memberships in 4-element white sets whose complements are zero forcing.
Nat.card_eq_fintype_card
For any finite type, the general cardinality `Nat.card` equals the finite-type cardinality `Fintype.card`.
Set.ncard_eq_toFinset_card'
The cardinality of a finite set as a natural number (`Set.ncard`) equals the cardinality of its coercion to a `Finset`.
SimpleGraph.Reachable.rfl
Every vertex in a graph is reachable from itself.
SimpleGraph.isTree_iff_connected_and_card.mpr
A simple graph on a finite vertex set is a tree if it is connected and the number of edges plus 1 equals the number of vertices.
family_count
For any decidable predicate P on vertex subsets, the number of sets in `family` satisfying P equals the number of sets in `level 4` satisfying P.
level_four
There are exactly 7 subsets of size 4 on `Fin 6` that contain no fort.
level_four_both
There are exactly 3 subsets of size 4 containing no fort that contain both vertex 1 and vertex 4.
level_four_four
There are exactly 4 subsets of size 4 containing no fort that contain vertex 4.
level_four_one
There are exactly 5 subsets of size 4 containing no fort that contain vertex 1.
noFort_iff
A vertex subset W contains no fort if and only if its complement is a zero forcing set.
total_count
The total number of 4-element white sets with zero forcing complements in G is 7.
tree
The constructed 6-vertex graph G is a tree.

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 In800def edges : List (Fin 6 × Fin 6) := [(0,1),(1,2),(0,3),(0,5),(3,4)]def G : SimpleGraph (Fin 6) where  Adj u v := (u,v) ∈ edges ∨ (v,u) ∈ edges  symm := ⟨by intro u v h; exact h.symm⟩  loopless := ⟨by intro v; fin_cases v <;> decide⟩instance : DecidableRel G.Adj := by  intro u v  change Decidable ((u,v) ∈ edges ∨ (v,u) ∈ edges)  infer_instancedef noFort (W : Finset (Fin 6)) : Prop :=  ¬ ∃ fortSet : Finset (Fin 6), fortSet.Nonempty ∧ fortSet ⊆ W ∧    ∀ u : Fin 6, u ∉ fortSet → ∀ w : Fin 6, w ∈ fortSet → G.Adj u w →      ∃ x : Fin 6, x ∈ fortSet ∧ G.Adj u x ∧ x ≠ winstance (W : Finset (Fin 6)) : Decidable (noFort W) := by  unfold noFort  infer_instancetheorem noFort_iff (W : Finset (Fin 6)) :    noFort W ↔ is_zero_forcing_set G ((Finset.univ \ W : Finset (Fin 6)) : Set (Fin 6)) :=  (zfs_compl_iff_no_stuck G W).symmdef level (k : ℕ) : Finset (Finset (Fin 6)) :=  Finset.univ.filter fun W => W.card = k ∧ noFort Wtheorem level_four : (level 4).card = 7 := by decidetheorem level_four_one : (level 4 |>.filter (fun W => (1 : Fin 6) ∈ W)).card = 5 := by decidetheorem level_four_four : (level 4 |>.filter (fun W => (4 : Fin 6) ∈ W)).card = 4 := by decidetheorem level_four_both : (level 4 |>.filter (fun W => (1 : Fin 6) ∈ W ∧ (4 : Fin 6) ∈ W)).card = 3 := by decidetheorem tree : G.IsTree := by  apply SimpleGraph.isTree_iff_connected_and_card.mpr  constructor  · apply (G.connected_iff_exists_forall_reachable).mpr    refine ⟨0, ?_⟩    have h01 : G.Reachable 0 1 := (show G.Adj 0 1 by decide).reachable    have h02 : G.Reachable 0 2 := h01.trans (show G.Adj 1 2 by decide).reachable    have h03 : G.Reachable 0 3 := (show G.Adj 0 3 by decide).reachable    have h04 : G.Reachable 0 4 := h03.trans (show G.Adj 3 4 by decide).reachable    have h05 : G.Reachable 0 5 := (show G.Adj 0 5 by decide).reachable    intro v    fin_cases v    · exact SimpleGraph.Reachable.rfl    · exact h01    · exact h02    · exact h03    · exact h04    · exact h05  · rw [Nat.card_eq_fintype_card, Nat.card_eq_fintype_card]    decidedef family : Set (Finset (Fin 6)) := {W | W.card = 4 ∧  is_zero_forcing_set G ((Finset.univ \ W : Finset (Fin 6)) : Set (Fin 6))}theorem family_count (P : Finset (Fin 6) → Prop) [DecidablePred P] :    {W ∈ family | P W}.ncard = ((level 4).filter P).card := by  classical  rw [Set.ncard_eq_toFinset_card']  congr 1  ext W  simp [family, level, noFort_iff]theorem total_count : family.ncard = 7 := by  have h := family_count (fun _ => True)  have hfamily : {W ∈ family | True} = family := by ext W; simp  have hfilter : (level 4).filter (fun _ => True) = level 4 := by simp  rw [hfamily, hfilter, level_four] at h  exact htheorem positive_corr :    ∃ (T : SimpleGraph (Fin 6)) (i j : Fin 6), T.IsTree ∧ i ≠ j ∧      (let fortSet : Set (Finset (Fin 6)) := {W | W.card = 4 ∧        is_zero_forcing_set T ((Finset.univ \ W : Finset (Fin 6)) : Set (Fin 6))};        {W ∈ fortSet | i ∈ W ∧ j ∈ W}.ncard * fortSet.ncard >        {W ∈ fortSet | i ∈ W}.ncard * {W ∈ fortSet | j ∈ W}.ncard) := by  refine ⟨G, 1, 4, tree, by decide, ?_⟩  change {W ∈ family | (1 : Fin 6) ∈ W ∧ (4 : Fin 6) ∈ W}.ncard * family.ncard >    {W ∈ family | (1 : Fin 6) ∈ W}.ncard * {W ∈ family | (4 : Fin 6) ∈ W}.ncard  rw [family_count, family_count, family_count, total_count, level_four_both, level_four_one, level_four_four]  decideend In800theorem tree_zf_white_rank_pair_positive_correlation : ∃ (T : SimpleGraph (Fin 6)) (i j : Fin 6), T.IsTree ∧ i ≠ j ∧ (let family : Set (Finset (Fin 6)) := {W | W.card = 4 ∧ is_zero_forcing_set T ((Finset.univ \ W : Finset (Fin 6)) : Set (Fin 6))}; {W ∈ family | i ∈ W ∧ j ∈ W}.ncard * family.ncard > {W ∈ family | i ∈ W}.ncard * {W ∈ family | j ∈ W}.ncard) := by  exact In800.positive_corr
See it in the graphDiscuss this resultChallenge it