AFTD Auto-Formalizing Theoretical Domains

op1370_coordinate_patterns_bound

theoremverified

If an uncomplemented family has the opposite membership of x at every coordinate in Y, where x is outside Y, then its size is at most 2^(n-(|Y|+1)).

Statement

lemma op1370_coordinate_patterns_bound (n : ℕ) (F : Finset (Finset (Fin n)))
    (hu : is_uncomplemented F) (x : Fin n) (Y : Finset (Fin n)) (hxY : x ∉ Y)
    (hpattern : ∀ S ∈ F, ∀ y ∈ Y, (x ∈ S ↔ y ∉ S)) :
    F.card ≤ 2 ^ (n - (Y.card + 1))
Source
Coordinate-pattern counting lemma for OP-1370.
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • is_uncomplementedA family of subsets of a finite set is uncomplemented if no set and its complement both belong to the family.
Used by 1

Lean source view module on GitHub

lemma op1370_coordinate_patterns_bound (n : ℕ) (F : Finset (Finset (Fin n)))
    (hu : is_uncomplemented F) (x : Fin n) (Y : Finset (Fin n)) (hxY : x ∉ Y)
    (hpattern : ∀ S ∈ F, ∀ y ∈ Y, (x ∈ S ↔ y ∉ S)) :
    F.card ≤ 2 ^ (n - (Y.card + 1)) := by
  open Finset in
  classical
  let V : Finset (Fin n) := univ \ insert x Y
  let f : Finset (Fin n) → Finset (Fin n) := fun S => (if x ∈ S then S else Sᶜ).erase x
  have hmap : Set.MapsTo f F V.powerset := by
    intro S hS
    apply mem_powerset.mpr
    intro a ha
    by_cases hxS : x ∈ S
    · simp only [f, hxS, ↓reduceIte, mem_erase] at ha
      simp only [V, mem_sdiff, mem_univ, mem_insert, true_and, not_or]
      refine ⟨ha.1, ?_⟩
      intro haY
      exact (hpattern S hS a haY).mp hxS ha.2
    · simp only [f, hxS, ↓reduceIte, mem_erase, mem_compl] at ha
      simp only [V, mem_sdiff, mem_univ, mem_insert, true_and, not_or]
      refine ⟨ha.1, ?_⟩
      intro haY
      have haS : a ∈ S := by
        by_contra haS
        exact hxS ((hpattern S hS a haY).mpr haS)
      exact ha.2 haS
  have hinj : (F : Set (Finset (Fin n))).InjOn f := by
    intro S hS T hT hST
    by_cases hxS : x ∈ S <;> by_cases hxT : x ∈ T
    · have he : S.erase x = T.erase x := by simpa [f, hxS, hxT] using hST
      calc S = insert x (S.erase x) := (insert_erase hxS).symm
           _ = insert x (T.erase x) := by rw [he]
           _ = T := insert_erase hxT
    · have he : S.erase x = Tᶜ.erase x := by simpa [f, hxS, hxT] using hST
      have hxTc : x ∈ Tᶜ := mem_compl.mpr hxT
      have hEq : S = Tᶜ := by
        calc S = insert x (S.erase x) := (insert_erase hxS).symm
             _ = insert x (Tᶜ.erase x) := by rw [he]
             _ = Tᶜ := insert_erase hxTc
      exact False.elim ((hu T hT) (hEq ▸ hS))
    · have he : Sᶜ.erase x = T.erase x := by simpa [f, hxS, hxT] using hST
      have hxSc : x ∈ Sᶜ := mem_compl.mpr hxS
      have hEq : Sᶜ = T := by
        calc Sᶜ = insert x (Sᶜ.erase x) := (insert_erase hxSc).symm
             _ = insert x (T.erase x) := by rw [he]
             _ = T := insert_erase hxT
      exact False.elim ((hu S hS) (hEq.symm ▸ hT))
    · have he : Sᶜ.erase x = Tᶜ.erase x := by simpa [f, hxS, hxT] using hST
      have hxSc : x ∈ Sᶜ := mem_compl.mpr hxS
      have hxTc : x ∈ Tᶜ := mem_compl.mpr hxT
      have hc : Sᶜ = Tᶜ := by
        calc Sᶜ = insert x (Sᶜ.erase x) := (insert_erase hxSc).symm
             _ = insert x (Tᶜ.erase x) := by rw [he]
             _ = Tᶜ := insert_erase hxTc
      simpa using congrArg (fun a : Finset (Fin n) => aᶜ) hc
  have hVcard : V.card = n - (Y.card + 1) := by
    dsimp [V]
    rw [card_sdiff_of_subset (subset_univ _), card_univ, Fintype.card_fin,
      card_insert_of_notMem hxY]
  have hc := card_le_card_of_injOn f hmap hinj
  simpa [card_powerset, hVcard] using hc
See it in the graphDiscuss this resultChallenge it