is_subcube_univ
For any natural number $n$, the entire hypercube $\mathrm{Finset.univ} \subseteq (\mathrm{Fin}\ n \to \mathrm{Bool})$ is an $n$-dimensional subcube is_subcube n Finset.univ.
Statement
theorem is_subcube_univ (n : ℕ) : is_subcube n (Finset.univ : 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$, the universal finset of functions from $\mathrm{Fin}(n)$ to $\mathrm{Bool}$ (i.e., the entire $n$-dimensional Boolean hypercube $\{0, 1\}^n$) is a subcube of dimension $n$ in the sense of is_subcube.
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
A subcube of dimension $n$ in the $n$-dimensional hypercube $\{0, 1\}^n$ requires fixing $n - n = 0$ coordinates. Choosing the empty set of coordinates $\emptyset$ as the constraint set and an arbitrary function as the center, the dimension condition $|\emptyset| + n = n$ holds trivially. The condition that points match the center on $\emptyset$ is vacuously true for every point, so the resulting subcube is indeed the entire hypercube.
We can exhibit the entire hypercube as an $n$-dimensional subcube by fixing zero coordinates.
By definition, an $n$-dimensional subcube in $\{0, 1\}^n$ is specified by choosing a set of fixed coordinates $S$ and a coordinate-value function $c$ such that $|S| + n = n$, with the subcube consisting of points agreeing with $c$ on $S$. We witness this definition by taking $S = \emptyset$ and an arbitrary constant function for $c$ (here, the constant false function). The dimension identity $|\emptyset| + n = n$ holds immediately because $|\emptyset| = 0$, leaving the goal to show that the subcube defined by $\emptyset$ equals $\mathrm{Finset.univ}$.
refine ⟨∅, (fun _ => false : Fin n → Bool), by simp, ?_⟩
The subcube determined by no coordinate constraints is the entire hypercube.
By extensionality on finite sets (`ext x`), it suffices to show that an arbitrary point $x$ belongs to $\mathrm{Finset.univ}$ if and only if $x(i) = c(i)$ for all $i \in \emptyset$. Since quantification over the empty set is vacuously true for every $x$, simplification concludes that both sides evaluate to true, completing the proof.
ext x simp
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.
/-- The entire hypercube is an `n`-dimensional subcube of itself. -/theorem is_subcube_univ (n : ℕ) : is_subcube n (Finset.univ : Finset (Fin n → Bool)) := by refine ⟨∅, (fun _ => false : Fin n → Bool), by simp, ?_⟩ ext x simp