AFTD Auto-Formalizing Theoretical Domains

stochastic_mst_instance_code_bot_zero

theoremverified

The empty graph on zero vertices is encoded by the single bit false.

Statement

theorem stochastic_mst_instance_code_bot_zero (p : (⊥ : SimpleGraph (Fin 0)).edgeSet → ℚ) :
    stochastic_mst_instance_code 0 ⊥ p = [false]
Source
Sanity check of stochastic_mst_instance_code (OP-851 encoding).
Verified
07 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • stochastic_mst_instance_codeThe binary encoding of an instance (G, p) of stochastic MST identification, G a simple graph on vertices 0..n-1 and p a rational…
  • nat_self_delimiting_codeThe self-delimiting binary code of a natural number m: each bit b of the binary expansion of m (least significant bit first, as in…

The proof, explained

The encoding of a stochastic minimum spanning tree instance consists of a unary count of vertices followed by the delimiter false, the graph adjacency bits, and the encoded edge probabilities. When the vertex count is 0, the unary prefix is empty and there are no pairs of vertices to encode, so the adjacency and probability components are both empty lists. Unfolding the definition and simplifying the list operations immediately yields the singleton list [false].

  1. The encoding of the empty graph on 0 vertices evaluates to [false]. automation

    Unfolding the definition of stochastic_mst_instance_code at n = 0, the unary prefix List.replicate 0 true evaluates to [], followed by [false]. The remaining segments iterate over the empty list List.finRange 0, so their flatMaps evaluate to empty lists. Simplifying the list concatenations [] ++ [false] ++ [] ++ [] yields [false].

    line 3

    uses stochastic_mst_instance_code

      simp [stochastic_mst_instance_code]
stochastic_mst_instance_code
Encodes an instance of the stochastic minimum spanning tree problem (given by a graph on $n$ vertices and edge probabilities $p$) as a list of boolean values.

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

theorem stochastic_mst_instance_code_bot_zero (p : (⊥ : SimpleGraph (Fin 0)).edgeSet → ℚ) :    stochastic_mst_instance_code 0 ⊥ p = [false] := by  simp [stochastic_mst_instance_code]
See it in the graphDiscuss this resultChallenge it