AFTD Auto-Formalizing Theoretical Domains

binary_partial_word_cube_cover_iff

theoremverified

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
Used by 3

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.

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

    lines 9–10

      classical
      constructor
  2. Under 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`.

    lines 11–14

    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 _
  3. 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$.

    lines 15–16

    uses mem_biUnion, binary_partial_word_cube_mem

        rcases mem_biUnion.mp hf with ⟨i, hi, hfi⟩
        exact ⟨i, (binary_partial_word_cube_mem _ _ _).mp hfi⟩
  4. 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.

    lines 17–19

    uses eq_univ_of_forall

      · intro h
        apply eq_univ_of_forall
        intro f
  5. 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.

    lines 20–21

    uses binary_partial_word_cube_mem, mem_univ, mem_biUnion

        obtain ⟨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

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