binary_partial_word_cube_mem
Membership in a partial-word cube is exactly agreement on every supported coordinate.
Statement
theorem binary_partial_word_cube_mem {V : Type*} [Fintype V] [DecidableEq V] (s : Finset V) (b f : V → Bool) : f ∈ binary_partial_word_cube s b ↔ ∀ v ∈ s, f v = b 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 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 7
- binary_partial_word_cube_sign_sumThe sum of a coordinate sign on a partial-word cube is its cardinality times the signed incidence of that coordinate.
- binary_partial_word_cube_odd_sumA rational function which changes sign under flipping a free coordinate of a partial-word cube sums to zero on that cube.
- binary_partial_word_cube_cover_iffA family of partial-word cubes covers the whole Boolean cube exactly when every Boolean assignment agrees with one of the partial words on…
- binary_partial_word_cube_disjointTwo partial-word cubes with a conflicting supported coordinate are disjoint.
- 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_cube_sign_pair_sumFor distinct coordinates, their sign product summed on a partial-word cube equals its cardinality times the two signed incidences.
- binary_partial_word_partition_momentsFor a partition by pairwise conflicting partial-word cubes, the cardinality-weighted first signed incidences and mixed signed incidences…
The proof, explained
The proof unfolds the definition of the partial-word cube as a product of coordinate sets (Fintype.piFinset), where coordinates in s are restricted to {b v} and coordinates outside s are unrestricted (univ). Using Fintype.mem_piFinset, membership in the cube is characterized as satisfying this condition coordinatewise for every vertex v. The two directions of the equivalence then follow by a case split on whether v ∈ s: for v ∈ s, the condition reduces to f v = b v, and for v ∉ s, the condition holds trivially since f v ∈ univ.
Cube membership is equivalent to satisfying coordinatewise membership conditions, reducing the proof to two implications.
By definition, binary_partial_word_cube is the Cartesian product (Fintype.piFinset) of coordinate sets taking value {b v} when v ∈ s and univ when v ∉ s. Applying Fintype.mem_piFinset rewrites membership of f in the cube into the condition that f a belongs to this coordinate set for all a ∈ V. The constructor tactic then splits the equivalence into forward and reverse implications.
uses
binary_partial_word_cube,Fintype.mem_piFinsetclassical simp only [binary_partial_word_cube, Fintype.mem_piFinset] constructor
If f belongs to the partial-word cube, then f v = b v for all v ∈ s.
Assume f satisfies the coordinatewise condition, and let v ∈ s. Since v ∈ s, the conditional expression simplifies via if_pos to the singleton {b v}. The condition f v ∈ {b v} then simplifies via mem_singleton to f v = b v.
uses
if_pos,mem_singleton· intro h v hv simpa only [if_pos hv, mem_singleton] using h v
If f agrees with b on all v ∈ s, then f belongs to the partial-word cube.
Assume f v = b v for all v ∈ s. To verify that f belongs to the cube, we must show that for any coordinate v, f v belongs to (if v ∈ s then {b v} else univ). We split into cases on whether v ∈ s: if v ∈ s, the condition simplifies via if_pos to f v ∈ {b v}, which holds by mem_singleton from the hypothesis f v = b v; if v ∉ s, the condition simplifies via if_neg to f v ∈ univ, which holds trivially by mem_univ.
uses
if_pos,mem_singleton,if_neg,mem_univ· intro h v by_cases hv : v ∈ s · simpa only [if_pos hv, mem_singleton] using h v hv · simp only [if_neg hv, mem_univ]
binary_partial_word_cube- The definition of the binary partial-word cube as the finite product of coordinate sets, equal to {b v} for v ∈ s and univ otherwise.
Fintype.mem_piFinset- A function f belongs to a finite product of sets Fintype.piFinset t if and only if f a ∈ t a for every coordinate a.
if_pos- If condition c is true, then (if c then t else e) = t.
if_neg- If condition c is false, then (if c then t else e) = e.
mem_singleton- An element x belongs to the singleton {y} if and only if x = y.
mem_univ- Every element of a finite type belongs to univ, the universal finite set.
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_mem {V : Type*} [Fintype V] [DecidableEq V] (s : Finset V) (b f : V → Bool) : f ∈ binary_partial_word_cube s b ↔ ∀ v ∈ s, f v = b v := by classical simp only [binary_partial_word_cube, Fintype.mem_piFinset] constructor · intro h v hv simpa only [if_pos hv, mem_singleton] using h v · intro h v by_cases hv : v ∈ s · simpa only [if_pos hv, mem_singleton] using h v hv · simp only [if_neg hv, mem_univ]