nat_self_delimiting_code_five
The self-delimiting code of 5 (binary 101, least significant bit first 1,0,1) is true,true, true,false, true,true, false.
Statement
theorem nat_self_delimiting_code_five :
nat_self_delimiting_code 5 = [true, true, true, false, true, true, false]- Source
- Sanity check of nat_self_delimiting_code (OP-851 encoding).
- Verified
- 07 Nov 2026
- Axioms
Quot.soundpropext- Built on 1
- 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…
- Used by 1
- op_1667_opposite_cerny_product_two_is_synchronizingThe binary word [false, true] of length 2 synchronizes the direct product of the 2-state Černý automaton C_2 and its letter-swapped copy…
The proof, explained
The claim is proved by direct computation. To encode the number 5, its binary bits are extracted in least-significant-bit-first order as [true, false, true]. Each bit b is expanded to [true, b], and a terminating false is appended to mark the end of the code. Lean's decision procedure checks the equality automatically by evaluating the functions on concrete values.
nat_self_delimiting_code 5 = [true, true, true, false, true, true, false] automation
The equality is verified by direct computation. By definition, `nat_self_delimiting_code 5` computes the binary representation of 5 starting from the least significant bit, yielding `[true, false, true]`. It then replaces each bit b with `[true, b]` to obtain `[true, true, true, false, true, true]`, and appends a final `false`. Because all operations are finite and computable, the `decide` tactic evaluates both sides to normal form and confirms they are identical.
decide
- The `decide` tactic discharges the goal by computational evaluation of the function `nat_self_delimiting_code` on the concrete input 5, rather than via step-by-step deductive lemmas.
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 nat_self_delimiting_code_five : nat_self_delimiting_code 5 = [true, true, true, false, true, true, false] := by decide