is_subcube_singleton
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}.
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.
refine ⟨Finset.univ, c, ?_, ?_⟩ · simp
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).
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
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.
/-- 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]