AFTD Auto-Formalizing Theoretical Domains

is_two_four_code_singleton

theoremverified

Any singleton set $\{x\} \subseteq (\mathrm{Fin}\, n \to \mathrm{Fin}\, q)$ is a $\{2, 4\}$-code.

Statement

theorem is_two_four_code_singleton (n q : ℕ) (x : Fin n → Fin q) : is_two_four_code ({x} : Set (Fin n → Fin q))
Source
folklore
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • is_two_four_codeA set of codewords $C \subseteq (\mathrm{Fin}\, n \to \mathrm{Fin}\, q)$ is a $\{2, 4\}$-code if any two distinct codewords $x, y \in C$…

Read back from the Lean

For all natural numbers n and q, and every function x : Fin n → Fin q, the singleton set {x} satisfies is_two_four_code.

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 theorem holds vacuously because a singleton set contains no pair of distinct elements. By definition of a {2, 4}-code, any two distinct codewords in the set must have Hamming distance 2 or 4. However, belonging to the singleton {x} forces any such codewords to both equal x, which directly contradicts the assumption that they are distinct.

  1. Assuming there are distinct codewords y, z ∈ {x} yields the contradiction z ≠ z.

    By definition of a {2, 4}-code, we introduce arbitrary elements y, z ∈ {x} along with the hypothesis y ≠ z that they are distinct. By Set.mem_singleton_iff, membership in {x} means y = x and z = x. Substituting these equalities transforms y ≠ z into the self-contradiction z ≠ z.

    lines 3–5

    uses Set.mem_singleton_iff

      intro y hy z hz hyz
      rw [Set.mem_singleton_iff] at hy hz
      subst hy hz
  2. The conclusion holds vacuously.

    Because z = z holds by reflexivity, the hypothesis z ≠ z is a contradiction (False), which proves the disjunction by the principle of explosion.

    line 6

      exact (hyz rfl).elim
Set.mem_singleton_iff
An element a belongs to the singleton set {b} if and only if a = b.

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

/-- Any singleton code is vacuously a {2,4}-code. -/theorem is_two_four_code_singleton (n q : ℕ) (x : Fin n → Fin q) : is_two_four_code ({x} : Set (Fin n → Fin q)) := by  intro y hy z hz hyz  rw [Set.mem_singleton_iff] at hy hz  subst hy hz  exact (hyz rfl).elim
See it in the graphDiscuss this resultChallenge it