AFTD Auto-Formalizing Theoretical Domains

op1370_cyclic_two_set_blocker_bound

theoremverifiedoriginal

Let n be at least four, and let three families of subsets of Fin n be mutually strongly incomparable. Choose four distinct coordinates x, a, b, c. Suppose the first family contains {x,a} and the complement of {x,c}, the second contains {x,b} and the complement of {x,a}, and the third contains {x,c} and the complement of {x,b}. Then the total number of sets is at most 3 times 2^(n-3). No uncomplementedness is assumed.

Statement

theorem op1370_cyclic_two_set_blocker_bound (n : ℕ) (hn : 4 ≤ n) (𝒜 : Fin 3 → Finset (Finset (Fin n))) (hinc : strongly_incomparable 𝒜) (x a b c : Fin n) (hxa : x ≠ a) (hxb : x ≠ b) (hxc : x ≠ c) (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) (h0 : ({x,a} : Finset (Fin n)) ∈ 𝒜 0 ∧ ({x,c} : Finset (Fin n))ᶜ ∈ 𝒜 0) (h1 : ({x,b} : Finset (Fin n)) ∈ 𝒜 1 ∧ ({x,a} : Finset (Fin n))ᶜ ∈ 𝒜 1) (h2 : ({x,c} : Finset (Fin n)) ∈ 𝒜 2 ∧ ({x,b} : Finset (Fin n))ᶜ ∈ 𝒜 2) : ∑ i, (𝒜 i).card ≤ 3 * 2 ^ (n - 3)
Related work
A cyclic complementary-pair case of Conjecture 4.3 in arXiv:2611.12199; no uncomplementedness is assumed.
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • strongly_incomparableAn indexed family of finset families 𝒜 : ι → Finset (Finset α) is strongly incomparable if for all i j : ι with i ≠ j, for all…
  • FThe prime field $\mathrm{GF}(p)$, realized as $\mathbb{Z}/p\mathbb{Z}$ via ZMod.

Read back from the Lean

For any natural number $n \ge 4$, let $\mathcal{A} = (\mathcal{A}_0, \mathcal{A}_1, \mathcal{A}_2)$ be a 3-tuple of families (finsets) of subsets of $\mathrm{Fin}(n)$. Assume that $\mathcal{A}$ is strongly incomparable, meaning that for all $i, j \in \{0, 1, 2\}$ with $i \ne j$, no set $A \in \mathcal{A}_i$ is a subset of any set $B \in \mathcal{A}_j$. Let $x, a, b, c \in \mathrm{Fin}(n)$ be four pairwise distinct elements ($x \ne a$, $x \ne b$, $x \ne c$, $a \ne b$, $a \ne c$, and $b \ne c$). Suppose further that: - $\{x, a\} \in \mathcal{A}_0$ and $\{x, c\}^c \in \mathcal{A}_0$, - $\{x, b\} \in \mathcal{A}_1$ and $\{x, a\}^c \in \mathcal{A}_1$, - $\{x, c\} \in \mathcal{A}_2$ and $\{x, b\}^c \in \mathcal{A}_2$, where complements are taken with respect to the universe $\mathrm{Fin}(n)$. Then the total number of sets across the three families satisfies $$\sum_{i \in \mathrm{Fin}(3)} |\mathcal{A}_i| \le 3 \cdot 2^{n - 3}.$$

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

set_option maxHeartbeats 4000000

private lemma op1370_cyclic_two_set_blocker_bound_trace0 (n : ℕ) (𝒜 : Fin 3 → Finset (Finset (Fin n))) (hinc : strongly_incomparable 𝒜)
  (x a b c : Fin n) (hxa : x ≠ a) (hxb : x ≠ b) (hxc : x ≠ c) (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c)
  (h1 : ({x,b} : Finset (Fin n)) ∈ 𝒜 1 ∧ ({x,a} : Finset (Fin n))ᶜ ∈ 𝒜 1)
  (h2 : ({x,c} : Finset (Fin n)) ∈ 𝒜 2 ∧ ({x,b} : Finset (Fin n))ᶜ ∈ 𝒜 2)
  (A : Finset (Fin n)) (hA : A ∈ 𝒜 0) :
  A ∩ ({x,a,b,c} : Finset (Fin n)) ∈ ({{x,a},{a,b},{a,b,c},{x}} : Finset (Finset (Fin n))) := by
  classical
  have hU1 : ¬ (({x,b} : Finset (Fin n)) ⊆ A ∩ {x,a,b,c}) := fun hsub =>
    hinc 1 0 (by decide) {x,b} h1.1 A hA (hsub.trans Finset.inter_subset_left)
  have hU2 : ¬ (({x,c} : Finset (Fin n)) ⊆ A ∩ {x,a,b,c}) := fun hsub =>
    hinc 2 0 (by decide) {x,c} h2.1 A hA (hsub.trans Finset.inter_subset_left)
  have hU3 : ¬ (A ∩ {x,a,b,c} ⊆ ({b,c} : Finset (Fin n))) := by
    intro hsub
    have hAc : A ⊆ ({x,a} : Finset (Fin n))ᶜ := by
      intro y hy
      rw [Finset.mem_compl]
      intro hyxa
      have hyC : y ∈ ({x,a,b,c} : Finset (Fin n)) := by
        simp only [Finset.mem_insert, Finset.mem_singleton] at hyxa ⊢
        tauto
      have hy' : y ∈ A ∩ {x,a,b,c} := Finset.mem_inter.mpr ⟨hy, hyC⟩
      have hybc : y ∈ ({b,c} : Finset (Fin n)) := hsub hy'
      simp only [Finset.mem_insert, Finset.mem_singleton] at hyxa hybc
      rcases hyxa with h1 | h1 <;> rcases hybc with h2 | h2
      · exact hxb (h1.symm.trans h2)
      · exact hxc (h1.symm.trans h2)
      · exact hab (h1.symm.trans h2)
      · exact hac (h1.symm.trans h2)
    exact hinc 0 1 (by decide) A hA ({x,a}ᶜ) h1.2 hAc
  have hU4 : ¬ (A ∩ {x,a,b,c} ⊆ ({a,c} : Finset (Fin n))) := by
    intro hsub
    have hAc : A ⊆ ({x,b} : Finset (Fin n))ᶜ := by
      intro y hy
      rw [Finset.mem_compl]
      intro hyxb
      have hyC : y ∈ ({x,a,b,c} : Finset (Fin n)) := by
        simp only [Finset.mem_insert, Finset.mem_singleton] at hyxb ⊢
        tauto
      have hy' : y ∈ A ∩ {x,a,b,c} := Finset.mem_inter.mpr ⟨hy, hyC⟩
      have hyac : y ∈ ({a,c} : Finset (Fin n)) := hsub hy'
      simp only [Finset.mem_insert, Finset.mem_singleton] at hyxb hyac
      rcases hyxb with h1 | h1 <;> rcases hyac with h2 | h2
      · exact hxa (h1.symm.trans h2)
      · exact hxc (h1.symm.trans h2)
      · exact hab (h2.symm.trans h1)
      · exact hbc (h1.symm.trans h2)
    exact hinc 0 2 (by decide) A hA ({x,b}ᶜ) h2.2 hAc
  have hTsub : A ∩ {x,a,b,c} ⊆ ({x,a,b,c} : Finset (Fin n)) := Finset.inter_subset_right
  have key : (A ∩ {x,a,b,c} = {x,a}) ∨ (A ∩ {x,a,b,c} = {a,b}) ∨ (A ∩ {x,a,b,c} = {a,b,c}) ∨ (A ∩ {x,a,b,c} = {x}) := by
    by_cases hx : x ∈ A ∩ {x,a,b,c}
    · have hbt : b ∉ A ∩ {x,a,b,c} := by
        intro hb
        exact hU1 (by
          intro y hy
          simp only [Finset.mem_insert, Finset.mem_singleton] at hy ⊢
          rcases hy with rfl | rfl
          · exact hx
          · exact hb)
      have hct : c ∉ A ∩ {x,a,b,c} := by
        intro hc
        exact hU2 (by
          intro y hy
          simp only [Finset.mem_insert, Finset.mem_singleton] at hy ⊢
          rcases hy with rfl | rfl
          · exact hx
          · exact hc)
      have hTsub2 : A ∩ {x,a,b,c} ⊆ ({x,a} : Finset (Fin n)) := by
        intro y hy
        have hyC := hTsub hy
        simp only [Finset.mem_insert, Finset.mem_singleton] at hyC ⊢
        rcases hyC with h | h | h | h
        · left; exact h
        · right; exact h
        · exact absurd (h ▸ hy) hbt
        · exact absurd (h ▸ hy) hct
      by_cases ha : a ∈ A ∩ {x,a,b,c}
      · left
        refine Finset.Subset.antisymm hTsub2 ?_
        intro y hy
        simp only [Finset.mem_insert, Finset.mem_singleton] at hy
        rcases hy with h | h
        · rw [h]; exact hx
        · rw [h]; exact ha
      · right; right; right
        refine Finset.Subset.antisymm ?_ ?_
        · intro y hy
          have h2 := hTsub2 hy
          simp only [Finset.mem_insert, Finset.mem_singleton] at h2 ⊢
          rcases h2 with h | h
          · exact h
          · exact absurd (h ▸ hy) ha
        · intro y hy
          simp only [Finset.mem_singleton] at hy
          rw [hy]; exact hx
    · have haT : a ∈ A ∩ {x,a,b,c} := by
        by_contra haT
        apply hU3
        intro y hy
        have hyC := hTsub hy
        simp only [Finset.mem_insert, Finset.mem_singleton] at hyC ⊢
        rcases hyC with h | h | h | h
        · exact absurd (h ▸ hy) hx
        · exact absurd (h ▸ hy) haT
        · left; exact h
        · right; exact h
      have hbT : b ∈ A ∩ {x,a,b,c} := by
        by_contra hbT
        apply hU4
        intro y hy
        have hyC := hTsub hy
        simp only [Finset.mem_insert, Finset.mem_singleton] at hyC ⊢
        rcases hyC with h | h | h | h
        · exact absurd (h ▸ hy) hx
        · left; exact h
        · exact absurd (h ▸ hy) hbT
        · right; exact h
      have hTsub3 : A ∩ {x,a,b,c} ⊆ ({a,b,c} : Finset (Fin n)) := by
        intro y hy
        have hyC := hTsub hy
        simp only [Finset.mem_insert, Finset.mem_singleton] at hyC ⊢
        rcases hyC with h | h | h | h
        · exact absurd (h ▸ hy) hx
        · left; exact h
        · right; left; exact h
        · right; right; exact h
      by_cases hcT : c ∈ A ∩ {x,a,b,c}
      · right; right; left
        refine Finset.Subset.antisymm hTsub3 ?_
        intro y hy
        simp only [Finset.mem_insert, Finset.mem_singleton] at hy ⊢
        rcases hy with h | h | h
        · rw [h]; exact haT
        · rw [h]; exact hbT
        · rw [h]; exact hcT
      · right; left
        refine Finset.Subset.antisymm ?_ ?_
        · intro y hy
          have h2 := hTsub3 hy
          simp only [Finset.mem_insert, Finset.mem_singleton] at h2 ⊢
          rcases h2 with h | h | h
          · left; exact h
          · right; exact h
          · exact absurd (h ▸ hy) hcT
        · intro y hy
          simp only [Finset.mem_insert, Finset.mem_singleton] at hy ⊢
          rcases hy with h | h
          · rw [h]; exact haT
          · rw [h]; exact hbT
  rcases key with h | h | h | h <;> rw [h] <;> simp

private lemma op1370_cyclic_two_set_blocker_bound_trace1 (n : ℕ) (𝒜 : Fin 3 → Finset (Finset (Fin n))) (hinc : strongly_incomparable 𝒜)
  (x a b c : Fin n) (hxa : x ≠ a) (hxb : x ≠ b) (hxc : x ≠ c) (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c)
  (h0 : ({x,a} : Finset (Fin n)) ∈ 𝒜 0 ∧ ({x,c} : Finset (Fin n))ᶜ ∈ 𝒜 0)
  (h2 : ({x,c} : Finset (Fin n)) ∈ 𝒜 2 ∧ ({x,b} : Finset (Fin n))ᶜ ∈ 𝒜 2)
  (A : Finset (Fin n)) (hA : A ∈ 𝒜 1) :
  A ∩ ({x,a,b,c} : Finset (Fin n)) ∈ ({{x,b},{b,c},{a,b,c},{x}} : Finset (Finset (Fin n))) := by
  classical
  have hU1 : ¬ (({x,a} : Finset (Fin n)) ⊆ A ∩ {x,a,b,c}) := fun hsub =>
    hinc 0 1 (by decide) {x,a} h0.1 A hA (hsub.trans Finset.inter_subset_left)
  have hU2 : ¬ (({x,c} : Finset (Fin n)) ⊆ A ∩ {x,a,b,c}) := fun hsub =>
    hinc 2 1 (by decide) {x,c} h2.1 A hA (hsub.trans Finset.inter_subset_left)
  have hU3 : ¬ (A ∩ {x,a,b,c} ⊆ ({a,b} : Finset (Fin n))) := by
    intro hsub
    have hAc : A ⊆ ({x,c} : Finset (Fin n))ᶜ := by
      intro y hy
      rw [Finset.mem_compl]
      intro hyxc
      have hyC : y ∈ ({x,a,b,c} : Finset (Fin n)) := by
        simp only [Finset.mem_insert, Finset.mem_singleton] at hyxc ⊢
        tauto
      have hy' : y ∈ A ∩ {x,a,b,c} := Finset.mem_inter.mpr ⟨hy, hyC⟩
      have hyab : y ∈ ({a,b} : Finset (Fin n)) := hsub hy'
      simp only [Finset.mem_insert, Finset.mem_singleton] at hyxc hyab
      rcases hyxc with h1 | h1 <;> rcases hyab with h2 | h2
      · exact hxa (h1.symm.trans h2)
      · exact hxb (h1.symm.trans h2)
      · exact hac (h2.symm.trans h1)
      · exact hbc (h2.symm.trans h1)
    exact hinc 1 0 (by decide) A hA ({x,c}ᶜ) h0.2 hAc
  have hU4 : ¬ (A ∩ {x,a,b,c} ⊆ ({a,c} : Finset (Fin n))) := by
    intro hsub
    have hAc : A ⊆ ({x,b} : Finset (Fin n))ᶜ := by
      intro y hy
      rw [Finset.mem_compl]
      intro hyxb
      have hyC : y ∈ ({x,a,b,c} : Finset (Fin n)) := by
        simp only [Finset.mem_insert, Finset.mem_singleton] at hyxb ⊢
        tauto
      have hy' : y ∈ A ∩ {x,a,b,c} := Finset.mem_inter.mpr ⟨hy, hyC⟩
      have hyac : y ∈ ({a,c} : Finset (Fin n)) := hsub hy'
      simp only [Finset.mem_insert, Finset.mem_singleton] at hyxb hyac
      rcases hyxb with h1 | h1 <;> rcases hyac with h2 | h2
      · exact hxa (h1.symm.trans h2)
      · exact hxc (h1.symm.trans h2)
      · exact hab (h2.symm.trans h1)
      · exact hbc (h1.symm.trans h2)
    exact hinc 1 2 (by decide) A hA ({x,b}ᶜ) h2.2 hAc
  have hTsub : A ∩ {x,a,b,c} ⊆ ({x,a,b,c} : Finset (Fin n)) := Finset.inter_subset_right
  have key : (A ∩ {x,a,b,c} = {x,b}) ∨ (A ∩ {x,a,b,c} = {b,c}) ∨ (A ∩ {x,a,b,c} = {a,b,c}) ∨ (A ∩ {x,a,b,c} = {x}) := by
    by_cases hx : x ∈ A ∩ {x,a,b,c}
    · have hat : a ∉ A ∩ {x,a,b,c} := by
        intro ha
        exact hU1 (by
          intro y hy
          simp only [Finset.mem_insert, Finset.mem_singleton] at hy ⊢
          rcases hy with rfl | rfl
          · exact hx
          · exact ha)
      have hct : c ∉ A ∩ {x,a,b,c} := by
        intro hc
        exact hU2 (by
          intro y hy
          simp only [Finset.mem_insert, Finset.mem_singleton] at hy ⊢
          rcases hy with rfl | rfl
          · exact hx
          · exact hc)
      have hTsub2 : A ∩ {x,a,b,c} ⊆ ({x,b} : Finset (Fin n)) := by
        intro y hy
        have hyC := hTsub hy
        simp only [Finset.mem_insert, Finset.mem_singleton] at hyC ⊢
        rcases hyC with h | h | h | h
        · left; exact h
        · exact absurd (h ▸ hy) hat
        · right; exact h
        · exact absurd (h ▸ hy) hct
      by_cases hb : b ∈ A ∩ {x,a,b,c}
      · left
        refine Finset.Subset.antisymm hTsub2 ?_
        intro y hy
        simp only [Finset.mem_insert, Finset.mem_singleton] at hy
        rcases hy with h | h
        · rw [h]; exact hx
        · rw [h]; exact hb
      · right; right; right
        refine Finset.Subset.antisymm ?_ ?_
        · intro y hy
          have h2 := hTsub2 hy
          simp only [Finset.mem_insert, Finset.mem_singleton] at h2 ⊢
          rcases h2 with h | h
          · exact h
          · exact absurd (h ▸ hy) hb
        · intro y hy
          simp only [Finset.mem_singleton] at hy
          rw [hy]; exact hx
    · have hcT : c ∈ A ∩ {x,a,b,c} := by
        by_contra hcT
        apply hU3
        intro y hy
        have hyC := hTsub hy
        simp only [Finset.mem_insert, Finset.mem_singleton] at hyC ⊢
        rcases hyC with h | h | h | h
        · exact absurd (h ▸ hy) hx
        · left; exact h
        · right; exact h
        · exact absurd (h ▸ hy) hcT
      have hbT : b ∈ A ∩ {x,a,b,c} := by
        by_contra hbT
        apply hU4
        intro y hy
        have hyC := hTsub hy
        simp only [Finset.mem_insert, Finset.mem_singleton] at hyC ⊢
        rcases hyC with h | h | h | h
        · exact absurd (h ▸ hy) hx
        · left; exact h
        · exact absurd (h ▸ hy) hbT
        · right; exact h
      have hTsub3 : A ∩ {x,a,b,c} ⊆ ({a,b,c} : Finset (Fin n)) := by
        intro y hy
        have hyC := hTsub hy
        simp only [Finset.mem_insert, Finset.mem_singleton] at hyC ⊢
        rcases hyC with h | h | h | h
        · exact absurd (h ▸ hy) hx
        · left; exact h
        · right; left; exact h
        · right; right; exact h
      by_cases haT : a ∈ A ∩ {x,a,b,c}
      · right; right; left
        refine Finset.Subset.antisymm hTsub3 ?_
        intro y hy
        simp only [Finset.mem_insert, Finset.mem_singleton] at hy ⊢
        rcases hy with h | h | h
        · rw [h]; exact haT
        · rw [h]; exact hbT
        · rw [h]; exact hcT
      · right; left
        refine Finset.Subset.antisymm ?_ ?_
        · intro y hy
          have h2 := hTsub3 hy
          simp only [Finset.mem_insert, Finset.mem_singleton] at h2 ⊢
          rcases h2 with h | h | h
          · exact absurd (h ▸ hy) haT
          · left; exact h
          · right; exact h
        · intro y hy
          simp only [Finset.mem_insert, Finset.mem_singleton] at hy ⊢
          rcases hy with h | h
          · rw [h]; exact hbT
          · rw [h]; exact hcT
  rcases key with h | h | h | h <;> rw [h] <;> simp

private lemma op1370_cyclic_two_set_blocker_bound_trace2 (n : ℕ) (𝒜 : Fin 3 → Finset (Finset (Fin n))) (hinc : strongly_incomparable 𝒜)
  (x a b c : Fin n) (hxa : x ≠ a) (hxb : x ≠ b) (hxc : x ≠ c) (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c)
  (h0 : ({x,a} : Finset (Fin n)) ∈ 𝒜 0 ∧ ({x,c} : Finset (Fin n))ᶜ ∈ 𝒜 0)
  (h1 : ({x,b} : Finset (Fin n)) ∈ 𝒜 1 ∧ ({x,a} : Finset (Fin n))ᶜ ∈ 𝒜 1)
  (A : Finset (Fin n)) (hA : A ∈ 𝒜 2) :
  A ∩ ({x,a,b,c} : Finset (Fin n)) ∈ ({{x,c},{a,c},{a,b,c},{x}} : Finset (Finset (Fin n))) := by
  classical
  have hU1 : ¬ (({x,a} : Finset (Fin n)) ⊆ A ∩ {x,a,b,c}) := fun hsub =>
    hinc 0 2 (by decide) {x,a} h0.1 A hA (hsub.trans Finset.inter_subset_left)
  have hU2 : ¬ (({x,b} : Finset (Fin n)) ⊆ A ∩ {x,a,b,c}) := fun hsub =>
    hinc 1 2 (by decide) {x,b} h1.1 A hA (hsub.trans Finset.inter_subset_left)
  have hU3 : ¬ (A ∩ {x,a,b,c} ⊆ ({a,b} : Finset (Fin n))) := by
    intro hsub
    have hAc : A ⊆ ({x,c} : Finset (Fin n))ᶜ := by
      intro y hy
      rw [Finset.mem_compl]
      intro hyxc
      have hyC : y ∈ ({x,a,b,c} : Finset (Fin n)) := by
        simp only [Finset.mem_insert, Finset.mem_singleton] at hyxc ⊢
        tauto
      have hy' : y ∈ A ∩ {x,a,b,c} := Finset.mem_inter.mpr ⟨hy, hyC⟩
      have hyab : y ∈ ({a,b} : Finset (Fin n)) := hsub hy'
      simp only [Finset.mem_insert, Finset.mem_singleton] at hyxc hyab
      rcases hyxc with h1 | h1 <;> rcases hyab with h2 | h2
      · exact hxa (h1.symm.trans h2)
      · exact hxb (h1.symm.trans h2)
      · exact hac (h2.symm.trans h1)
      · exact hbc (h2.symm.trans h1)
    exact hinc 2 0 (by decide) A hA ({x,c}ᶜ) h0.2 hAc
  have hU4 : ¬ (A ∩ {x,a,b,c} ⊆ ({b,c} : Finset (Fin n))) := by
    intro hsub
    have hAc : A ⊆ ({x,a} : Finset (Fin n))ᶜ := by
      intro y hy
      rw [Finset.mem_compl]
      intro hyxa
      have hyC : y ∈ ({x,a,b,c} : Finset (Fin n)) := by
        simp only [Finset.mem_insert, Finset.mem_singleton] at hyxa ⊢
        tauto
      have hy' : y ∈ A ∩ {x,a,b,c} := Finset.mem_inter.mpr ⟨hy, hyC⟩
      have hybc : y ∈ ({b,c} : Finset (Fin n)) := hsub hy'
      simp only [Finset.mem_insert, Finset.mem_singleton] at hyxa hybc
      rcases hyxa with h1 | h1 <;> rcases hybc with h2 | h2
      · exact hxb (h1.symm.trans h2)
      · exact hxc (h1.symm.trans h2)
      · exact hab (h1.symm.trans h2)
      · exact hac (h1.symm.trans h2)
    exact hinc 2 1 (by decide) A hA ({x,a}ᶜ) h1.2 hAc
  have hTsub : A ∩ {x,a,b,c} ⊆ ({x,a,b,c} : Finset (Fin n)) := Finset.inter_subset_right
  have key : (A ∩ {x,a,b,c} = {x,c}) ∨ (A ∩ {x,a,b,c} = {a,c}) ∨ (A ∩ {x,a,b,c} = {a,b,c}) ∨ (A ∩ {x,a,b,c} = {x}) := by
    by_cases hx : x ∈ A ∩ {x,a,b,c}
    · have hat : a ∉ A ∩ {x,a,b,c} := by
        intro ha
        exact hU1 (by
          intro y hy
          simp only [Finset.mem_insert, Finset.mem_singleton] at hy ⊢
          rcases hy with rfl | rfl
          · exact hx
          · exact ha)
      have hbt : b ∉ A ∩ {x,a,b,c} := by
        intro hb
        exact hU2 (by
          intro y hy
          simp only [Finset.mem_insert, Finset.mem_singleton] at hy ⊢
          rcases hy with rfl | rfl
          · exact hx
          · exact hb)
      have hTsub2 : A ∩ {x,a,b,c} ⊆ ({x,c} : Finset (Fin n)) := by
        intro y hy
        have hyC := hTsub hy
        simp only [Finset.mem_insert, Finset.mem_singleton] at hyC ⊢
        rcases hyC with h | h | h | h
        · left; exact h
        · exact absurd (h ▸ hy) hat
        · exact absurd (h ▸ hy) hbt
        · right; exact h
      by_cases hc : c ∈ A ∩ {x,a,b,c}
      · left
        refine Finset.Subset.antisymm hTsub2 ?_
        intro y hy
        simp only [Finset.mem_insert, Finset.mem_singleton] at hy
        rcases hy with h | h
        · rw [h]; exact hx
        · rw [h]; exact hc
      · right; right; right
        refine Finset.Subset.antisymm ?_ ?_
        · intro y hy
          have h2 := hTsub2 hy
          simp only [Finset.mem_insert, Finset.mem_singleton] at h2 ⊢
          rcases h2 with h | h
          · exact h
          · exact absurd (h ▸ hy) hc
        · intro y hy
          simp only [Finset.mem_singleton] at hy
          rw [hy]; exact hx
    · have hcT : c ∈ A ∩ {x,a,b,c} := by
        by_contra hcT
        apply hU3
        intro y hy
        have hyC := hTsub hy
        simp only [Finset.mem_insert, Finset.mem_singleton] at hyC ⊢
        rcases hyC with h | h | h | h
        · exact absurd (h ▸ hy) hx
        · left; exact h
        · right; exact h
        · exact absurd (h ▸ hy) hcT
      have haT : a ∈ A ∩ {x,a,b,c} := by
        by_contra haT
        apply hU4
        intro y hy
        have hyC := hTsub hy
        simp only [Finset.mem_insert, Finset.mem_singleton] at hyC ⊢
        rcases hyC with h | h | h | h
        · exact absurd (h ▸ hy) hx
        · exact absurd (h ▸ hy) haT
        · left; exact h
        · right; exact h
      have hTsub3 : A ∩ {x,a,b,c} ⊆ ({a,b,c} : Finset (Fin n)) := by
        intro y hy
        have hyC := hTsub hy
        simp only [Finset.mem_insert, Finset.mem_singleton] at hyC ⊢
        rcases hyC with h | h | h | h
        · exact absurd (h ▸ hy) hx
        · left; exact h
        · right; left; exact h
        · right; right; exact h
      by_cases hbT : b ∈ A ∩ {x,a,b,c}
      · right; right; left
        refine Finset.Subset.antisymm hTsub3 ?_
        intro y hy
        simp only [Finset.mem_insert, Finset.mem_singleton] at hy ⊢
        rcases hy with h | h | h
        · rw [h]; exact haT
        · rw [h]; exact hbT
        · rw [h]; exact hcT
      · right; left
        refine Finset.Subset.antisymm ?_ ?_
        · intro y hy
          have h2 := hTsub3 hy
          simp only [Finset.mem_insert, Finset.mem_singleton] at h2 ⊢
          rcases h2 with h | h | h
          · left; exact h
          · exact absurd (h ▸ hy) hbT
          · right; exact h
        · intro y hy
          simp only [Finset.mem_insert, Finset.mem_singleton] at hy ⊢
          rcases hy with h | h
          · rw [h]; exact haT
          · rw [h]; exact hcT
  rcases key with h | h | h | h <;> rw [h] <;> simp

private lemma op1370_cyclic_two_set_blocker_bound_nxbG0 (n : ℕ) (x a b c : Fin n) (hxa : x ≠ a) (hxb : x ≠ b) (hxc : x ≠ c)
    (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) :
    ({x,b}:Finset (Fin n)) ∉ ({{x,a},{a,b},{a,b,c},{x}}:Finset (Finset (Fin n))) := by
  simp only [Finset.mem_insert, Finset.mem_singleton]
  rintro (h|h|h|h)
  · have hm : b ∈ ({x,a}:Finset (Fin n)) := by
      have ht : b ∈ ({x,b}:Finset (Fin n)) := by simp
      rwa [h] at ht
    simp only [Finset.mem_insert, Finset.mem_singleton] at hm
    rcases hm with h'|h' <;> first | exact hxb h' | exact hxb h'.symm | exact hab h' | exact hab h'.symm
  · have hm : x ∈ ({a,b}:Finset (Fin n)) := by
      have ht : x ∈ ({x,b}:Finset (Fin n)) := by simp
      rwa [h] at ht
    simp only [Finset.mem_insert, Finset.mem_singleton] at hm
    rcases hm with h'|h' <;> first | exact hxa h' | exact hxa h'.symm | exact hxb h' | exact hxb h'.symm
  · have hm : x ∈ ({a,b,c}:Finset (Fin n)) := by
      have ht : x ∈ ({x,b}:Finset (Fin n)) := by simp
      rwa [h] at ht
    simp only [Finset.mem_insert, Finset.mem_singleton] at hm
    rcases hm with h'|h'|h' <;> first | exact hxa h' | exact hxa h'.symm | exact hxb h' | exact hxb h'.symm | exact hxc h' | exact hxc h'.symm
  · have hm : b ∈ ({x}:Finset (Fin n)) := by
      have ht : b ∈ ({x,b}:Finset (Fin n)) := by simp
      rwa [h] at ht
    simp only [Finset.mem_singleton] at hm
    first | exact hxb hm | exact hxb hm.symm

private lemma op1370_cyclic_two_set_blocker_bound_nxaG1 (n : ℕ) (x a b c : Fin n) (hxa : x ≠ a) (hxb : x ≠ b) (hxc : x ≠ c)
    (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) :
    ({x,a}:Finset (Fin n)) ∉ ({{x,b},{b,c},{a,b,c},{x}}:Finset (Finset (Fin n))) := by
  simp only [Finset.mem_insert, Finset.mem_singleton]
  rintro (h|h|h|h)
  · have hm : a ∈ ({x,b}:Finset (Fin n)) := by
      have ht : a ∈ ({x,a}:Finset (Fin n)) := by simp
      rwa [h] at ht
    simp only [Finset.mem_insert, Finset.mem_singleton] at hm
    rcases hm with h'|h' <;> first | exact hxa h'.symm | exact hxa h' | exact hab h'.symm | exact hab h'
  · have hm : x ∈ ({b,c}:Finset (Fin n)) := by
      have ht : x ∈ ({x,a}:Finset (Fin n)) := by simp
      rwa [h] at ht
    simp only [Finset.mem_insert, Finset.mem_singleton] at hm
    rcases hm with h'|h' <;> first | exact hxb h' | exact hxb h'.symm | exact hxc h' | exact hxc h'.symm
  · have hm : x ∈ ({a,b,c}:Finset (Fin n)) := by
      have ht : x ∈ ({x,a}:Finset (Fin n)) := by simp
      rwa [h] at ht
    simp only [Finset.mem_insert, Finset.mem_singleton] at hm
    rcases hm with h'|h'|h' <;> first | exact hxa h' | exact hxa h'.symm | exact hxb h' | exact hxb h'.symm | exact hxc h' | exact hxc h'.symm
  · have hm : a ∈ ({x}:Finset (Fin n)) := by
      have ht : a ∈ ({x,a}:Finset (Fin n)) := by simp
      rwa [h] at ht
    simp only [Finset.mem_singleton] at hm
    first | exact hxa hm | exact hxa hm.symm

private lemma op1370_cyclic_two_set_blocker_bound_nxaG2 (n : ℕ) (x a b c : Fin n) (hxa : x ≠ a) (hxb : x ≠ b) (hxc : x ≠ c)
    (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) :
    ({x,a}:Finset (Fin n)) ∉ ({{x,c},{a,c},{a,b,c},{x}}:Finset (Finset (Fin n))) := by
  simp only [Finset.mem_insert, Finset.mem_singleton]
  rintro (h|h|h|h)
  · have hm : a ∈ ({x,c}:Finset (Fin n)) := by
      have ht : a ∈ ({x,a}:Finset (Fin n)) := by simp
      rwa [h] at ht
    simp only [Finset.mem_insert, Finset.mem_singleton] at hm
    rcases hm with h'|h' <;> first | exact hxa h'.symm | exact hxa h' | exact hac h' | exact hac h'.symm
  · have hm : x ∈ ({a,c}:Finset (Fin n)) := by
      have ht : x ∈ ({x,a}:Finset (Fin n)) := by simp
      rwa [h] at ht
    simp only [Finset.mem_insert, Finset.mem_singleton] at hm
    rcases hm with h'|h' <;> first | exact hxa h' | exact hxa h'.symm | exact hxc h' | exact hxc h'.symm
  · have hm : x ∈ ({a,b,c}:Finset (Fin n)) := by
      have ht : x ∈ ({x,a}:Finset (Fin n)) := by simp
      rwa [h] at ht
    simp only [Finset.mem_insert, Finset.mem_singleton] at hm
    rcases hm with h'|h'|h' <;> first | exact hxa h' | exact hxa h'.symm | exact hxb h' | exact hxb h'.symm | exact hxc h' | exact hxc h'.symm
  · have hm : a ∈ ({x}:Finset (Fin n)) := by
      have ht : a ∈ ({x,a}:Finset (Fin n)) := by simp
      rwa [h] at ht
    simp only [Finset.mem_singleton] at hm
    first | exact hxa hm | exact hxa hm.symm

private lemma op1370_cyclic_two_set_blocker_bound_nbcG0 (n : ℕ) (x a b c : Fin n) (hxa : x ≠ a) (hxb : x ≠ b) (hxc : x ≠ c)
    (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) :
    ({b,c}:Finset (Fin n)) ∉ ({{x,a},{a,b},{a,b,c},{x}}:Finset (Finset (Fin n))) := by
  simp only [Finset.mem_insert, Finset.mem_singleton]
  rintro (h|h|h|h)
  · have hm : b ∈ ({x,a}:Finset (Fin n)) := by
      have ht : b ∈ ({b,c}:Finset (Fin n)) := by simp
      rwa [h] at ht
    simp only [Finset.mem_insert, Finset.mem_singleton] at hm
    rcases hm with h'|h' <;> first | exact hxb h' | exact hxb h'.symm | exact hab h' | exact hab h'.symm
  · have hm : c ∈ ({a,b}:Finset (Fin n)) := by
      have ht : c ∈ ({b,c}:Finset (Fin n)) := by simp
      rwa [h] at ht
    simp only [Finset.mem_insert, Finset.mem_singleton] at hm
    rcases hm with h'|h' <;> first | exact hac h'.symm | exact hac h' | exact hbc h'.symm | exact hbc h'
  · have hm : a ∈ ({b,c}:Finset (Fin n)) := by
      have ht : a ∈ ({a,b,c}:Finset (Fin n)) := by simp
      rwa [← h] at ht
    simp only [Finset.mem_insert, Finset.mem_singleton] at hm
    rcases hm with h'|h' <;> first | exact hab h' | exact hab h'.symm | exact hac h' | exact hac h'.symm
  · have hm : b ∈ ({x}:Finset (Fin n)) := by
      have ht : b ∈ ({b,c}:Finset (Fin n)) := by simp
      rwa [h] at ht
    simp only [Finset.mem_singleton] at hm
    first | exact hxb hm | exact hxb hm.symm

private lemma op1370_cyclic_two_set_blocker_bound_nabG1 (n : ℕ) (x a b c : Fin n) (hxa : x ≠ a) (hxb : x ≠ b) (hxc : x ≠ c)
    (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) :
    ({a,b}:Finset (Fin n)) ∉ ({{x,b},{b,c},{a,b,c},{x}}:Finset (Finset (Fin n))) := by
  simp only [Finset.mem_insert, Finset.mem_singleton]
  rintro (h|h|h|h)
  · have hm : a ∈ ({x,b}:Finset (Fin n)) := by
      have ht : a ∈ ({a,b}:Finset (Fin n)) := by simp
      rwa [h] at ht
    simp only [Finset.mem_insert, Finset.mem_singleton] at hm
    rcases hm with h'|h' <;> first | exact hxa h'.symm | exact hxa h' | exact hab h' | exact hab h'.symm
  · have hm : a ∈ ({b,c}:Finset (Fin n)) := by
      have ht : a ∈ ({a,b}:Finset (Fin n)) := by simp
      rwa [h] at ht
    simp only [Finset.mem_insert, Finset.mem_singleton] at hm
    rcases hm with h'|h' <;> first | exact hab h' | exact hab h'.symm | exact hac h' | exact hac h'.symm
  · have hm : c ∈ ({a,b}:Finset (Fin n)) := by
      have ht : c ∈ ({a,b,c}:Finset (Fin n)) := by simp
      rwa [← h] at ht
    simp only [Finset.mem_insert, Finset.mem_singleton] at hm
    rcases hm with h'|h' <;> first | exact hac h'.symm | exact hac h' | exact hbc h'.symm | exact hbc h'
  · have hm : a ∈ ({x}:Finset (Fin n)) := by
      have ht : a ∈ ({a,b}:Finset (Fin n)) := by simp
      rwa [h] at ht
    simp only [Finset.mem_singleton] at hm
    first | exact hxa hm | exact hxa hm.symm

private lemma op1370_cyclic_two_set_blocker_bound_nabG2 (n : ℕ) (x a b c : Fin n) (hxa : x ≠ a) (hxb : x ≠ b) (hxc : x ≠ c)
    (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) :
    ({a,b}:Finset (Fin n)) ∉ ({{x,c},{a,c},{a,b,c},{x}}:Finset (Finset (Fin n))) := by
  simp only [Finset.mem_insert, Finset.mem_singleton]
  rintro (h|h|h|h)
  · have hm : a ∈ ({x,c}:Finset (Fin n)) := by
      have ht : a ∈ ({a,b}:Finset (Fin n)) := by simp
      rwa [h] at ht
    simp only [Finset.mem_insert, Finset.mem_singleton] at hm
    rcases hm with h'|h' <;> first | exact hxa h'.symm | exact hxa h' | exact hac h' | exact hac h'.symm
  · have hm : b ∈ ({a,c}:Finset (Fin n)) := by
      have ht : b ∈ ({a,b}:Finset (Fin n)) := by simp
      rwa [h] at ht
    simp only [Finset.mem_insert, Finset.mem_singleton] at hm
    rcases hm with h'|h' <;> first | exact hab h'.symm | exact hab h' | exact hbc h' | exact hbc h'.symm
  · have hm : c ∈ ({a,b}:Finset (Fin n)) := by
      have ht : c ∈ ({a,b,c}:Finset (Fin n)) := by simp
      rwa [← h] at ht
    simp only [Finset.mem_insert, Finset.mem_singleton] at hm
    rcases hm with h'|h' <;> first | exact hac h'.symm | exact hac h' | exact hbc h'.symm | exact hbc h'
  · have hm : a ∈ ({x}:Finset (Fin n)) := by
      have ht : a ∈ ({a,b}:Finset (Fin n)) := by simp
      rwa [h] at ht
    simp only [Finset.mem_singleton] at hm
    first | exact hxa hm | exact hxa hm.symm

private lemma op1370_cyclic_two_set_blocker_bound_sliceX (n : ℕ) (𝒜 : Fin 3 → Finset (Finset (Fin n)))
    (x a b c : Fin n) (hxa : x ≠ a) (hxb : x ≠ b) (hxc : x ≠ c)
    (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c)
    (hinc : strongly_incomparable 𝒜)
    (trace0 : ∀ A ∈ 𝒜 0, A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ ({{x,a},{a,b},{a,b,c},{x}}:Finset (Finset (Fin n))))
    (trace1 : ∀ A ∈ 𝒜 1, A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ ({{x,b},{b,c},{a,b,c},{x}}:Finset (Finset (Fin n))))
    (trace2 : ∀ A ∈ 𝒜 2, A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ ({{x,c},{a,c},{a,b,c},{x}}:Finset (Finset (Fin n))))
    (nxbG0 : ({x,b}:Finset (Fin n)) ∉ ({{x,a},{a,b},{a,b,c},{x}}:Finset (Finset (Fin n))))
    (nxaG1 : ({x,a}:Finset (Fin n)) ∉ ({{x,b},{b,c},{a,b,c},{x}}:Finset (Finset (Fin n))))
    (nxaG2 : ({x,a}:Finset (Fin n)) ∉ ({{x,c},{a,c},{a,b,c},{x}}:Finset (Finset (Fin n))))
    (W : Finset (Fin n)) (hWC : W ⊆ ({x,a,b,c}:Finset (Fin n))ᶜ) :
    (Finset.filter (fun A => A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ ({{x,a},{x,b},{x,c},{x}}:Finset (Finset (Fin n))))
      (Finset.filter (fun A => A ∩ ({x,a,b,c}:Finset (Fin n))ᶜ = W) (𝒜 0 ∪ 𝒜 1 ∪ 𝒜 2))).card ≤ 3 := by
  classical
  let F1 : Finset (Finset (Fin n)) := Finset.filter (fun A => A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ ({{x,a},{x,b},{x,c},{x}}:Finset (Finset (Fin n)))) (Finset.filter (fun A => A ∩ ({x,a,b,c}:Finset (Fin n))ᶜ = W) (𝒜 0 ∪ 𝒜 1 ∪ 𝒜 2))
  change F1.card ≤ 3
  have interU : ∀ S : Finset (Fin n), S ⊆ ({x,a,b,c}:Finset (Fin n)) →
      (W ∪ S) ∩ ({x,a,b,c}:Finset (Fin n)) = S := by
    intro S hSC
    ext y
    simp only [Finset.mem_inter, Finset.mem_union]
    constructor
    · rintro ⟨hyW | hyS, hyC⟩
      · exact absurd hyC (Finset.mem_compl.mp (hWC hyW))
      · exact hyS
    · intro hyS; exact ⟨Or.inr hyS, hSC hyS⟩
  have htrA : (W ∪ {x,a} : Finset (Fin n)) ∩ ({x,a,b,c}:Finset (Fin n)) = {x,a} :=
    interU {x,a} (by intro y hy; simp only [Finset.mem_insert, Finset.mem_singleton] at hy ⊢; tauto)
  have htrB : (W ∪ {x,b} : Finset (Fin n)) ∩ ({x,a,b,c}:Finset (Fin n)) = {x,b} :=
    interU {x,b} (by intro y hy; simp only [Finset.mem_insert, Finset.mem_singleton] at hy ⊢; tauto)
  have hsubPA : (W ∪ {x} : Finset (Fin n)) ⊆ (W ∪ {x,a} : Finset (Fin n)) := by
    intro y hy; simp only [Finset.mem_union, Finset.mem_insert, Finset.mem_singleton] at hy ⊢; tauto
  have hsubPB : (W ∪ {x} : Finset (Fin n)) ⊆ (W ∪ {x,b} : Finset (Fin n)) := by
    intro y hy; simp only [Finset.mem_union, Finset.mem_insert, Finset.mem_singleton] at hy ⊢; tauto
  by_contra hle
  push_neg at hle
  let K : Finset (Finset (Fin n)) := {W ∪ {x}, W ∪ {x,a}, W ∪ {x,b}, W ∪ {x,c}}
  have hFK : F1 ⊆ K := by
    intro A hA
    simp only [F1, Finset.mem_filter] at hA
    obtain ⟨⟨hAU, hAW⟩, htGX⟩ := hA
    have hAeq : A = W ∪ (A ∩ ({x,a,b,c}:Finset (Fin n))) := by
      have := Finset.sdiff_union_inter A ({x,a,b,c}:Finset (Fin n))
      rw [Finset.sdiff_eq_inter_compl, hAW] at this
      exact this.symm
    simp only [Finset.mem_insert, Finset.mem_singleton] at htGX
    rw [hAeq]
    simp only [K, Finset.mem_insert, Finset.mem_singleton] at htGX ⊢
    rcases htGX with h|h|h|h
    · right; left; rw [h]
    · right; right; left; rw [h]
    · right; right; right; rw [h]
    · left; rw [h]
  have hKcard : K.card ≤ 4 := by
    have h1 := Finset.card_insert_le (W ∪ {x} : Finset (Fin n)) (insert (W ∪ {x,a} : Finset (Fin n)) (insert (W ∪ {x,b} : Finset (Fin n)) ({(W ∪ {x,c} : Finset (Fin n))} : Finset (Finset (Fin n)))))
    have h2 := Finset.card_insert_le (W ∪ {x,a} : Finset (Fin n)) (insert (W ∪ {x,b} : Finset (Fin n)) ({(W ∪ {x,c} : Finset (Fin n))} : Finset (Finset (Fin n))))
    have h3 := Finset.card_insert_le (W ∪ {x,b} : Finset (Fin n)) ({(W ∪ {x,c} : Finset (Fin n))} : Finset (Finset (Fin n)))
    rw [Finset.card_singleton] at h3
    change ({W ∪ {x}, W ∪ {x,a}, W ∪ {x,b}, W ∪ {x,c}} : Finset (Finset (Fin n))).card ≤ 4
    omega
  have hcardge : 4 ≤ F1.card := by omega
  have hFKle : F1.card ≤ K.card := Finset.card_le_card hFK
  have hKle : K.card ≤ F1.card := by omega
  have hKF : F1 = K := Finset.eq_of_subset_of_card_le hFK hKle
  have inU : ∀ X, X ∈ F1 → X ∈ 𝒜 0 ∪ 𝒜 1 ∪ 𝒜 2 := by
    intro X hX
    simp only [F1, Finset.mem_filter] at hX
    exact hX.1.1
  have hP0U : (W ∪ {x} : Finset (Fin n)) ∈ 𝒜 0 ∪ 𝒜 1 ∪ 𝒜 2 :=
    inU _ (by rw [hKF]; simp [K])
  have hPAU : (W ∪ {x,a} : Finset (Fin n)) ∈ 𝒜 0 ∪ 𝒜 1 ∪ 𝒜 2 :=
    inU _ (by rw [hKF]; simp [K])
  have hPBU : (W ∪ {x,b} : Finset (Fin n)) ∈ 𝒜 0 ∪ 𝒜 1 ∪ 𝒜 2 :=
    inU _ (by rw [hKF]; simp [K])
  simp only [Finset.mem_union] at hP0U hPAU hPBU
  rcases hP0U with hP0_01 | hP0_2
  · rcases hP0_01 with hP0_0 | hP0_1
    · have hPB0 : (W ∪ {x,b} : Finset (Fin n)) ∈ 𝒜 0 := by
        rcases hPBU with h01 | h2'
        · rcases h01 with h0 | h1
          · exact h0
          · exact absurd hsubPB (hinc 0 1 (by decide) (W ∪ {x}) hP0_0 (W ∪ {x,b}) h1)
        · exact absurd hsubPB (hinc 0 2 (by decide) (W ∪ {x}) hP0_0 (W ∪ {x,b}) h2')
      have hmem : ({x,b}:Finset (Fin n)) ∈ ({{x,a},{a,b},{a,b,c},{x}}:Finset (Finset (Fin n))) := by
        have htr := trace0 (W ∪ {x,b}) hPB0
        rw [htrB] at htr; exact htr
      exact nxbG0 hmem
    · have hPA1 : (W ∪ {x,a} : Finset (Fin n)) ∈ 𝒜 1 := by
        rcases hPAU with h01 | h2'
        · rcases h01 with h0 | h1
          · exact absurd hsubPA (hinc 1 0 (by decide) (W ∪ {x}) hP0_1 (W ∪ {x,a}) h0)
          · exact h1
        · exact absurd hsubPA (hinc 1 2 (by decide) (W ∪ {x}) hP0_1 (W ∪ {x,a}) h2')
      have hmem : ({x,a}:Finset (Fin n)) ∈ ({{x,b},{b,c},{a,b,c},{x}}:Finset (Finset (Fin n))) := by
        have htr := trace1 (W ∪ {x,a}) hPA1
        rw [htrA] at htr; exact htr
      exact nxaG1 hmem
  · have hPA2 : (W ∪ {x,a} : Finset (Fin n)) ∈ 𝒜 2 := by
      rcases hPAU with h01 | h2'
      · rcases h01 with h0 | h1
        · exact absurd hsubPA (hinc 2 0 (by decide) (W ∪ {x}) hP0_2 (W ∪ {x,a}) h0)
        · exact absurd hsubPA (hinc 2 1 (by decide) (W ∪ {x}) hP0_2 (W ∪ {x,a}) h1)
      · exact h2'
    have hmem : ({x,a}:Finset (Fin n)) ∈ ({{x,c},{a,c},{a,b,c},{x}}:Finset (Finset (Fin n))) := by
      have htr := trace2 (W ∪ {x,a}) hPA2
      rw [htrA] at htr; exact htr
    exact nxaG2 hmem

private lemma op1370_cyclic_two_set_blocker_bound_sliceH (n : ℕ) (𝒜 : Fin 3 → Finset (Finset (Fin n)))
    (x a b c : Fin n) (hxa : x ≠ a) (hxb : x ≠ b) (hxc : x ≠ c)
    (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c)
    (hinc : strongly_incomparable 𝒜)
    (trace0 : ∀ A ∈ 𝒜 0, A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ ({{x,a},{a,b},{a,b,c},{x}}:Finset (Finset (Fin n))))
    (trace1 : ∀ A ∈ 𝒜 1, A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ ({{x,b},{b,c},{a,b,c},{x}}:Finset (Finset (Fin n))))
    (trace2 : ∀ A ∈ 𝒜 2, A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ ({{x,c},{a,c},{a,b,c},{x}}:Finset (Finset (Fin n))))
    (nbcG0 : ({b,c}:Finset (Fin n)) ∉ ({{x,a},{a,b},{a,b,c},{x}}:Finset (Finset (Fin n))))
    (nabG1 : ({a,b}:Finset (Fin n)) ∉ ({{x,b},{b,c},{a,b,c},{x}}:Finset (Finset (Fin n))))
    (nabG2 : ({a,b}:Finset (Fin n)) ∉ ({{x,c},{a,c},{a,b,c},{x}}:Finset (Finset (Fin n))))
    (W : Finset (Fin n)) (hWC : W ⊆ ({x,a,b,c}:Finset (Fin n))ᶜ) :
    (Finset.filter (fun A => A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ ({{a,b},{b,c},{a,c},{a,b,c}}:Finset (Finset (Fin n))))
      (Finset.filter (fun A => A ∩ ({x,a,b,c}:Finset (Fin n))ᶜ = W) (𝒜 0 ∪ 𝒜 1 ∪ 𝒜 2))).card ≤ 3 := by
  classical
  let F2 : Finset (Finset (Fin n)) := Finset.filter (fun A => A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ ({{a,b},{b,c},{a,c},{a,b,c}}:Finset (Finset (Fin n)))) (Finset.filter (fun A => A ∩ ({x,a,b,c}:Finset (Fin n))ᶜ = W) (𝒜 0 ∪ 𝒜 1 ∪ 𝒜 2))
  change F2.card ≤ 3
  have interU : ∀ S : Finset (Fin n), S ⊆ ({x,a,b,c}:Finset (Fin n)) →
      (W ∪ S) ∩ ({x,a,b,c}:Finset (Fin n)) = S := by
    intro S hSC
    ext y
    simp only [Finset.mem_inter, Finset.mem_union]
    constructor
    · rintro ⟨hyW | hyS, hyC⟩
      · exact absurd hyC (Finset.mem_compl.mp (hWC hyW))
      · exact hyS
    · intro hyS; exact ⟨Or.inr hyS, hSC hyS⟩
  have htrAB : (W ∪ {a,b} : Finset (Fin n)) ∩ ({x,a,b,c}:Finset (Fin n)) = {a,b} :=
    interU {a,b} (by intro y hy; simp only [Finset.mem_insert, Finset.mem_singleton] at hy ⊢; tauto)
  have htrBC : (W ∪ {b,c} : Finset (Fin n)) ∩ ({x,a,b,c}:Finset (Fin n)) = {b,c} :=
    interU {b,c} (by intro y hy; simp only [Finset.mem_insert, Finset.mem_singleton] at hy ⊢; tauto)
  have hsubAB : (W ∪ {a,b} : Finset (Fin n)) ⊆ (W ∪ {a,b,c} : Finset (Fin n)) := by
    intro y hy; simp only [Finset.mem_union, Finset.mem_insert, Finset.mem_singleton] at hy ⊢; tauto
  have hsubBC : (W ∪ {b,c} : Finset (Fin n)) ⊆ (W ∪ {a,b,c} : Finset (Fin n)) := by
    intro y hy; simp only [Finset.mem_union, Finset.mem_insert, Finset.mem_singleton] at hy ⊢; tauto
  by_contra hle
  push_neg at hle
  let K2 : Finset (Finset (Fin n)) := {W ∪ {a,b}, W ∪ {b,c}, W ∪ {a,c}, W ∪ {a,b,c}}
  have hFK : F2 ⊆ K2 := by
    intro A hA
    simp only [F2, Finset.mem_filter] at hA
    obtain ⟨⟨hAU, hAW⟩, htGH⟩ := hA
    have hAeq : A = W ∪ (A ∩ ({x,a,b,c}:Finset (Fin n))) := by
      have := Finset.sdiff_union_inter A ({x,a,b,c}:Finset (Fin n))
      rw [Finset.sdiff_eq_inter_compl, hAW] at this
      exact this.symm
    simp only [Finset.mem_insert, Finset.mem_singleton] at htGH
    rw [hAeq]
    simp only [K2, Finset.mem_insert, Finset.mem_singleton] at htGH ⊢
    rcases htGH with h|h|h|h
    · left; rw [h]
    · right; left; rw [h]
    · right; right; left; rw [h]
    · right; right; right; rw [h]
  have hKcard : K2.card ≤ 4 := by
    have h1 := Finset.card_insert_le (W ∪ {a,b} : Finset (Fin n)) (insert (W ∪ {b,c} : Finset (Fin n)) (insert (W ∪ {a,c} : Finset (Fin n)) ({(W ∪ {a,b,c} : Finset (Fin n))} : Finset (Finset (Fin n)))))
    have h2 := Finset.card_insert_le (W ∪ {b,c} : Finset (Fin n)) (insert (W ∪ {a,c} : Finset (Fin n)) ({(W ∪ {a,b,c} : Finset (Fin n))} : Finset (Finset (Fin n))))
    have h3 := Finset.card_insert_le (W ∪ {a,c} : Finset (Fin n)) ({(W ∪ {a,b,c} : Finset (Fin n))} : Finset (Finset (Fin n)))
    rw [Finset.card_singleton] at h3
    change ({W ∪ {a,b}, W ∪ {b,c}, W ∪ {a,c}, W ∪ {a,b,c}} : Finset (Finset (Fin n))).card ≤ 4
    omega
  have hcardge : 4 ≤ F2.card := by omega
  have hFKle : F2.card ≤ K2.card := Finset.card_le_card hFK
  have hKle : K2.card ≤ F2.card := by omega
  have hKF : F2 = K2 := Finset.eq_of_subset_of_card_le hFK hKle
  have inU : ∀ X, X ∈ F2 → X ∈ 𝒜 0 ∪ 𝒜 1 ∪ 𝒜 2 := by
    intro X hX
    simp only [F2, Finset.mem_filter] at hX
    exact hX.1.1
  have hYHU : (W ∪ {a,b,c} : Finset (Fin n)) ∈ 𝒜 0 ∪ 𝒜 1 ∪ 𝒜 2 :=
    inU _ (by rw [hKF]; simp [K2])
  have hYabU : (W ∪ {a,b} : Finset (Fin n)) ∈ 𝒜 0 ∪ 𝒜 1 ∪ 𝒜 2 :=
    inU _ (by rw [hKF]; simp [K2])
  have hYbcU : (W ∪ {b,c} : Finset (Fin n)) ∈ 𝒜 0 ∪ 𝒜 1 ∪ 𝒜 2 :=
    inU _ (by rw [hKF]; simp [K2])
  simp only [Finset.mem_union] at hYHU hYabU hYbcU
  rcases hYHU with hYH_01 | hYH_2
  · rcases hYH_01 with hYH_0 | hYH_1
    · have hYbc0 : (W ∪ {b,c} : Finset (Fin n)) ∈ 𝒜 0 := by
        rcases hYbcU with h01 | h2'
        · rcases h01 with h0 | h1
          · exact h0
          · exact absurd hsubBC (hinc 1 0 (by decide) (W ∪ {b,c}) h1 (W ∪ {a,b,c}) hYH_0)
        · exact absurd hsubBC (hinc 2 0 (by decide) (W ∪ {b,c}) h2' (W ∪ {a,b,c}) hYH_0)
      have hmem : ({b,c}:Finset (Fin n)) ∈ ({{x,a},{a,b},{a,b,c},{x}}:Finset (Finset (Fin n))) := by
        have htr := trace0 (W ∪ {b,c}) hYbc0
        rw [htrBC] at htr; exact htr
      exact nbcG0 hmem
    · have hYab1 : (W ∪ {a,b} : Finset (Fin n)) ∈ 𝒜 1 := by
        rcases hYabU with h01 | h2'
        · rcases h01 with h0 | h1
          · exact absurd hsubAB (hinc 0 1 (by decide) (W ∪ {a,b}) h0 (W ∪ {a,b,c}) hYH_1)
          · exact h1
        · exact absurd hsubAB (hinc 2 1 (by decide) (W ∪ {a,b}) h2' (W ∪ {a,b,c}) hYH_1)
      have hmem : ({a,b}:Finset (Fin n)) ∈ ({{x,b},{b,c},{a,b,c},{x}}:Finset (Finset (Fin n))) := by
        have htr := trace1 (W ∪ {a,b}) hYab1
        rw [htrAB] at htr; exact htr
      exact nabG1 hmem
  · have hYab2 : (W ∪ {a,b} : Finset (Fin n)) ∈ 𝒜 2 := by
      rcases hYabU with h01 | h2'
      · rcases h01 with h0 | h1
        · exact absurd hsubAB (hinc 0 2 (by decide) (W ∪ {a,b}) h0 (W ∪ {a,b,c}) hYH_2)
        · exact absurd hsubAB (hinc 1 2 (by decide) (W ∪ {a,b}) h1 (W ∪ {a,b,c}) hYH_2)
      · exact h2'
    have hmem : ({a,b}:Finset (Fin n)) ∈ ({{x,c},{a,c},{a,b,c},{x}}:Finset (Finset (Fin n))) := by
      have htr := trace2 (W ∪ {a,b}) hYab2
      rw [htrAB] at htr; exact htr
    exact nabG2 hmem

private lemma op1370_cyclic_two_set_blocker_bound_fiber (n : ℕ) (𝒜 : Fin 3 → Finset (Finset (Fin n)))
    (x a b c : Fin n)
    (trace0 : ∀ A ∈ 𝒜 0, A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ ({{x,a},{a,b},{a,b,c},{x}}:Finset (Finset (Fin n))))
    (trace1 : ∀ A ∈ 𝒜 1, A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ ({{x,b},{b,c},{a,b,c},{x}}:Finset (Finset (Fin n))))
    (trace2 : ∀ A ∈ 𝒜 2, A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ ({{x,c},{a,c},{a,b,c},{x}}:Finset (Finset (Fin n))))
    (sliceXf : ∀ W, W ⊆ ({x,a,b,c}:Finset (Fin n))ᶜ →
      (Finset.filter (fun A => A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ ({{x,a},{x,b},{x,c},{x}}:Finset (Finset (Fin n))))
        (Finset.filter (fun A => A ∩ ({x,a,b,c}:Finset (Fin n))ᶜ = W) (𝒜 0 ∪ 𝒜 1 ∪ 𝒜 2))).card ≤ 3)
    (sliceHf : ∀ W, W ⊆ ({x,a,b,c}:Finset (Fin n))ᶜ →
      (Finset.filter (fun A => A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ ({{a,b},{b,c},{a,c},{a,b,c}}:Finset (Finset (Fin n))))
        (Finset.filter (fun A => A ∩ ({x,a,b,c}:Finset (Fin n))ᶜ = W) (𝒜 0 ∪ 𝒜 1 ∪ 𝒜 2))).card ≤ 3) :
    ∀ W ∈ ({x,a,b,c}:Finset (Fin n))ᶜ.powerset,
      (Finset.filter (fun A => A ∩ ({x,a,b,c}:Finset (Fin n))ᶜ = W) (𝒜 0 ∪ 𝒜 1 ∪ 𝒜 2)).card ≤ 6 := by
  classical
  intro W hW
  have hWC : W ⊆ ({x,a,b,c}:Finset (Fin n))ᶜ := Finset.mem_powerset.mp hW
  let F : Finset (Finset (Fin n)) := Finset.filter (fun A => A ∩ ({x,a,b,c}:Finset (Fin n))ᶜ = W) (𝒜 0 ∪ 𝒜 1 ∪ 𝒜 2)
  let GX : Finset (Finset (Fin n)) := {{x,a},{x,b},{x,c},{x}}
  let GH : Finset (Finset (Fin n)) := {{a,b},{b,c},{a,c},{a,b,c}}
  change F.card ≤ 6
  have hcover : ∀ A ∈ F, A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ GX ∨ A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ GH := by
    intro A hA
    simp only [F, Finset.mem_filter] at hA
    obtain ⟨hAU, hAW⟩ := hA
    simp only [Finset.mem_union] at hAU
    rcases hAU with (hA0 | hA1) | hA2
    · have h := trace0 A hA0
      simp only [GX, GH, Finset.mem_insert, Finset.mem_singleton] at h ⊢
      tauto
    · have h := trace1 A hA1
      simp only [GX, GH, Finset.mem_insert, Finset.mem_singleton] at h ⊢
      tauto
    · have h := trace2 A hA2
      simp only [GX, GH, Finset.mem_insert, Finset.mem_singleton] at h ⊢
      tauto
  let F1 : Finset (Finset (Fin n)) := F.filter (fun A => A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ GX)
  let F2 : Finset (Finset (Fin n)) := F.filter (fun A => A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ GH)
  have hsplit : F.card = F1.card + (F.filter (fun A => ¬ (A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ GX))).card := by
    have hthis := Finset.card_filter_add_card_filter_not (s := F) (p := fun A => A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ GX)
    exact hthis.symm
  have hsub12 : F.filter (fun A => ¬ (A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ GX)) ⊆ F2 := by
    intro A hA
    simp only [Finset.mem_filter] at hA
    obtain ⟨hAF, hAnG⟩ := hA
    simp only [F2, Finset.mem_filter]
    refine ⟨hAF, ?_⟩
    rcases hcover A hAF with h | h
    · exact absurd h hAnG
    · exact h
  have hle2 : (F.filter (fun A => ¬ (A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ GX))).card ≤ F2.card :=
    Finset.card_le_card hsub12
  have hF1le : F1.card ≤ 3 := by
    rw [show F1 = Finset.filter (fun A => A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ GX) F from rfl]
    rw [show F = Finset.filter (fun A => A ∩ ({x,a,b,c}:Finset (Fin n))ᶜ = W) (𝒜 0 ∪ 𝒜 1 ∪ 𝒜 2) from rfl]
    rw [show GX = ({{x,a},{x,b},{x,c},{x}}:Finset (Finset (Fin n))) from rfl]
    exact sliceXf W hWC
  have hF2le : F2.card ≤ 3 := by
    rw [show F2 = Finset.filter (fun A => A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ GH) F from rfl]
    rw [show F = Finset.filter (fun A => A ∩ ({x,a,b,c}:Finset (Fin n))ᶜ = W) (𝒜 0 ∪ 𝒜 1 ∪ 𝒜 2) from rfl]
    rw [show GH = ({{a,b},{b,c},{a,c},{a,b,c}}:Finset (Finset (Fin n))) from rfl]
    exact sliceHf W hWC
  omega

theorem op1370_cyclic_two_set_blocker_bound (n : ℕ) (hn : 4 ≤ n) (𝒜 : Fin 3 → Finset (Finset (Fin n))) (hinc : strongly_incomparable 𝒜) (x a b c : Fin n) (hxa : x ≠ a) (hxb : x ≠ b) (hxc : x ≠ c) (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) (h0 : ({x,a} : Finset (Fin n)) ∈ 𝒜 0 ∧ ({x,c} : Finset (Fin n))ᶜ ∈ 𝒜 0) (h1 : ({x,b} : Finset (Fin n)) ∈ 𝒜 1 ∧ ({x,a} : Finset (Fin n))ᶜ ∈ 𝒜 1) (h2 : ({x,c} : Finset (Fin n)) ∈ 𝒜 2 ∧ ({x,b} : Finset (Fin n))ᶜ ∈ 𝒜 2) : ∑ i, (𝒜 i).card ≤ 3 * 2 ^ (n - 3) := by
  classical
  let C : Finset (Fin n) := {x,a,b,c}
  have hC : C = {x,a,b,c} := rfl
  have hCcard : C.card = 4 := by
    rw [hC]
    have h1' : x ∉ (insert a (insert b ({c}:Finset (Fin n)))) := by simp [hxa, hxb, hxc]
    have h2' : a ∉ (insert b ({c}:Finset (Fin n))) := by simp [hab, hac]
    have h3' : b ∉ ({c}:Finset (Fin n)) := by simp [hbc]
    rw [show ({x,a,b,c} : Finset (Fin n)) = insert x (insert a (insert b {c})) from rfl,
      Finset.card_insert_of_notMem h1', Finset.card_insert_of_notMem h2', Finset.card_insert_of_notMem h3', Finset.card_singleton]
  have hCcomplcard : Cᶜ.card = n - 4 := by
    rw [Finset.card_compl, Fintype.card_fin, hCcard]
  let U : Finset (Finset (Fin n)) := 𝒜 0 ∪ 𝒜 1 ∪ 𝒜 2
  have hdisj01 : Disjoint (𝒜 0) (𝒜 1) := by
    rw [Finset.disjoint_left]; intro A hA0 hA1
    exact hinc 0 1 (by decide) A hA0 A hA1 (Finset.Subset.refl A)
  have hdisj02 : Disjoint (𝒜 0) (𝒜 2) := by
    rw [Finset.disjoint_left]; intro A hA0 hA2
    exact hinc 0 2 (by decide) A hA0 A hA2 (Finset.Subset.refl A)
  have hdisj12 : Disjoint (𝒜 1) (𝒜 2) := by
    rw [Finset.disjoint_left]; intro A hA1 hA2
    exact hinc 1 2 (by decide) A hA1 A hA2 (Finset.Subset.refl A)
  have hdisj012 : Disjoint (𝒜 0 ∪ 𝒜 1) (𝒜 2) := by
    rw [Finset.disjoint_left]; intro A hA hA2
    rcases Finset.mem_union.mp hA with hA0 | hA1
    · exact (Finset.disjoint_left.mp hdisj02) hA0 hA2
    · exact (Finset.disjoint_left.mp hdisj12) hA1 hA2
  have hsum : ∑ i, (𝒜 i).card = U.card := by
    rw [Fin.sum_univ_three, show U = 𝒜 0 ∪ 𝒜 1 ∪ 𝒜 2 from rfl,
      Finset.card_union_of_disjoint hdisj012, Finset.card_union_of_disjoint hdisj01]
  rw [hsum]
  have hmap : Set.MapsTo (fun A => A ∩ Cᶜ) (↑U) (↑(Cᶜ).powerset) := by
    intro A hA
    simp only [Finset.mem_coe, Finset.mem_powerset]
    exact Finset.inter_subset_right
  rw [Finset.card_eq_sum_card_fiberwise hmap]
  have trace0' : ∀ A ∈ 𝒜 0, A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ ({{x,a},{a,b},{a,b,c},{x}}:Finset (Finset (Fin n))) :=
    fun A hA => op1370_cyclic_two_set_blocker_bound_trace0 n 𝒜 hinc x a b c hxa hxb hxc hab hac hbc h1 h2 A hA
  have trace1' : ∀ A ∈ 𝒜 1, A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ ({{x,b},{b,c},{a,b,c},{x}}:Finset (Finset (Fin n))) :=
    fun A hA => op1370_cyclic_two_set_blocker_bound_trace1 n 𝒜 hinc x a b c hxa hxb hxc hab hac hbc h0 h2 A hA
  have trace2' : ∀ A ∈ 𝒜 2, A ∩ ({x,a,b,c}:Finset (Fin n)) ∈ ({{x,c},{a,c},{a,b,c},{x}}:Finset (Finset (Fin n))) :=
    fun A hA => op1370_cyclic_two_set_blocker_bound_trace2 n 𝒜 hinc x a b c hxa hxb hxc hab hac hbc h0 h1 A hA
  have sliceX' := fun (W : Finset (Fin n)) (hW : W ⊆ ({x,a,b,c}:Finset (Fin n))ᶜ) =>
    op1370_cyclic_two_set_blocker_bound_sliceX n 𝒜 x a b c hxa hxb hxc hab hac hbc hinc trace0' trace1' trace2'
      (op1370_cyclic_two_set_blocker_bound_nxbG0 n x a b c hxa hxb hxc hab hac hbc)
      (op1370_cyclic_two_set_blocker_bound_nxaG1 n x a b c hxa hxb hxc hab hac hbc)
      (op1370_cyclic_two_set_blocker_bound_nxaG2 n x a b c hxa hxb hxc hab hac hbc) W hW
  have sliceH' := fun (W : Finset (Fin n)) (hW : W ⊆ ({x,a,b,c}:Finset (Fin n))ᶜ) =>
    op1370_cyclic_two_set_blocker_bound_sliceH n 𝒜 x a b c hxa hxb hxc hab hac hbc hinc trace0' trace1' trace2'
      (op1370_cyclic_two_set_blocker_bound_nbcG0 n x a b c hxa hxb hxc hab hac hbc)
      (op1370_cyclic_two_set_blocker_bound_nabG1 n x a b c hxa hxb hxc hab hac hbc)
      (op1370_cyclic_two_set_blocker_bound_nabG2 n x a b c hxa hxb hxc hab hac hbc) W hW
  have hfib := op1370_cyclic_two_set_blocker_bound_fiber n 𝒜 x a b c trace0' trace1' trace2' sliceX' sliceH'
  have hfib' : ∀ W ∈ (Cᶜ).powerset, (U.filter (fun A => A ∩ Cᶜ = W)).card ≤ 6 := by
    intro W hW
    exact hfib W hW
  calc
    ∑ W ∈ (Cᶜ).powerset, (U.filter (fun A => A ∩ Cᶜ = W)).card
        ≤ ∑ W ∈ (Cᶜ).powerset, 6 := Finset.sum_le_sum hfib'
    _ = 6 * (Cᶜ).powerset.card := by rw [Finset.sum_const, smul_eq_mul]; exact Nat.mul_comm _ _
    _ = 6 * 2 ^ (Cᶜ.card) := by rw [Finset.card_powerset]
    _ = 6 * 2 ^ (n - 4) := by rw [hCcomplcard]
    _ = 3 * 2 ^ (n - 3) := by
          have hk : n - 3 = (n - 4) + 1 := by omega
          rw [hk, Nat.pow_succ]; ring
See it in the graphDiscuss this resultChallenge it