AFTD Auto-Formalizing Theoretical Domains

binary_partial_word_partition_order_convex

theoremverified

In a finite Boolean cube partition with one more part than mentioned coordinates, linearly order the parts so that every false occurrence of a coordinate precedes every true occurrence. Then the parts mentioning any given coordinate form an order-convex set.

Statement

theorem binary_partial_word_partition_order_convex (n : ℕ)
    {I V : Type*} [Fintype I] [LinearOrder 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)
    (hessential : ∀ v, ∃ i, v ∈ s i)
    (hsize : Fintype.card V = n)
    (hcard : Fintype.card I = Fintype.card V + 1)
    (horder : ∀ v i j, v ∈ s i → v ∈ s j → b i v = false → b j v = true → i < j) :
    ∀ v i j k, i ≤ j → j ≤ k → v ∈ s i → v ∈ s k → v ∈ s j
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 7
Used by 1

The proof, explained

The proof proceeds by strong induction on the number of coordinates n = |V|. In the inductive step, a singular coordinate v is identified that appears in exactly two parts i₀ and i₁, which form an adjacent pair of 'twins' in the linear order: they have the same coordinate support, agree everywhere except on v, and satisfy i₀ < i₁ with no parts between them. Restricting the partition to the subcube where v = false collapses the twins via a monotone retraction π : I → J (sending i₁ to i₀) to obtain a valid partition on n - 1 coordinates. Applying the induction hypothesis to the restricted partition and pulling convexity back through π establishes order-convexity for all coordinates w ≠ v, while the adjacency of the twins directly yields convexity for v.

  1. The theorem holds vacuously when the coordinate set V is empty (n = 0).

    We set up strong induction on n = |V|. In the base case n = 0, the cardinality of V is zero, so V is empty (by Fintype.card_eq_zero_iff.mp). The universal statement over coordinates v ∈ V holds vacuously via isEmptyElim.

    lines 15–22

    uses Nat.strong_induction_on, Fintype.card_eq_zero_iff.mp, isEmptyElim

      classical
      induction n using Nat.strong_induction_on generalizing I V with
      | h n ih =>
        by_cases hn : n = 0
        · have hV : Fintype.card V = 0 := hsize.trans hn
          haveI : IsEmpty V := Fintype.card_eq_zero_iff.mp hV
          intro v
          exact isEmptyElim v
  2. When n > 0, there exists a singular coordinate v appearing in exactly two twin parts i₀ < i₁.

    Since n > 0, V is nonempty (by Fintype.card_pos_iff.mp). By binary_partial_word_partition_singular_coordinate, there exists a singular coordinate v appearing with bit false in exactly one part and bit true in exactly one part. By binary_partial_word_partition_twins, these parts are twins: distinct indices i₀ and i₁ with b(i₀, v) = false and b(i₁, v) = true, which are the only parts mentioning v (honly), share identical support s(i₀) = s(i₁), and agree on all other coordinates. The ordering hypothesis horder then forces i₀ < i₁.

    lines 23–28

    uses Fintype.card_pos_iff.mp, binary_partial_word_partition_singular_coordinate, binary_partial_word_partition_twins

        haveI : Nonempty V := Fintype.card_pos_iff.mp (by omega)
        obtain ⟨v, hsing⟩ := binary_partial_word_partition_singular_coordinate
          s b hconflict hcover hessential hcard
        obtain ⟨i₀, i₁, hne, hv₀, hb₀, hv₁, hb₁, honly, hsame, hbits⟩ :=
          binary_partial_word_partition_twins s b hconflict hcover v hsing
        have h₀₁ : i₀ < i₁ := horder v i₀ i₁ hv₀ hv₁ hb₀ hb₁
  3. The twins i₀ and i₁ are immediately adjacent in the linear order: no part j satisfies i₀ < j < i₁.

    Suppose, for contradiction, that there is some part j with i₀ < j < i₁. Since i₀ ≠ j, the conflict hypothesis provides a coordinate w ∈ s(i₀) ∩ s(j) where b(i₀, w) ≠ b(j, w). Because v only belongs to i₀ and i₁, w cannot be v. Since s(i₀) = s(i₁) and the twins agree away from v, w also belongs to s(i₁) with b(i₁, w) = b(i₀, w). If b(i₀, w) = false, then b(j, w) = true and b(i₁, w) = false, so the ordering hypothesis horder requires i₁ < j, contradicting j < i₁. If b(i₀, w) = true, then b(j, w) = false, so horder requires j < i₀, contradicting i₀ < j. In either case we obtain a contradiction.

    lines 29–51

    uses ne_of_lt, ne_of_gt, not_lt_of_gt

        have hadj (j : I) (h₀j : i₀ < j) (hj₁ : j < i₁) : False := by
          obtain ⟨w, hw, hdiff⟩ := hconflict i₀ j (ne_of_lt h₀j)
          have hwv : w ≠ v := by
            intro he
            subst w
            rcases honly j (mem_inter.mp hw).2 with hj | hj
            · exact (ne_of_gt h₀j) hj
            · exact (ne_of_lt hj₁) hj
          have hwi₁ : w ∈ s i₁ := hsame ▸ (mem_inter.mp hw).1
          have hbitse := hbits w (mem_inter.mp hw).1 hwv
          cases hb : b i₀ w
          · have hbj : b j w = true := by
              cases hbj : b j w
              · exact (hdiff (hb.trans hbj.symm)).elim
              · rfl
            have hbi₁ : b i₁ w = false := hbitse.symm.trans hb
            exact (not_lt_of_gt hj₁) (horder w i₁ j hwi₁ (mem_inter.mp hw).2 hbi₁ hbj)
          · have hbj : b j w = false := by
              cases hbj : b j w
              · rfl
              · exact (hdiff (hb.trans hbj.symm)).elim
            exact (not_lt_of_gt h₀j) (horder w j i₀ (mem_inter.mp hw).2
              (mem_inter.mp hw).1 hbj hb)
  4. Define the restricted coordinate set W = V \ {v}, the surviving parts J = I \ {i₁}, and a retraction map π : I → J sending i₁ to i₀.

    We restrict to the subcube where v is false. The coordinates become W = {w : V // w ≠ v}, and the surviving parts are J = {i : I // v ∉ s(i) ∨ b(i, v) = false}. Since i₁ is the only part fixing v to true, every other index i ≠ i₁ belongs to J (hsurv). We define the retraction π : I → J mapping i₁ to i₀ (using Or.inr hb₀) and fixing all other parts.

    lines 52–62

    uses Or.inl, Or.inr

        let J := {i : I // v ∉ s i ∨ b i v = false}
        let W := {w : V // w ≠ v}
        let t : J → Finset W := fun i => binary_partial_word_restrict_support (s i.val) v
        let c : J → W → Bool := fun i w => b i.val w.val
        have hsurv (i : I) (hi : i ≠ i₁) : v ∉ s i ∨ b i v = false := by
          by_cases hvi : v ∈ s i
          · right
            have hi₀ : i = i₀ := (honly i hvi).resolve_right hi
            simpa only [hi₀] using hb₀
          · exact Or.inl hvi
        let π : I → J := fun i => if h : i = i₁ then ⟨i₀, Or.inr hb₀⟩ else ⟨i, hsurv i h⟩
  5. The retraction π : I → J is monotone.

    Given i ≤ j, we verify that π(i) ≤ π(j). When neither or both equal i₁, order is trivial. If i = i₁ and j ≠ i₁, then i₀ < i₁ ≤ j implies π(i) = i₀ ≤ j = π(j). If i ≠ i₁ and j = i₁, then i < i₁; since no part lies strictly between i₀ and i₁ (hadj), we have i ≤ i₀, so π(i) = i ≤ i₀ = π(j).

    lines 63–75

    uses lt_of_le_of_ne, le_of_not_gt

        have hπmono : Monotone π := by
          intro i j hij
          change (π i).val ≤ (π j).val
          by_cases hi : i = i₁
          · by_cases hj : j = i₁
            · simp [π, hi, hj]
            · have h₀j : i₀ ≤ j := h₀₁.le.trans (hi ▸ hij)
              simpa only [π, dif_pos hi, dif_neg hj] using h₀j
          · by_cases hj : j = i₁
            · have hi₁ : i < i₁ := lt_of_le_of_ne (hj ▸ hij) hi
              have hi₀ : i ≤ i₀ := le_of_not_gt (fun h₀i => hadj i h₀i hi₁)
              simpa only [π, dif_neg hi, dif_pos hj] using hi₀
            · simpa only [π, dif_neg hi, dif_neg hj] using hij
  6. For any coordinate w ∈ W and part i ∈ I, w ∈ t(π(i)) ↔ w ∈ s(i).

    When i ≠ i₁, π(i) = i and the restricted support t(i) coincides with s(i) \ {v}. When i = i₁, π(i₁) = i₀; because the twins have identical supports s(i₀) = s(i₁), w ∈ t(i₀) ↔ w ∈ s(i₀) ↔ w ∈ s(i₁).

    lines 76–83

        have hπmem (w : W) (i : I) : w ∈ t (π i) ↔ w.val ∈ s i := by
          by_cases hi : i = i₁
          · subst i
            simp only [π, dif_pos rfl, t, binary_partial_word_restrict_support, mem_filter,
              mem_univ, true_and]
            rw [hsame]
          · simp only [π, dif_neg hi, t, binary_partial_word_restrict_support,
              mem_filter, mem_univ, true_and]
  7. The restricted system on W and J satisfies the induction hypotheses, yielding order-convexity for all coordinates in W.

    By binary_partial_word_partition_restrict, (t, c) is a conflicting cover of the cube on W. All coordinates in W remain essential. The sizes satisfy |W| = |V| - 1 < n and |J| = |I| - 1 = |W| + 1, computed using Fintype.card_subtype_compl, Fintype.card_subtype_eq, Fintype.card_subtype, and card_filter_add_card_filter_not. The ordering condition horder' is inherited from I. Thus the strong induction hypothesis ih applies to (W, J, t, c).

    lines 84–113

    uses binary_partial_word_partition_restrict, Fintype.card_subtype_eq, Fintype.card_subtype_compl, Fintype.card_subtype, card_filter_add_card_filter_not

        have hr := binary_partial_word_partition_restrict s b hconflict hcover v false
        have hess : ∀ w : W, ∃ i : J, w ∈ t i := by
          intro w
          obtain ⟨i, hi⟩ := hessential w.val
          exact ⟨π i, (hπmem w i).mpr hi⟩
        have hW : Fintype.card W = Fintype.card V - 1 := by
          simpa only [W, Fintype.card_subtype_eq] using
            Fintype.card_subtype_compl (fun w : V => w = v)
        have hJ : Fintype.card J + 1 = Fintype.card I := by
          rw [Fintype.card_subtype]
          have he : (univ.filter (fun i : I => ¬(v ∉ s i ∨ b i v = false))) =
              univ.filter (fun i => v ∈ s i ∧ b i v = true) := by
            ext i
            by_cases hv : v ∈ s i
            · cases hb : b i v <;> simp [hv, hb]
            · simp [hv]
          have hc := card_filter_add_card_filter_not (s := univ)
            (fun i : I => v ∉ s i ∨ b i v = false)
          simpa only [he, hsing true, card_univ] using hc
        have hcard' : Fintype.card J = Fintype.card W + 1 := by omega
        have hlt : Fintype.card W < n := by omega
        have horder' : ∀ w (i j : J), w ∈ t i → w ∈ t j →
            c i w = false → c j w = true → i < j := by
          intro w i j hi hj hbi hbj
          apply horder w.val i.val j.val
          · exact (mem_filter.mp hi).2
          · exact (mem_filter.mp hj).2
          · exact hbi
          · exact hbj
        have hind := ih (Fintype.card W) hlt t c hr.1 hr.2 hess rfl hcard' horder'
  8. Order-convexity holds in I for the singular coordinate w = v.

    Suppose i ≤ j ≤ k with v ∈ s(i) and v ∈ s(k). Since v only appears in i₀ and i₁ (with i₀ < i₁), we must have i₀ ≤ i and k ≤ i₁, so i₀ ≤ j ≤ i₁. Because no part lies strictly between the twins i₀ and i₁ (hadj), j must equal either i₀ or i₁. In either case, v ∈ s(j).

    lines 114–131

    uses lt_of_le_of_ne, Ne.symm

        intro w i j k hij hjk hwi hwk
        by_cases hwv : w = v
        · subst w
          have h₀i : i₀ ≤ i := by
            rcases honly i hwi with hi | hi
            · exact hi.symm.le
            · simpa only [hi] using h₀₁.le
          have hk₁ : k ≤ i₁ := by
            rcases honly k hwk with hk | hk
            · simpa only [hk] using h₀₁.le
            · exact hk.le
          have h₀j : i₀ ≤ j := h₀i.trans hij
          have hj₁ : j ≤ i₁ := hjk.trans hk₁
          by_cases hj₀ : j = i₀
          · simpa only [hj₀] using hv₀
          by_cases hj₁eq : j = i₁
          · simpa only [hj₁eq] using hv₁
          exact (hadj j (lt_of_le_of_ne h₀j (Ne.symm hj₀)) (lt_of_le_of_ne hj₁ hj₁eq)).elim
  9. Order-convexity holds in I for any coordinate w ≠ v.

    Given i ≤ j ≤ k with w ∈ s(i) and w ∈ s(k), where w ≠ v, monotonicity of π yields π(i) ≤ π(j) ≤ π(k) in J. Viewing w as an element of W, the support correspondence gives w ∈ t(π(i)) and w ∈ t(π(k)). By the induction hypothesis on J, w ∈ t(π(j)). Converting back via the support correspondence, we conclude w ∈ s(j).

    lines 132–134

        · have hs := hind ⟨w, hwv⟩ (π i) (π j) (π k) (hπmono hij) (hπmono hjk)
            ((hπmem ⟨w, hwv⟩ i).mpr hwi) ((hπmem ⟨w, hwv⟩ k).mpr hwk)
          exact (hπmem ⟨w, hwv⟩ j).mp hs
Nat.strong_induction_on
Strong induction on natural numbers: to prove a statement for all n, it suffices to prove it for n assuming it holds for all m < n.
Fintype.card_eq_zero_iff.mp
A finite type with cardinality zero is empty.
isEmptyElim
From an element of an empty type, any conclusion can be deduced (ex falso).
Fintype.card_pos_iff.mp
A finite type with strictly positive cardinality is nonempty.
binary_partial_word_partition_singular_coordinate
In a Boolean cube partition with |I| = |V| + 1, there exists a singular coordinate that occurs with bit value false in exactly one part and with bit value true in exactly one part.
binary_partial_word_partition_twins
For a singular coordinate v, the unique two parts mentioning it are twins: they have identical coordinate supports, agree on all other coordinates, and assign opposite values to v.
ne_of_lt
In a preorder, a strictly smaller element is not equal to a larger element.
ne_of_gt
In a preorder, a strictly larger element is not equal to a smaller element.
not_lt_of_gt
In a preorder, if a < b, then b cannot be strictly less than a.
Or.inl
Disjunction introduction from the left: P implies P ∨ Q.
Or.inr
Disjunction introduction from the right: Q implies P ∨ Q.
lt_of_le_of_ne
In a partial order, if a ≤ b and a ≠ b, then a < b.
le_of_not_gt
In a linear order, if b is not strictly less than a, then a ≤ b.
binary_partial_word_partition_restrict
Restricting a partition of the Boolean cube by fixing a coordinate v to a bit value yields a valid conflicting partition covering the cube on the remaining coordinates.
Fintype.card_subtype_eq
The subtype of elements equal to a fixed element y has cardinality 1.
Fintype.card_subtype_compl
The cardinality of the subtype satisfying ¬p equals the total cardinality minus the cardinality of the subtype satisfying p.
Fintype.card_subtype
The cardinality of a subtype {x // p x} is the cardinality of the filtered finset of elements satisfying p.
card_filter_add_card_filter_not
For any finite set and predicate p, the number of elements satisfying p plus the number of elements not satisfying p equals the total size of the set.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.

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_order_convex (n : ℕ)    {I V : Type*} [Fintype I] [LinearOrder 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)    (hessential : ∀ v, ∃ i, v ∈ s i)    (hsize : Fintype.card V = n)    (hcard : Fintype.card I = Fintype.card V + 1)    (horder : ∀ v i j, v ∈ s i → v ∈ s j → b i v = false → b j v = true → i < j) :    ∀ v i j k, i ≤ j → j ≤ k → v ∈ s i → v ∈ s k → v ∈ s j := by  classical  induction n using Nat.strong_induction_on generalizing I V with  | h n ih =>    by_cases hn : n = 0    · have hV : Fintype.card V = 0 := hsize.trans hn      haveI : IsEmpty V := Fintype.card_eq_zero_iff.mp hV      intro v      exact isEmptyElim v    haveI : Nonempty V := Fintype.card_pos_iff.mp (by omega)    obtain ⟨v, hsing⟩ := binary_partial_word_partition_singular_coordinate      s b hconflict hcover hessential hcard    obtain ⟨i₀, i₁, hne, hv₀, hb₀, hv₁, hb₁, honly, hsame, hbits⟩ :=      binary_partial_word_partition_twins s b hconflict hcover v hsing    have h₀₁ : i₀ < i₁ := horder v i₀ i₁ hv₀ hv₁ hb₀ hb₁    have hadj (j : I) (h₀j : i₀ < j) (hj₁ : j < i₁) : False := by      obtain ⟨w, hw, hdiff⟩ := hconflict i₀ j (ne_of_lt h₀j)      have hwv : w ≠ v := by        intro he        subst w        rcases honly j (mem_inter.mp hw).2 with hj | hj        · exact (ne_of_gt h₀j) hj        · exact (ne_of_lt hj₁) hj      have hwi₁ : w ∈ s i₁ := hsame ▸ (mem_inter.mp hw).1      have hbitse := hbits w (mem_inter.mp hw).1 hwv      cases hb : b i₀ w      · have hbj : b j w = true := by          cases hbj : b j w          · exact (hdiff (hb.trans hbj.symm)).elim          · rfl        have hbi₁ : b i₁ w = false := hbitse.symm.trans hb        exact (not_lt_of_gt hj₁) (horder w i₁ j hwi₁ (mem_inter.mp hw).2 hbi₁ hbj)      · have hbj : b j w = false := by          cases hbj : b j w          · rfl          · exact (hdiff (hb.trans hbj.symm)).elim        exact (not_lt_of_gt h₀j) (horder w j i₀ (mem_inter.mp hw).2          (mem_inter.mp hw).1 hbj hb)    let J := {i : I // v ∉ s i ∨ b i v = false}    let W := {w : V // w ≠ v}    let t : J → Finset W := fun i => binary_partial_word_restrict_support (s i.val) v    let c : J → W → Bool := fun i w => b i.val w.val    have hsurv (i : I) (hi : i ≠ i₁) : v ∉ s i ∨ b i v = false := by      by_cases hvi : v ∈ s i      · right        have hi₀ : i = i₀ := (honly i hvi).resolve_right hi        simpa only [hi₀] using hb₀      · exact Or.inl hvi    let π : I → J := fun i => if h : i = i₁ then ⟨i₀, Or.inr hb₀⟩ else ⟨i, hsurv i h⟩    have hπmono : Monotone π := by      intro i j hij      change (π i).val ≤ (π j).val      by_cases hi : i = i₁      · by_cases hj : j = i₁        · simp [π, hi, hj]        · have h₀j : i₀ ≤ j := h₀₁.le.trans (hi ▸ hij)          simpa only [π, dif_pos hi, dif_neg hj] using h₀j      · by_cases hj : j = i₁        · have hi₁ : i < i₁ := lt_of_le_of_ne (hj ▸ hij) hi          have hi₀ : i ≤ i₀ := le_of_not_gt (fun h₀i => hadj i h₀i hi₁)          simpa only [π, dif_neg hi, dif_pos hj] using hi₀        · simpa only [π, dif_neg hi, dif_neg hj] using hij    have hπmem (w : W) (i : I) : w ∈ t (π i) ↔ w.val ∈ s i := by      by_cases hi : i = i₁      · subst i        simp only [π, dif_pos rfl, t, binary_partial_word_restrict_support, mem_filter,          mem_univ, true_and]        rw [hsame]      · simp only [π, dif_neg hi, t, binary_partial_word_restrict_support,          mem_filter, mem_univ, true_and]    have hr := binary_partial_word_partition_restrict s b hconflict hcover v false    have hess : ∀ w : W, ∃ i : J, w ∈ t i := by      intro w      obtain ⟨i, hi⟩ := hessential w.val      exact ⟨π i, (hπmem w i).mpr hi⟩    have hW : Fintype.card W = Fintype.card V - 1 := by      simpa only [W, Fintype.card_subtype_eq] using        Fintype.card_subtype_compl (fun w : V => w = v)    have hJ : Fintype.card J + 1 = Fintype.card I := by      rw [Fintype.card_subtype]      have he : (univ.filter (fun i : I => ¬(v ∉ s i ∨ b i v = false))) =          univ.filter (fun i => v ∈ s i ∧ b i v = true) := by        ext i        by_cases hv : v ∈ s i        · cases hb : b i v <;> simp [hv, hb]        · simp [hv]      have hc := card_filter_add_card_filter_not (s := univ)        (fun i : I => v ∉ s i ∨ b i v = false)      simpa only [he, hsing true, card_univ] using hc    have hcard' : Fintype.card J = Fintype.card W + 1 := by omega    have hlt : Fintype.card W < n := by omega    have horder' : ∀ w (i j : J), w ∈ t i → w ∈ t j →        c i w = false → c j w = true → i < j := by      intro w i j hi hj hbi hbj      apply horder w.val i.val j.val      · exact (mem_filter.mp hi).2      · exact (mem_filter.mp hj).2      · exact hbi      · exact hbj    have hind := ih (Fintype.card W) hlt t c hr.1 hr.2 hess rfl hcard' horder'    intro w i j k hij hjk hwi hwk    by_cases hwv : w = v    · subst w      have h₀i : i₀ ≤ i := by        rcases honly i hwi with hi | hi        · exact hi.symm.le        · simpa only [hi] using h₀₁.le      have hk₁ : k ≤ i₁ := by        rcases honly k hwk with hk | hk        · simpa only [hk] using h₀₁.le        · exact hk.le      have h₀j : i₀ ≤ j := h₀i.trans hij      have hj₁ : j ≤ i₁ := hjk.trans hk₁      by_cases hj₀ : j = i₀      · simpa only [hj₀] using hv₀      by_cases hj₁eq : j = i₁      · simpa only [hj₁eq] using hv₁      exact (hadj j (lt_of_le_of_ne h₀j (Ne.symm hj₀)) (lt_of_le_of_ne hj₁ hj₁eq)).elim    · have hs := hind ⟨w, hwv⟩ (π i) (π j) (π k) (hπmono hij) (hπmono hjk)        ((hπmem ⟨w, hwv⟩ i).mpr hwi) ((hπmem ⟨w, hwv⟩ k).mpr hwk)      exact (hπmem ⟨w, hwv⟩ j).mp hs
See it in the graphDiscuss this resultChallenge it