binary_partial_word_cube_cover_iff
A family of partial-word cubes covers the whole Boolean cube exactly when every Boolean assignment agrees with one of the partial words on its support.
Statement
theorem binary_partial_word_cube_cover_iff {I V : Type*} [Fintype I] [Fintype V] [DecidableEq V] (s : I → Finset V) (b : I → V → Bool) : (univ.biUnion (fun i => binary_partial_word_cube (s i) (b i))) = univ ↔ ∀ f : V → Bool, ∃ i, ∀ v ∈ s i, f v = b i v
- 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 2
- binary_partial_word_cubeThe finite Boolean cube determined by fixing the coordinates of a finite support to the values of a Boolean word.
- binary_partial_word_cube_memMembership in a partial-word cube is exactly agreement on every supported coordinate.
- Used by 3
- binary_partial_word_partition_both_bitsEvery mentioned coordinate of a finite partial-word cube partition occurs with both Boolean values.
- binary_partial_word_partition_twinsIf a coordinate appears in exactly two parts of a Boolean cube partition, once at each value, those parts have equal supports and agree at…
- binary_partial_word_partition_restrictFixing one coordinate of a finite partial-word cube partition and retaining the compatible words gives a partition with the same…
The proof, explained
The equivalence is established in two directions. In the forward direction, if the union of partial-word cubes covers the entire universe, any assignment belongs to the union and thus to some cube $i$, meaning it agrees with $b_i$ on $s_i$. In the reverse direction, if every assignment agrees with some $b_i$ on $s_i$, then every assignment belongs to at least one cube; hence every assignment belongs to the union, which implies the union is the whole universe.
The equivalence reduces to proving the forward and backward implications.
We enable classical reasoning and split the if-and-only-if statement into two subgoals: showing that coverage implies every assignment matches some partial word, and showing the converse.
classical constructorUnder the assumption that the cubes cover the universe, any given assignment belongs to their union.
Assume that the union of cubes equals `univ`, and consider an arbitrary assignment $f : V \to \text{Bool}$. Rewriting by this assumption, $f$ belongs to the union if and only if $f \in \text{univ}$, which holds by `mem_univ`.
uses
mem_univ· intro h f have hf : f ∈ univ.biUnion (fun i => binary_partial_word_cube (s i) (b i)) := by rw [h] exact mem_univ _
There exists an index $i$ such that $f$ agrees with the partial word $b_i$ on its support $s_i$.
Since $f$ belongs to the indexed union, `mem_biUnion` provides an index $i$ such that $f$ is in the partial-word cube indexed by $i$. By `binary_partial_word_cube_mem`, membership in this cube is equivalent to $f(v) = b_i(v)$ for all $v \in s_i$.
uses
mem_biUnion,binary_partial_word_cube_memrcases mem_biUnion.mp hf with ⟨i, hi, hfi⟩ exact ⟨i, (binary_partial_word_cube_mem _ _ _).mp hfi⟩
In the converse direction, it suffices to show that every assignment belongs to the union of cubes.
Assume that every assignment agrees with some partial word on its support. To show that the union of the cubes equals `univ`, `eq_univ_of_forall` reduces the goal to showing that an arbitrary assignment $f$ belongs to the union.
uses
eq_univ_of_forall· intro h apply eq_univ_of_forall intro f
Every assignment $f$ belongs to the union of the partial-word cubes.
Applying the hypothesis to $f$ gives an index $i$ such that $f$ agrees with $b_i$ on $s_i$. By `binary_partial_word_cube_mem`, this agreement implies $f$ belongs to the subcube for $i$. Since $i \in \text{univ}$ by `mem_univ`, `mem_biUnion` places $f$ in the union of all cubes.
uses
binary_partial_word_cube_mem,mem_univ,mem_biUnionobtain ⟨i, hi⟩ := h f exact mem_biUnion.mpr ⟨i, mem_univ _, (binary_partial_word_cube_mem _ _ _).mpr hi⟩
mem_univ- Every element of a finite type belongs to the universal set `univ`.
mem_biUnion- An element belongs to an indexed union of finite sets if and only if it belongs to at least one set in the family.
binary_partial_word_cube_mem- A full Boolean assignment belongs to a partial-word subcube if and only if it agrees with the given partial word on all variables in its support.
eq_univ_of_forall- A finite set equals the universal set `univ` if every element of the ambient finite type belongs to it.
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_cover_iff {I V : Type*} [Fintype I] [Fintype V] [DecidableEq V] (s : I → Finset V) (b : I → V → Bool) : (univ.biUnion (fun i => binary_partial_word_cube (s i) (b i))) = univ ↔ ∀ f : V → Bool, ∃ i, ∀ v ∈ s i, f v = b i v := by classical constructor · intro h f have hf : f ∈ univ.biUnion (fun i => binary_partial_word_cube (s i) (b i)) := by rw [h] exact mem_univ _ rcases mem_biUnion.mp hf with ⟨i, hi, hfi⟩ exact ⟨i, (binary_partial_word_cube_mem _ _ _).mp hfi⟩ · intro h apply eq_univ_of_forall intro f obtain ⟨i, hi⟩ := h f exact mem_biUnion.mpr ⟨i, mem_univ _, (binary_partial_word_cube_mem _ _ _).mpr hi⟩