three_deletion_num_embeddings_one_zero
The binary word of length 1 constantly equal to false has exactly 4 embeddings in the binary word of length 4 constantly equal to false.
Statement
theorem three_deletion_num_embeddings_one_zero : three_deletion_num_embeddings 1 (fun _ => false) (fun _ => false) = 4
- Source
- folklore
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- three_deletion_num_embeddingsFor a binary word w of length n and a binary word y of length n + 3, three_deletion_num_embeddings n w y is the number of strictly…
Read back from the Lean
The value of three_deletion_num_embeddings 1 (fun _ => false) (fun _ => false) is 4; that is, the number of strictly monotonic functions from Fin 1 to Fin 4 preserving the all-false boolean word is equal to 4.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The claim asserts that there are 4 embeddings of the 1-bit word `[0]` into the 4-bit word `[0, 0, 0, 0]`. By definition, an embedding is a strictly monotonic map from `Fin 1` to `Fin 4` that preserves the bit values. Since all sets and predicates involved are finite and decidable, the proof proceeds purely by computation using the `decide` tactic.
The number of embeddings of the 1-bit all-zero word into the 4-bit all-zero word is 4. automation
The count `three_deletion_num_embeddings 1 (fun _ => false) (fun _ => false)` is defined as the cardinality of strictly monotonic functions from `Fin 1` to `Fin 4` preserving bit values. Because both the domain and codomain are finite and all conditions are decidable, the `decide` tactic performs an exhaustive computation over the four possible functions from `Fin 1` to `Fin 4` and verifies that all four satisfy the condition.
decide
- The proof relies entirely on Lean's kernel computation (`decide`) to exhaustively evaluate the finite search space and count the embeddings, rather than applying a general formula for combinations.
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.
/-- Sanity check: the 1-bit word [0] has 4 embeddings in the 4-bit word [0,0,0,0]. -/theorem three_deletion_num_embeddings_one_zero : three_deletion_num_embeddings 1 (fun _ => false) (fun _ => false) = 4 := by decide