AFTD Auto-Formalizing Theoretical Domains

binary_partial_word_partition_both_bits

theoremverified

Every mentioned coordinate of a finite partial-word cube partition occurs with both Boolean values.

Statement

theorem binary_partial_word_partition_both_bits {I V : Type*} [Fintype I] [Fintype V]
    [DecidableEq V] (s : I → Finset V) (b : I → V → Bool)
    (hconflict : ∀ i j, i ≠ j → ∃ v ∈ s i ∩ s j, b i v ≠ b j v)
    (hcover : (univ.biUnion (fun i => binary_partial_word_cube (s i) (b i))) = univ)
    (v : V) (hessential : ∃ i, v ∈ s i) :
    ∀ bit : Bool, ∃ i, v ∈ s i ∧ b i v = bit
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_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…
Used by 2

The proof, explained

Given a coordinate v fixed by some subcube i in the partition, consider the Boolean word f obtained by flipping the value of b(i) at v. Because the subcubes cover the entire hypercube, f must belong to some subcube j. This subcube j must be distinct from i and must also fix coordinate v, since otherwise the conflict coordinate between i and j would force f to take two different values at that coordinate. Thus j fixes v to the opposite bit ¬b(i)(v), showing that both Boolean values are attained at v.

  1. We select a subcube i fixing coordinate v, define a word f by flipping the bit at v, and obtain a subcube j that covers f.

    By the assumption that v is essential (hessential), there is some subcube index i with v ∈ s(i). We define f to agree with b(i) at every coordinate except v, where its value is inverted to ¬b(i)(v). Since the subcubes cover the hypercube (hcover), binary_partial_word_cube_cover_iff provides a subcube j such that f agrees with b(j) on all coordinates in s(j).

    lines 11–14

    uses binary_partial_word_cube_cover_iff

      classical
      obtain ⟨i, hi⟩ := hessential
      let f := Function.update (b i) v (!(b i v))
      obtain ⟨j, hj⟩ := (binary_partial_word_cube_cover_iff s b).mp hcover f
  2. The covering subcube j is distinct from i.

    Flipping a Boolean bit always produces a different value (hflip). If i = j, then because v ∈ s(i), the covering condition for j would give f(v) = b(i)(v). But by definition, f(v) = ¬b(i)(v) via Function.update_self, which would imply ¬b(i)(v) = b(i)(v), a contradiction.

    lines 15–20

    uses Function.update_self

      have hflip : (!(b i v)) ≠ b i v := by cases b i v <;> decide
      have hij : i ≠ j := by
        intro heq
        subst j
        have he := hj v hi
        exact hflip (by simpa only [f, Function.update_self] using he)
  3. The subcube j also fixes coordinate v, that is, v ∈ s(j).

    Suppose for contradiction that v ∉ s(j). Since i ≠ j, the partition conflict hypothesis (hconflict) guarantees a coordinate w ∈ s(i) ∩ s(j) where b(i)(w) ≠ b(j)(w). Because w ∈ s(j) and v ∉ s(j), we must have w ≠ v. Since w ≠ v, updating f at v leaves coordinate w unchanged (Function.update_of_ne), so f(w) = b(i)(w). But because w ∈ s(j), the covering property of j requires f(w) = b(j)(w). Hence b(i)(w) = b(j)(w), contradicting b(i)(w) ≠ b(j)(w).

    lines 21–26

    uses Function.update_of_ne

      have hvj : v ∈ s j := by
        by_contra hn
        obtain ⟨w, hw, hne⟩ := hconflict i j hij
        have hwv : w ≠ v := by rintro rfl; exact hn (mem_inter.mp hw).2
        have he := hj w (mem_inter.mp hw).2
        exact hne (by simpa only [f, Function.update_of_ne hwv] using he)
  4. Subcube j assigns to coordinate v the flipped bit, b(j)(v) = ¬b(i)(v).

    Since v ∈ s(j), the covering property ensures b(j)(v) = f(v). Evaluating f at v via Function.update_self gives ¬b(i)(v).

    lines 27–28

    uses Function.update_self

      have hbj : b j v = !(b i v) := by
        simpa only [f, Function.update_self] using (hj v hvj).symm
  5. For every Boolean value bit, some subcube fixes v to that value.

    Given any bit, we split on whether b(i)(v) = bit. If so, subcube i witnesses the claim since v ∈ s(i) and b(i)(v) = bit. If not, then because Bool has only two values, the flipped bit ¬b(i)(v) must equal bit. Subcube j then witnesses the claim since v ∈ s(j) and b(j)(v) = ¬b(i)(v) = bit.

    lines 29–33

      intro bit
      by_cases hbit : b i v = bit
      · exact ⟨i, hi, hbit⟩
      · refine ⟨j, hvj, hbj.trans ?_⟩
        cases hbi : b i v <;> cases bit <;> simp_all
binary_partial_word_cube_cover_iff
A collection of partial-word cubes covers the entire space of Boolean functions on V if and only if every Boolean function agrees with at least one cube on all coordinates fixed by that cube.
Function.update_self
Updating a function at an input coordinate and then evaluating at that same coordinate yields the updated value.
Function.update_of_ne
Updating a function at an input coordinate does not change its value when evaluated at any distinct coordinate.

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_partition_both_bits {I V : Type*} [Fintype I] [Fintype V]    [DecidableEq V] (s : I → Finset V) (b : I → V → Bool)    (hconflict : ∀ i j, i ≠ j → ∃ v ∈ s i ∩ s j, b i v ≠ b j v)    (hcover : (univ.biUnion (fun i => binary_partial_word_cube (s i) (b i))) = univ)    (v : V) (hessential : ∃ i, v ∈ s i) :    ∀ bit : Bool, ∃ i, v ∈ s i ∧ b i v = bit := by  classical  obtain ⟨i, hi⟩ := hessential  let f := Function.update (b i) v (!(b i v))  obtain ⟨j, hj⟩ := (binary_partial_word_cube_cover_iff s b).mp hcover f  have hflip : (!(b i v)) ≠ b i v := by cases b i v <;> decide  have hij : i ≠ j := by    intro heq    subst j    have he := hj v hi    exact hflip (by simpa only [f, Function.update_self] using he)  have hvj : v ∈ s j := by    by_contra hn    obtain ⟨w, hw, hne⟩ := hconflict i j hij    have hwv : w ≠ v := by rintro rfl; exact hn (mem_inter.mp hw).2    have he := hj w (mem_inter.mp hw).2    exact hne (by simpa only [f, Function.update_of_ne hwv] using he)  have hbj : b j v = !(b i v) := by    simpa only [f, Function.update_self] using (hj v hvj).symm  intro bit  by_cases hbit : b i v = bit  · exact ⟨i, hi, hbit⟩  · refine ⟨j, hvj, hbj.trans ?_⟩    cases hbi : b i v <;> cases bit <;> simp_all
See it in the graphDiscuss this resultChallenge it