AFTD Auto-Formalizing Theoretical Domains

binary_partial_word_cube_card

theoremverified

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

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

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

    lines 8–9

    uses binary_partial_word_cube, Fintype.card_piFinset

      classical
      rw [binary_partial_word_cube, Fintype.card_piFinset]
  2. 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`).

    lines 10–12

    uses apply_ite, card_singleton, card_univ, Fintype.card_bool, prod_ite, prod_const_one, one_mul, prod_const

      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]
  3. 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`).

    lines 13–15

    uses filter_not, filter_mem_eq_inter, univ_inter, card_univ, card_sdiff_of_subset, subset_univ

      congr 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.

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

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