binary_partial_word_cube_disjoint
Two partial-word cubes with a conflicting supported coordinate are disjoint.
Statement
theorem binary_partial_word_cube_disjoint {V : Type*} [Fintype V] [DecidableEq V] (s t : Finset V) (b c : V → Bool) (h : ∃ v ∈ s ∩ t, b v ≠ c v) : Disjoint (binary_partial_word_cube s b) (binary_partial_word_cube t c)
- 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_momentsFor a partition by pairwise conflicting partial-word cubes, the cardinality-weighted first signed incidences and mixed signed incidences…
- 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
To show that the two partial-word cubes are disjoint, the proof unpacks the hypothesis to obtain a coordinate v in the intersection of both supports where the patterns b and c disagree. It then assumes for contradiction that some function f belongs to both cubes. By definition of a partial-word cube, f(v) must equal both b(v) and c(v), forcing b(v) = c(v), which contradicts the disagreement at v.
Extract a coordinate v in both supports on which the patterns disagree.
Unpack the existential hypothesis h to obtain a coordinate v ∈ s ∩ t (named hv) such that b(v) ≠ c(v) (named hbc).
rcases h with ⟨v, hv, hbc⟩
To show the cubes are disjoint, it suffices to derive a contradiction from a function belonging to both.
By Finset.disjoint_left.mpr, proving disjointness reduces to showing that no element belongs to both sets. Assume for contradiction that f is a function belonging to both cubes, with hypotheses hf : f ∈ binary_partial_word_cube s b and hg : f ∈ binary_partial_word_cube t c.
uses
Finset.disjoint_left.mprapply Finset.disjoint_left.mpr intro f hf hg
Contradiction: the function f forces b(v) = c(v), but b(v) ≠ c(v).
Since v ∈ s ∩ t, we have v ∈ s and v ∈ t by mem_inter. Because f belongs to the first cube, binary_partial_word_cube_mem implies f(v) = b(v), so b(v) = f(v). Because f belongs to the second cube, it implies f(v) = c(v). By transitivity of equality, b(v) = c(v), contradicting the hypothesis hbc that b(v) ≠ c(v).
uses
binary_partial_word_cube_mem,mem_interexact hbc ((binary_partial_word_cube_mem s b f).mp hf v (mem_inter.mp hv).1 |>.symm.trans ((binary_partial_word_cube_mem t c f).mp hg v (mem_inter.mp hv).2))
Finset.disjoint_left.mpr- Two finite sets are disjoint if no element of the first set belongs to the second set.
binary_partial_word_cube_mem- A function belongs to the partial-word cube defined by a support set s and pattern b if and only if it agrees with b on every coordinate in s.
mem_inter- An element belongs to the intersection of two finite sets if and only if it belongs to both sets.
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_disjoint {V : Type*} [Fintype V] [DecidableEq V] (s t : Finset V) (b c : V → Bool) (h : ∃ v ∈ s ∩ t, b v ≠ c v) : Disjoint (binary_partial_word_cube s b) (binary_partial_word_cube t c) := by rcases h with ⟨v, hv, hbc⟩ apply Finset.disjoint_left.mpr intro f hf hg exact hbc ((binary_partial_word_cube_mem s b f).mp hf v (mem_inter.mp hv).1 |>.symm.trans ((binary_partial_word_cube_mem t c f).mp hg v (mem_inter.mp hv).2))