AFTD Auto-Formalizing Theoretical Domains

is_subcube_univ

theoremverified

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.

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

    line 3

      refine ⟨∅, (fun _ => false : Fin n → Bool), by simp, ?_⟩
  2. 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.

    lines 4–5

      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

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