AFTD Auto-Formalizing Theoretical Domains

stochastic_mst_submodular_goal_value

def

The 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 submodular goal function g for G with goal value Q.

Statement

open scoped Classical in
noncomputable def stochastic_mst_submodular_goal_value {V : Type*} [Fintype V] (G : SimpleGraph V) : ℕ
Defined in
scout/2610-40844-stochastic-minimum-spanning-tree-identification-with-binary.md:702
Verified
07 Nov 2026
Axioms
none listed
Built on 1
  • 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

Given a finite type V and a simple graph G on V, stochastic_mst_submodular_goal_value G is defined as the infimum (in ℕ, which is the minimum if non-empty, and 0 if empty) of the set of natural numbers Q for which there exists a function g : (G.edgeSet → Option Bool) → ℕ such that g is a submodular goal function for G with goal value Q (is_submodular_goal_function G g Q). A function g : (G.edgeSet → Option Bool) → ℕ is a submodular goal function for G with target value Q if: 1. g assigns 0 to the empty partial assignment (where every edge is none). 2. Monotonicity: For all partial assignments β, γ : G.edgeSet → Option Bool, if β ≤ γ (i.e., whenever β e = some b, then γ e = some b), then g β ≤ g γ. 3. Submodularity (diminishing returns): For all partial assignments β, γ : G.edgeSet → Option Bool, every edge e ∈ G.edgeSet, and every boolean s : Bool, if β ≤ γ and γ e = none, then g (γ[e ↦ some s]) + g β ≤ g (β[e ↦ some s]) + g γ. 4. Goal condition: For all partial assignments β : G.edgeSet → Option Bool, g β = Q if and only if β is an MST certificate for G (is_mst_certificate G β). Here, β is an MST certificate for G (is_mst_certificate G β) if there exists a subgraph T ≤ G such that: - T is a tree (T.IsTree), and - for every total edge assignment α : G.edgeSet → Bool extending β (i.e., α e = b whenever β e = some b), T is a minimum spanning tree for G under α (is_mst_for G T α), meaning that for every tree subgraph T' ≤ G, the sum of weights (1 if α e = true, 0 if α e = false) of edges in T is less than or equal to the sum of weights of edges in T'.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

open scoped Classical in
/-- The minimum goal value Q of a submodular goal function for G. -/
noncomputable def stochastic_mst_submodular_goal_value {V : Type*} [Fintype V] (G : SimpleGraph V) : ℕ := sInf {Q : ℕ | ∃ g, is_submodular_goal_function G g Q}
See it in the graphDiscuss this resultChallenge it