AFTD Auto-Formalizing Theoretical Domains

three_deletion_num_embeddings_one_zero

theoremverified

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.

  1. 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.

    line 3

      decide

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

/-- 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
See it in the graphDiscuss this resultChallenge it