AFTD Auto-Formalizing Theoretical Domains

is_subcube_singleton

theoremverified

For any natural number $n$ and any point $c : \mathrm{Fin}\ n \to \mathrm{Bool}$, the singleton subset $\{c\} \subseteq (\mathrm{Fin}\ n \to \mathrm{Bool})$ is a $0$-dimensional subcube is_subcube 0 {c}.

Statement

theorem is_subcube_singleton (n : ℕ) (c : Fin n → Bool) :
    is_subcube 0 ({c} : Finset (Fin n → Bool))
Source
folklore
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • is_subcubeFor an implicit dimension $n$, a dimension $d : \mathbb{N}$, and a finite subset…

Read back from the Lean

For every natural number $n$ and every function $c : \mathrm{Fin}\ n \to \mathrm{Bool}$, the singleton set $\{c\}$ is a subcube of dimension $0$.

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

By definition, a 0-dimensional subcube in the Boolean hypercube Fin n → Bool is formed by fixing a set of coordinates of size n - 0 = n to match a reference point c. We choose the coordinate set to be all of Fin n (Finset.univ) and the reference point to be c. The dimension equation |Finset.univ| + 0 = n holds since Fin n has n elements, and function extensionality shows that the only point agreeing with c on all coordinates is c itself, yielding the singleton {c}.

  1. To show that {c} is a 0-dimensional subcube, we choose the full coordinate set S = Finset.univ and reference point c, which satisfies the dimension requirement |S| + 0 = n.

    By definition, a subcube of dimension d is given by a coordinate subset S and a reference point c such that |S| + d = n, containing all points that agree with c on S. Setting d = 0, we instantiate S with the universal set Finset.univ and the pattern with c. The dimension equation |Finset.univ| + 0 = n holds because the universe Finset.univ of Fin n has cardinality n, and n + 0 = n.

    lines 4–5

      refine ⟨Finset.univ, c, ?_, ?_⟩
      · simp
  2. The set of functions agreeing with c on all coordinates is precisely the singleton {c}.

    By set extensionality (ext x), a function x belongs to the subcube if and only if x i = c i for all i in Finset.univ. Since x ∈ {c} means x = c, this equivalence is function extensionality (funext_iff).

    lines 6–7

    uses funext_iff

      · ext x
        simp [funext_iff]
funext_iff
Two functions are equal if and only if they agree on all arguments: f = g ↔ ∀ x, f x = g x.

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

/-- Every singleton in the Boolean hypercube is a `0`-dimensional subcube. -/theorem is_subcube_singleton (n : ℕ) (c : Fin n → Bool) :    is_subcube 0 ({c} : Finset (Fin n → Bool)) := by  refine ⟨Finset.univ, c, ?_, ?_⟩  · simp  · ext x    simp [funext_iff]
See it in the graphDiscuss this resultChallenge it