AFTD Auto-Formalizing Theoretical Domains

is_submodular_goal_function

def

A 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 assignment (fun _ => none); g is monotone under partial assignment extension (partial_assignment_le β γ → g β ≤ g γ); g satisfies state-dependent submodularity (for all β ≼ γ and e with γ e = none, g(γ_{e ← s}) + g(β) ≤ g(β_{e ← s}) + g(γ)); and g(β) = Q if and only if β is an MST identification certificate for G (is_mst_certificate G β).

Statement

open scoped Classical in
def is_submodular_goal_function {V : Type*} [Fintype V] (G : SimpleGraph V)
    (g : (G.edgeSet → Option Bool) → ℕ) (Q : ℕ) : Prop
Defined in
scout/2610-40844-stochastic-minimum-spanning-tree-identification-with-binary.md:686
Verified
06 Nov 2026
Axioms
none listed
Built on 2
  • 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…
Used by 2

Read back from the Lean

For a finite vertex type V, a simple graph G on V, a function g : (G.edgeSet → Option Bool) → ℕ, and a natural number Q, is_submodular_goal_function G g Q asserts the conjunction of four properties: 1. (Base value) g maps the completely unassigned partial assignment (the constant none function) to 0. 2. (Monotonicity) For all partial assignments β and γ, if β ≤ γ (i.e., for every edge e and boolean b, if β(e) = some b then γ(e) = some b), then g(β) ≤ g(γ). 3. (Submodularity / Diminishing returns) For all partial assignments β and γ, every edge e ∈ G.edgeSet, and every boolean s, if β ≤ γ and γ(e) = none, then g(γ[e ↦ some s]) + g(β) ≤ g(β[e ↦ some s]) + g(γ). 4. (Target characterization) For all partial assignments β, g(β) = Q if and only if β is an MST certificate for G (is_mst_certificate G β).

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
/-- A submodular goal function with goal value Q for stochastic MST identification. -/
def is_submodular_goal_function {V : Type*} [Fintype V] (G : SimpleGraph V)
    (g : (G.edgeSet → Option Bool) → ℕ) (Q : ℕ) : Prop := g (fun _ => none) = 0 ∧
  (∀ β γ, partial_assignment_le β γ → g β ≤ g γ) ∧
  (∀ β γ e s, partial_assignment_le β γ → γ e = none →
    g (Function.update γ e (some s)) + g β ≤ g (Function.update β e (some s)) + g γ) ∧
  (∀ β, g β = Q ↔ is_mst_certificate G β)
See it in the graphDiscuss this resultChallenge it