AFTD Auto-Formalizing Theoretical Domains

binary_partial_word_cube_mem

theoremverified

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

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.

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

    lines 8–10

    uses binary_partial_word_cube, Fintype.mem_piFinset

      classical
      simp only [binary_partial_word_cube, Fintype.mem_piFinset]
      constructor
  2. 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.

    lines 11–12

    uses if_pos, mem_singleton

      · intro h v hv
        simpa only [if_pos hv, mem_singleton] using h v
  3. 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.

    lines 13–16

    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

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