AFTD Auto-Formalizing Theoretical Domains

binary_partial_word_cube_disjoint

theoremverified

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

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.

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

    line 9

      rcases h with ⟨v, hv, hbc⟩
  2. 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.

    lines 10–11

    uses Finset.disjoint_left.mpr

      apply Finset.disjoint_left.mpr
      intro f hf hg
  3. 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).

    lines 12–13

    uses binary_partial_word_cube_mem, mem_inter

      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))
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

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