binary_partial_word_partition_order_convex
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
- 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_restrict_supportRestrict the support of a partial word to the coordinate subtype excluding one specified coordinate.
- binary_partial_word_partition_restrictFixing one coordinate of a finite partial-word cube partition and retaining the compatible words gives a partition with the same…
- binary_partial_word_partition_singular_coordinateA finite Boolean cube partition mentioning every coordinate and having exactly one more part than coordinates, with a nonempty coordinate…
- binary_partial_word_partition_twinsIf a coordinate appears in exactly two parts of a Boolean cube partition, once at each value, those parts have equal supports and agree at…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- ordered_biclique_minimum_incidence_intervalsLet g be positive and take g-1 bicliques indexed by cuts r+1 of the ordered set Fin g, with the first side strictly above r and the second…
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.
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.
uses
Nat.strong_induction_on,Fintype.card_eq_zero_iff.mp,isEmptyElimclassical 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
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₁.
uses
Fintype.card_pos_iff.mp,binary_partial_word_partition_singular_coordinate,binary_partial_word_partition_twinshaveI : 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₁
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.
uses
ne_of_lt,ne_of_gt,not_lt_of_gthave 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)
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.
uses
Or.inl,Or.inrlet 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⟩
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).
uses
lt_of_le_of_ne,le_of_not_gthave 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
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₁).
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]
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).
uses
binary_partial_word_partition_restrict,Fintype.card_subtype_eq,Fintype.card_subtype_compl,Fintype.card_subtype,card_filter_add_card_filter_nothave 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'
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).
uses
lt_of_le_of_ne,Ne.symmintro 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
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).
· 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.
- The induction on the number of coordinates n uses strong induction. Restricting the partition by fixing the singular coordinate v = false leaves i₀ and removes twin i₁; the retraction π mapping i₁ ↦ i₀ is monotone precisely because the twins are adjacent in the linear order.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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