stochastic_mst_instance_code_bot_zero
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].
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].
uses
stochastic_mst_instance_codesimp [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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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]