op1370_maximal_free_region_saturation
theoremverified
In a system reaching any valid total-size upper bound, a set incomparable to all other colors belongs to its color either directly or through its complement.
Statement
theorem op1370_maximal_free_region_saturation
(n t : β) (hn : 0 < n) (π : Fin t β Finset (Finset (Fin n)))
(hunc : β i, is_uncomplemented (π i))
(hinc : strongly_incomparable π)
(K : β)
(hupper : β B : Fin t β Finset (Finset (Fin n)),
(β i, is_uncomplemented (B i)) β strongly_incomparable B β
(β i, (B i).card) β€ K)
(heq : (β i, (π i).card) = K)
(i : Fin t) (S : Finset (Fin n))
(hfree : β j, j β i β β T β π j, Β¬ S β T β§ Β¬ T β S) :
S β π i β¨ SαΆ β π i- Source
- Filed by the prover as a step towards another result
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- is_uncomplementedA family of subsets of a finite set is uncomplemented if no set and its complement both belong to the family.
- strongly_incomparableAn indexed family of finset families
π : ΞΉ β Finset (Finset Ξ±)is strongly incomparable if for alli j : ΞΉwithi β j, for allβ¦
- Used by 1
- op1370_maximal_free_regions_incomparableFor a system reaching a valid total-size upper bound, the full compatibility regions of distinct colors are mutually strongly incomparable.
Lean source view module on GitHub
open Finset theorem op1370_maximal_free_region_saturation (n t : β) (hn : 0 < n) (π : Fin t β Finset (Finset (Fin n))) (hunc : β i, is_uncomplemented (π i)) (hinc : strongly_incomparable π) (K : β) (hupper : β B : Fin t β Finset (Finset (Fin n)), (β i, is_uncomplemented (B i)) β strongly_incomparable B β (β i, (B i).card) β€ K) (heq : (β i, (π i).card) = K) (i : Fin t) (S : Finset (Fin n)) (hfree : β j, j β i β β T β π j, Β¬ S β T β§ Β¬ T β S) : S β π i β¨ SαΆ β π i := by classical by_cases hS : S β π i Β· exact Or.inl hS by_cases hSc : SαΆ β π i Β· exact Or.inr hSc exfalso have hnself : S β SαΆ := by intro he let x : Fin n := β¨0, hnβ© have hx : x β S β x β S := by have hx' := congrArg (fun T : Finset (Fin n) => x β T) he simpa using hx' by_cases hs : x β S Β· exact (hx.mp hs) hs Β· exact hs (hx.mpr hs) let π' := Function.update π i (insert S (π i)) have hunc' : β j, is_uncomplemented (π' j) := by intro j by_cases hj : j = i Β· subst j simp only [π', Function.update_self] intro T hT hTc rcases mem_insert.mp hT with hTS | hT Β· subst T rcases mem_insert.mp hTc with hEq | hTc Β· exact hnself hEq.symm Β· exact hSc hTc Β· rcases mem_insert.mp hTc with hEq | hTc Β· have hTSc : T = SαΆ := by have hh := congrArg (fun R : Finset (Fin n) => RαΆ) hEq simpa using hh exact hSc (hTSc βΈ hT) Β· exact hunc i T hT hTc Β· simpa [π', Function.update_of_ne hj] using hunc j have hinc' : strongly_incomparable π' := by intro j k hjk U hU V hV hUV by_cases hj : j = i Β· subst j have hk : k β i := Ne.symm hjk have hU' : U β insert S (π i) := by simpa [π'] using hU have hV' : V β π k := by simpa [π', Function.update_of_ne hk] using hV rcases mem_insert.mp hU' with rfl | hU' Β· exact (hfree k hk V hV').1 hUV Β· exact hinc i k hjk U hU' V hV' hUV Β· by_cases hk : k = i Β· subst k have hU' : U β π j := by simpa [π', Function.update_of_ne hj] using hU have hV' : V β insert S (π i) := by simpa [π'] using hV rcases mem_insert.mp hV' with rfl | hV' Β· exact (hfree j hj U hU').2 hUV Β· exact hinc j i hjk U hU' V hV' hUV Β· have hU' : U β π j := by simpa [π', Function.update_of_ne hj] using hU have hV' : V β π k := by simpa [π', Function.update_of_ne hk] using hV exact hinc j k hjk U hU' V hV' hUV have hcard : β j, (π' j).card = (π j).card + if j = i then 1 else 0 := by intro j by_cases hj : j = i Β· subst j simp [π', hS] Β· simp [π', Function.update_of_ne hj, hj] have hsum : (β j, (π' j).card) = (β j, (π j).card) + 1 := by simp_rw [hcard] simp [Finset.sum_add_distrib] have hup := hupper π' hunc' hinc' have hbad : K + 1 β€ K := by simpa [hsum, heq] using hup exact Nat.not_succ_le_self K (by simpa [Nat.add_comm] using hbad)