AFTD Auto-Formalizing Theoretical Domains

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 all i j : ΞΉ with i β‰  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)
See it in the graphDiscuss this resultChallenge it