AFTD Auto-Formalizing Theoretical Domains

stochastic_mst_instance_code_top_two

theoremverified

The single edge on two vertices with probability 1/2 is encoded as 1,1,0 (n = 2 in unary), 1 (the pair 0,1 is adjacent), 1,1,0 (numerator 1), 1,0,1,1,0 (denominator 2, bits 0,1).

Statement

theorem stochastic_mst_instance_code_top_two :
    stochastic_mst_instance_code 2 ⊤ (fun _ => 1 / 2) =
      [true, true, false, true, true, true, false, true, false, true, true, 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 theorem verifies by direct computation that encoding the complete graph on two vertices with edge probability $1/2$ yields the expected 12-bit sequence. Because the instance parameters and the encoding function are completely concrete and computable, the `decide +kernel` tactic closes the goal by evaluating the expression directly in the Lean kernel.

  1. The encoding of the complete graph on two vertices with probability 1/2 evaluates to `[true, true, false, true, true, true, false, true, false, true, true, false]`. automation

    The expression is closed and purely computable. According to the definition of `stochastic_mst_instance_code`: the vertex count $n = 2$ is represented in unary as `[true, true, false]`; the single ordered pair of vertices $(0, 1)$ is an edge in $\top$, contributing the adjacency bit `[true]`; and the probability $1/2$ is encoded via its numerator $1$ (giving `[true, true, false]`) and denominator $2$ (whose binary bits $0, 1$ give `[true, false, true, true, false]`). Concatenating these gives the expected 12-element boolean list. The `decide +kernel` tactic computes both sides and confirms equality directly within the Lean kernel.

    line 4

      decide +kernel

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_top_two :    stochastic_mst_instance_code 2 ⊤ (fun _ => 1 / 2) =      [true, true, false, true, true, true, false, true, false, true, true, false] := by  decide +kernel
See it in the graphDiscuss this resultChallenge it