binary_partial_word_cube_card
A partial-word cube on a finite coordinate type has cardinality two to the number of coordinates outside its support.
Statement
theorem binary_partial_word_cube_card {V : Type*} [Fintype V] [DecidableEq V] (s : Finset V) (b : V → Bool) : (binary_partial_word_cube s b).card = 2 ^ (Fintype.card V - s.card)
- Source
- Reusable finite-cube and ordered-biclique helpers for the uniform OP-205 / RT-1 full-root-gap reduction following arXiv:2610.15635. The deficiency-one singular-coordinate/tree argument formalizes the Boolean setting of arXiv:1103.3693 Lemma 2.5.4 and Corollary 2.5.6; arXiv:2212.14685 Section 2.3 gives a related partition-size discussion. These are helper formalizations, not an original graph covering result; no advance is claimed.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- binary_partial_word_cubeThe finite Boolean cube determined by fixing the coordinates of a finite support to the values of a Boolean word.
- Used by 3
- binary_partial_word_partition_dimension_boundA finite partition of a Boolean cube by pairwise conflicting partial words, mentioning every coordinate, has at least one more part than…
- binary_partial_word_cube_packingPairwise conflicting partial words pack disjoint cubes into the full Boolean cube, bounding the sum of their cardinalities.
- binary_partial_word_cube_cover_of_volume_eqPairwise conflicting partial words whose rational volume sum is one cover the entire finite Boolean cube.
The proof, explained
The cardinality of the partial-word cube is computed by viewing it as a Cartesian product of coordinate sets over all coordinates in V. Coordinates in the support s are restricted to a single boolean value, while coordinates outside s can take either of the 2 boolean values. The total number of elements is therefore the product of 1 for each coordinate in s and 2 for each coordinate outside s, which simplifies to 2^{|V \ s|} = 2^{|V| - |s|}.
The cardinality of the partial-word cube is the product over all coordinates in V of the cardinality of each coordinate's constraint set.
Enabling classical logic for decidability, we expand the definition of `binary_partial_word_cube`: it is the Cartesian product (`Fintype.piFinset`) of sets where coordinate v is restricted to the singleton {b(v)} if v ∈ s, and is the entire universe of booleans if v ∉ s. By `Fintype.card_piFinset`, the cardinality of such a product is the product of the cardinalities of the individual factor sets.
uses
binary_partial_word_cube,Fintype.card_piFinsetclassical rw [binary_partial_word_cube, Fintype.card_piFinset]The product simplifies to 2 raised to the number of coordinates outside s.
Distributing the cardinality operator across the conditional (`apply_ite`), each coordinate in s has cardinality 1 since it is a singleton (`card_singleton`), while each coordinate outside s has cardinality 2 since the boolean type has two values (`card_univ`, `Fintype.card_bool`). The product over all coordinates v ∈ V then splits into a product over coordinates in s and a product over coordinates not in s (`prod_ite`). The product over v ∈ s is a product of 1s and evaluates to 1 (`prod_const_one`, `one_mul`), while the product over v ∉ s multiplies the constant 2 once for each element outside s, yielding 2^{|{v ∈ V | v ∉ s}|} (`prod_const`).
uses
apply_ite,card_singleton,card_univ,Fintype.card_bool,prod_ite,prod_const_one,one_mul,prod_constsimp_rw [apply_ite Finset.card, card_singleton, card_univ, Fintype.card_bool] rw [prod_ite] simp only [prod_const_one, one_mul, prod_const]
The number of coordinates outside s is |V| - |s|, which equates the exponents and completes the proof.
Matching the common base 2 on both sides reduces the equality to showing that the exponents are equal (`congr 1`), namely that |{v ∈ V | v ∉ s}| = |V| - |s|. The set of coordinates not in s is the complement `univ \ s` (`filter_not`, `filter_mem_eq_inter`, `univ_inter`). Because s ⊆ univ (`subset_univ`), the cardinality of this difference is |univ| - |s| (`card_sdiff_of_subset`), which matches |V| - |s| because |univ| = |V| (`card_univ`).
uses
filter_not,filter_mem_eq_inter,univ_inter,card_univ,card_sdiff_of_subset,subset_univcongr 1 simpa only [filter_not, filter_mem_eq_inter, univ_inter, card_univ] using (card_sdiff_of_subset (subset_univ s))
binary_partial_word_cube- The subcube of functions V → Bool that agree with b on coordinates in s and are unconstrained elsewhere, defined as a Cartesian product of finite sets.
Fintype.card_piFinset- The cardinality of a dependent product of finite sets over a finite index type is the product of their individual cardinalities.
apply_ite- Applying a function f to a conditional expression yields `if P then f x else f y`.
card_singleton- The cardinality of a singleton set {a} is 1.
card_univ- The cardinality of the universal finset of a finite type is the cardinality of the type itself.
Fintype.card_bool- The boolean type Bool has cardinality 2.
prod_ite- The product of a conditional expression over a finite set splits into the product of the then-branch over elements satisfying the condition times the product of the else-branch over elements not satisfying it.
prod_const_one- The product of the constant 1 over any finite set equals 1.
one_mul- Multiplication by 1 on the left is the identity (1 * a = a).
prod_const- The product of a constant value b over a finite set s equals b raised to the power of the cardinality of s.
filter_not- Filtering a finite set by the negation of a predicate p yields the set difference of the original set and the elements satisfying p.
filter_mem_eq_inter- Filtering a set s by membership in another set t is equal to the intersection s ∩ t.
univ_inter- The intersection of the universal finset with any finset s is s itself.
card_sdiff_of_subset- If s is a subset of t, the cardinality of the set difference t \ s is the cardinality of t minus the cardinality of s.
subset_univ- Every finset of elements of a finite type is a subset of the universal finset.
- Line 8 uses the `classical` tactic to provide decidable instances for predicates such as set membership, which is a formal requirement for Lean's representation of conditional expressions and finite set operations.
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.
open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem binary_partial_word_cube_card {V : Type*} [Fintype V] [DecidableEq V] (s : Finset V) (b : V → Bool) : (binary_partial_word_cube s b).card = 2 ^ (Fintype.card V - s.card) := by classical rw [binary_partial_word_cube, Fintype.card_piFinset] simp_rw [apply_ite Finset.card, card_singleton, card_univ, Fintype.card_bool] rw [prod_ite] simp only [prod_const_one, one_mul, prod_const] congr 1 simpa only [filter_not, filter_mem_eq_inter, univ_inter, card_univ] using (card_sdiff_of_subset (subset_univ s))