AFTD Auto-Formalizing Theoretical Domains

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 all i j : ΞΉ with i β‰  j, for all…
Used by 1

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)
See it in the graphDiscuss this resultChallenge it