op1370_maximal_free_regions_incomparable
theoremverified
For a system reaching a valid total-size upper bound, the full compatibility regions of distinct colors are mutually strongly incomparable.
Statement
theorem op1370_maximal_free_regions_incomparable
(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 j : Fin t) (hij : i β j) (S T : Finset (Fin n))
(hS : β k, k β i β β U β π k, Β¬ S β U β§ Β¬ U β S)
(hT : β k, k β j β β U β π k, Β¬ T β U β§ Β¬ U β T) : Β¬ S β T- Source
- Filed by the prover as a step towards another result
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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β¦ - op1370_maximal_free_region_saturationIn a system reaching any valid total-size upper bound, a set incomparable to all other colors belongs to its color either directly orβ¦
Lean source view module on GitHub
open Finset theorem op1370_maximal_free_regions_incomparable (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 j : Fin t) (hij : i β j) (S T : Finset (Fin n)) (hS : β k, k β i β β U β π k, Β¬ S β U β§ Β¬ U β S) (hT : β k, k β j β β U β π k, Β¬ T β U β§ Β¬ U β T) : Β¬ S β T := by intro hST have hns : S β π i := by intro hs exact (hT i hij S hs).2 hST have hnt : T β π j := by intro ht exact (hS j hij.symm T ht).1 hST have hs' : SαΆ β π i := (op1370_maximal_free_region_saturation n t hn π hunc hinc K hupper heq i S hS).resolve_left hns have ht' : TαΆ β π j := (op1370_maximal_free_region_saturation n t hn π hunc hinc K hupper heq j T hT).resolve_left hnt exact hinc j i hij.symm TαΆ ht' SαΆ hs' (Finset.compl_subset_compl.mpr hST)