AFTD Auto-Formalizing Theoretical Domains

tree_submodular_goal_value_zero

theoremverified

For every finite simple graph G on a vertex type V that is a tree (G.IsTree), the submodular goal value stochastic_mst_submodular_goal_value G is 0.

Statement

open scoped Classical in
theorem tree_submodular_goal_value_zero {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.IsTree) :
    stochastic_mst_submodular_goal_value G = 0
Source
scout/2610-40844-stochastic-minimum-spanning-tree-identification-with-binary.md:703
Verified
07 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • stochastic_mst_submodular_goal_valueThe submodular goal value Q_ID(G) of a finite graph G is the infimum in ℕ (sInf) of the set of natural numbers Q such that there exists a…
  • partial_assignment_leA partial assignment β is extended by γ (written β ≼ γ) if for every element e and boolean value b, β(e) = some b implies γ(e) = some b.
  • is_mst_certificateA partial realization β : G.edgeSet → Option Bool is an MST identification certificate for G if there exists a spanning tree T of G (T ≤ G…
  • is_mst_forA simple graph T on a finite vertex type V is a minimum spanning tree of G under edge realization α : G.edgeSet → Bool if T is a subgraph…
  • is_submodular_goal_functionA function g : (G.edgeSet → Option Bool) → ℕ is a submodular goal function with goal value Q for G if: g evaluates to 0 on the empty…
Used by 1

Read back from the Lean

For any finite type V and any simple graph G on V, if G is a tree (G.IsTree), then the stochastic MST submodular goal value of G (stochastic_mst_submodular_goal_value G) equals 0.

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

Because G is already a tree on a finite vertex set V, any spanning sub-tree T' ≤ G has |V| - 1 edges and is therefore equal to G itself. Consequently, G is uniquely its own minimum spanning tree under any edge weights, which makes every partial observation an MST certificate. This allows the constant zero function to serve as a valid submodular goal function achieving goal value Q = 0. Since 0 is an achievable goal value, the infimum over all achievable goal values—the stochastic MST submodular goal value—is 0.

  1. Any spanning sub-tree T' of G has the same number of edges as G.

    In any finite graph on vertex set V, any tree has |V| - 1 edges (so |E(G)| + 1 = |V| and |E(T')| + 1 = |V|). Linear integer arithmetic (via omega) deduces that |E(T')| = |E(G)|.

    lines 4–6

      have hcardG := hG.card_edgeFinset
      have hcardT' := hT'.card_edgeFinset
      have hcard_eq : T'.edgeFinset.card = G.edgeFinset.card := by omega
  2. Any spanning sub-tree T' ≤ G is identical to G.

    Because T' ≤ G, the edges of T' form a subset of the edges of G (by SimpleGraph.edgeFinset_subset_edgeFinset). A subset between finite sets of equal cardinality must be the entire set (Finset.eq_of_subset_of_card_le and ge_of_eq). Since their edge sets are equal, the graphs T' and G are equal (SimpleGraph.edgeFinset_inj).

    lines 7–10

    uses SimpleGraph.edgeFinset_subset_edgeFinset, Finset.eq_of_subset_of_card_le, ge_of_eq, SimpleGraph.edgeFinset_inj

      have hsub : T'.edgeFinset ⊆ G.edgeFinset := by rwa [SimpleGraph.edgeFinset_subset_edgeFinset]
      have heq : T'.edgeFinset = G.edgeFinset :=
        Finset.eq_of_subset_of_card_le hsub (ge_of_eq hcard_eq)
      rwa [SimpleGraph.edgeFinset_inj] at heq
  3. The tree G is a minimum spanning tree for itself under any edge weights α.

    To show that G is an MST for α, we check that G ≤ G (by le_rfl), G is a tree, and any tree subgraph T' ≤ G has total edge weight at least that of G. But by tree_submodular_goal_value_zero_subgraph_eq, any such T' must equal G, so the inequality between their weights holds by reflexivity.

    lines 15–18

    uses le_rfl, tree_submodular_goal_value_zero_subgraph_eq

      refine ⟨le_rfl, hG, fun T' hT'le hT'tree => ?_⟩
      have heq : T' = G := tree_submodular_goal_value_zero_subgraph_eq hG hT'tree hT'le
      subst heq
      rfl
  4. The constant zero function is a submodular goal function with goal value 0.

    The conditions for a submodular goal function require g(∅) = 0, monotonicity, submodularity, and that g(β) = Q if and only if β is an MST certificate. With g identically zero and Q = 0, the first three conditions hold trivially by reflexivity (le_rfl). The goal equivalence 0 = 0 ↔ is_mst_certificate G β reduces to True ↔ True because tree_submodular_goal_value_zero_is_mst_certificate proves that every partial assignment is an MST certificate for G.

    lines 28–29

    uses le_rfl, tree_submodular_goal_value_zero_is_mst_certificate

      refine ⟨rfl, fun _ _ _ => le_rfl, fun _ _ _ _ _ _ => le_rfl, fun β => ?_⟩
      simp [tree_submodular_goal_value_zero_is_mst_certificate G hG β]
  5. The stochastic MST submodular goal value of G is 0.

    The submodular goal value is defined as the infimum over all goal values Q achievable by a submodular goal function. Since g ≡ 0 achieves Q = 0 (by tree_submodular_goal_value_zero_is_submodular_goal_function), 0 belongs to this set (via Or.inl). The infimum of any set of natural numbers containing 0 is 0 (by Nat.sInf_eq_zero.mpr).

    lines 35–36

    uses tree_submodular_goal_value_zero_is_submodular_goal_function, Or.inl, Nat.sInf_eq_zero.mpr

      change sInf {Q | ∃ g, is_submodular_goal_function G g Q} = 0
      exact Nat.sInf_eq_zero.mpr (Or.inl ⟨fun _ => 0, tree_submodular_goal_value_zero_is_submodular_goal_function G hG⟩)
SimpleGraph.edgeFinset_subset_edgeFinset
A simple graph is a subgraph of another if and only if its edge set is a subset of the other's edge set.
Finset.eq_of_subset_of_card_le
If one finite set is a subset of another and has at least as many elements, the two sets are equal.
ge_of_eq
Equality implies the reverse inequality in a preorder (a = b implies b ≤ a).
SimpleGraph.edgeFinset_inj
Two simple graphs on the same vertices are equal if and only if their edge sets are equal.
le_rfl
The preorder relation ≤ is reflexive (a ≤ a).
tree_submodular_goal_value_zero_subgraph_eq
Any spanning sub-tree of a finite tree graph is equal to the ambient graph.
tree_submodular_goal_value_zero_is_mst_certificate
For every tree graph G, every partial edge assignment is an MST certificate for G.
Nat.sInf_eq_zero.mpr
A set of natural numbers has infimum 0 if it contains 0 (or if it is empty).
Or.inl
Proves a disjunction A ∨ B by proving the left disjunct A.
tree_submodular_goal_value_zero_is_submodular_goal_function
For every finite tree G, the constant zero function is a submodular goal function with goal value 0.

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

open scoped Classical intheorem tree_submodular_goal_value_zero_subgraph_eq {V : Type*} [Fintype V] {G T' : SimpleGraph V}    (hG : G.IsTree) (hT' : T'.IsTree) (hle : T' ≤ G) : T' = G := by  have hcardG := hG.card_edgeFinset  have hcardT' := hT'.card_edgeFinset  have hcard_eq : T'.edgeFinset.card = G.edgeFinset.card := by omega  have hsub : T'.edgeFinset ⊆ G.edgeFinset := by rwa [SimpleGraph.edgeFinset_subset_edgeFinset]  have heq : T'.edgeFinset = G.edgeFinset :=    Finset.eq_of_subset_of_card_le hsub (ge_of_eq hcard_eq)  rwa [SimpleGraph.edgeFinset_inj] at heqopen scoped Classical intheorem tree_submodular_goal_value_zero_is_mst_for {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.IsTree)    (α : G.edgeSet → Bool) : is_mst_for G G α := by  refine ⟨le_rfl, hG, fun T' hT'le hT'tree => ?_⟩  have heq : T' = G := tree_submodular_goal_value_zero_subgraph_eq hG hT'tree hT'le  subst heq  rflopen scoped Classical intheorem tree_submodular_goal_value_zero_is_mst_certificate {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.IsTree)    (β : G.edgeSet → Option Bool) : is_mst_certificate G β :=  ⟨G, le_rfl, hG, fun α _ => tree_submodular_goal_value_zero_is_mst_for G hG α⟩open scoped Classical intheorem tree_submodular_goal_value_zero_is_submodular_goal_function {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.IsTree) :    is_submodular_goal_function G (fun _ => 0) 0 := by  refine ⟨rfl, fun _ _ _ => le_rfl, fun _ _ _ _ _ _ => le_rfl, fun β => ?_⟩  simp [tree_submodular_goal_value_zero_is_mst_certificate G hG β]open scoped Classical in/-- For a tree, the submodular goal value is 0. -/theorem tree_submodular_goal_value_zero {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.IsTree) :    stochastic_mst_submodular_goal_value G = 0 := by  change sInf {Q | ∃ g, is_submodular_goal_function G g Q} = 0  exact Nat.sInf_eq_zero.mpr (Or.inl ⟨fun _ => 0, tree_submodular_goal_value_zero_is_submodular_goal_function G hG⟩)
See it in the graphDiscuss this resultChallenge it