AFTD Auto-Formalizing Theoretical Domains

op1370_two_set_complement_block_bound

theoremverifiedoriginal

Let n be at least three and let indexed families of subsets of Fin n be mutually strongly incomparable. Suppose there is a coordinate x such that for every nonempty family, some set {x,y} occurs in a different family and its complement occurs in a different family; these two other families may coincide. Then the total size of all families is at most 2^(n-1)-2.

Statement

theorem op1370_two_set_complement_block_bound (n t : ℕ) (hn : 3 ≤ n)
    (𝒜 : Fin t → Finset (Finset (Fin n))) (hinc : strongly_incomparable 𝒜)
    (x : Fin n)
    (hblock : ∀ i : Fin t, (𝒜 i).Nonempty → ∃ j k : Fin t, j ≠ i ∧ k ≠ i ∧
      ∃ y : Fin n, ({x, y} : Finset (Fin n)) ∈ 𝒜 j ∧ ({x, y} : Finset (Fin n))ᶜ ∈ 𝒜 k) :
    ∑ i, (𝒜 i).card ≤ 2 ^ (n - 1) - 2
Related work
A conditional two-set deficit toward Conjecture 4.3 of arXiv:2611.12199, without uncomplementedness or nonemptiness assumptions.
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…
  • op1370_zero_fiber_countFor n at least three, if a family of subsets of Fin n omits the empty set, {x}, its complement, and the full set, and no x-erased fiber…

Read back from the Lean

Let $n, t$ be natural numbers with $n \ge 3$. Let $\mathcal{A} : \mathrm{Fin}(t) \to \mathrm{Finset}(\mathrm{Finset}(\mathrm{Fin}(n)))$ be a family of $t$ collections of subsets of $\mathrm{Fin}(n)$. Assume $\mathcal{A}$ is strongly incomparable (for all distinct $i, j \in \mathrm{Fin}(t)$, no set in $\mathcal{A}(i)$ is a subset of any set in $\mathcal{A}(j)$). Let $x \in \mathrm{Fin}(n)$ be fixed. Assume that for every $i \in \mathrm{Fin}(t)$, if $\mathcal{A}(i)$ is nonempty, then there exist indices $j, k \in \mathrm{Fin}(t)$ with $j \ne i$ and $k \ne i$, and an element $y \in \mathrm{Fin}(n)$, such that $\{x, y\} \in \mathcal{A}(j)$ and $\{x, y\}^c \in \mathcal{A}(k)$ (where the complement is with respect to $\mathrm{Fin}(n)$). Then the total number of sets $\sum_{i \in \mathrm{Fin}(t)} |\mathcal{A}(i)|$ is at most $2^{n - 1} - 2$.

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

The proof, explained

The proof combines all families into their union U = ⋃ i, 𝒜 i, which has size ∑ i, #(𝒜 i) because strong incomparability forces distinct families to be disjoint. By leveraging the blocking pairs {x, y} ∈ 𝒜 j and {x, y}ᶜ ∈ 𝒜 k (with j, k ≠ i), strong incomparability prevents U from containing ∅, {x}, univ.erase x, or univ, and also prevents any set S ∉ U from having both S and S ∪ {x} in U. This zero fiber overlap allows the counting lemma op1370_zero_fiber_count to directly supply the upper bound 2^(n-1) - 2.

  1. Let U be the union of all families 𝒜 i for i : Fin t.

    We define U := univ.biUnion 𝒜 as the collection of all subsets of Fin n appearing in any family 𝒜 i.

    lines 7–9

      open Finset in
      classical
      let U := univ.biUnion 𝒜
  2. Distinct families 𝒜 i and 𝒜 j (with i ≠ j) are mutually disjoint.

    If some set S were in both 𝒜 i and 𝒜 j for i ≠ j, then S ⊆ S would contradict the strong incomparability assumption between distinct families.

    lines 10–14

    uses disjoint_left, Subset.refl

      have hdisj : ∀ i j : Fin t, i ≠ j → Disjoint (𝒜 i) (𝒜 j) := by
        intro i j hij
        rw [disjoint_left]
        intro S hSi hSj
        exact hinc i j hij S hSi S hSj (Subset.refl S)
  3. The cardinality of U is the sum of the cardinalities of the families 𝒜 i.

    Since the families are pairwise disjoint, the size of their union equals the sum of their individual sizes.

    lines 15–17

    uses card_biUnion

      have hsum : U.card = ∑ i, (𝒜 i).card := by
        dsimp [U]
        rw [card_biUnion (fun i _ j _ hij => hdisj i j hij)]
  4. The empty set ∅ does not belong to U.

    If ∅ ∈ U, then ∅ ∈ 𝒜 i for some i. By the blocking hypothesis, there is an index j ≠ i and an element y such that {x, y} ∈ 𝒜 j. But ∅ ⊆ {x, y}, contradicting strong incomparability between 𝒜 i and 𝒜 j.

    lines 18–22

    uses mem_biUnion, empty_subset

      have hempty : (∅ : Finset (Fin n)) ∉ U := by
        intro h
        obtain ⟨i, _, hi⟩ := mem_biUnion.mp h
        obtain ⟨j, k, hji, hki, y, hw, hc⟩ := hblock i ⟨∅, hi⟩
        exact hinc i j hji.symm ∅ hi {x, y} hw (empty_subset _)
  5. The universal set univ does not belong to U.

    If univ ∈ U, then univ ∈ 𝒜 i for some i. The blocking hypothesis gives j ≠ i and y such that {x, y} ∈ 𝒜 j. But {x, y} ⊆ univ, contradicting strong incomparability between 𝒜 j and 𝒜 i.

    lines 23–27

    uses mem_biUnion, subset_univ

      have huniv : (univ : Finset (Fin n)) ∉ U := by
        intro h
        obtain ⟨i, _, hi⟩ := mem_biUnion.mp h
        obtain ⟨j, k, hji, hki, y, hw, hc⟩ := hblock i ⟨univ, hi⟩
        exact hinc j i hji {x, y} hw univ hi (subset_univ _)
  6. The singleton {x} does not belong to U.

    If {x} ∈ U, then {x} ∈ 𝒜 i for some i. The blocking hypothesis gives j ≠ i and y with {x, y} ∈ 𝒜 j. But {x} ⊆ {x, y}, contradicting strong incomparability between 𝒜 i and 𝒜 j.

    lines 28–33

    uses mem_biUnion

      have hx : ({x} : Finset (Fin n)) ∉ U := by
        intro h
        obtain ⟨i, _, hi⟩ := mem_biUnion.mp h
        obtain ⟨j, k, hji, hki, y, hw, hc⟩ := hblock i ⟨{x}, hi⟩
        have hsub : ({x} : Finset (Fin n)) ⊆ {x, y} := by simp
        exact hinc i j hji.symm {x} hi {x, y} hw hsub
  7. The co-singleton univ.erase x does not belong to U.

    If univ.erase x ∈ U, it belongs to 𝒜 i for some i. By the blocking hypothesis, there is k ≠ i and y such that {x, y}ᶜ ∈ 𝒜 k. Since x ∉ {x, y}ᶜ, every element of {x, y}ᶜ is in univ.erase x, so {x, y}ᶜ ⊆ univ.erase x. This contradicts strong incomparability between 𝒜 k and 𝒜 i.

    lines 34–45

    uses mem_biUnion, mem_erase, mem_univ, mem_compl

      have hV : (univ.erase x : Finset (Fin n)) ∉ U := by
        intro h
        obtain ⟨i, _, hi⟩ := mem_biUnion.mp h
        obtain ⟨j, k, hji, hki, y, hw, hc⟩ := hblock i ⟨univ.erase x, hi⟩
        have hsub : ({x, y} : Finset (Fin n))ᶜ ⊆ univ.erase x := by
          intro z hz
          rw [mem_erase]
          refine ⟨?_, mem_univ _⟩
          intro hzx
          subst z
          exact (mem_compl.mp hz) (by simp)
        exact hinc k i hki ({x,y} : Finset (Fin n))ᶜ hc (univ.erase x) hi hsub
  8. For any set S ∈ U not containing x, the augmented set S ∪ {x} does not belong to U.

    Suppose S ∈ U (with x ∉ S) and S ∪ {x} ∈ U. If S and S ∪ {x} were in different families 𝒜 i and 𝒜 i', then S ⊆ S ∪ {x} would contradict strong incomparability; hence both belong to the same family 𝒜 i. By the blocking hypothesis on 𝒜 i, there exist j, k ≠ i and y such that {x, y} ∈ 𝒜 j and {x, y}ᶜ ∈ 𝒜 k. If y were in S, then {x, y} ⊆ S ∪ {x}, contradicting strong incomparability between 𝒜 j and 𝒜 i. Hence y ∉ S. But since neither x nor y is in S, we have S ⊆ {x, y}ᶜ, contradicting strong incomparability between 𝒜 i and 𝒜 k.

    lines 46–69

    uses mem_biUnion, subset_insert, mem_insert, mem_singleton, mem_insert_self, mem_insert_of_mem, mem_compl, not_or

      have hno : ∀ S ∈ U, x ∉ S → insert x S ∉ U := by
        intro S hS hxS hSx
        obtain ⟨i, _, hSi⟩ := mem_biUnion.mp hS
        obtain ⟨i', _, hSxi⟩ := mem_biUnion.mp hSx
        have heq : i = i' := by
          by_contra hne
          exact hinc i i' hne S hSi (insert x S) hSxi (subset_insert x S)
        subst i'
        obtain ⟨j, k, hji, hki, y, hw, hc⟩ := hblock i ⟨S, hSi⟩
        have hy : y ∉ S := by
          intro hyS
          have hsub : ({x,y} : Finset (Fin n)) ⊆ insert x S := by
            intro z hz
            simp only [mem_insert, mem_singleton] at hz
            rcases hz with rfl | rfl
            · exact mem_insert_self _ _
            · exact mem_insert_of_mem hyS
          exact hinc j i hji {x,y} hw (insert x S) hSxi hsub
        have hsub : S ⊆ ({x,y} : Finset (Fin n))ᶜ := by
          intro z hz
          rw [mem_compl]
          simp only [mem_insert, mem_singleton, not_or]
          exact ⟨fun hzx => hxS (hzx ▸ hz), fun hzy => hy (hzy ▸ hz)⟩
        exact hinc i k hki.symm S hSi ({x,y} : Finset (Fin n))ᶜ hc hsub
  9. The fiber overlap at coordinate x has cardinality 0.

    Any element in the intersection of {S ∈ U | x ∉ S} and {T \ {x} | T ∈ U, x ∈ T} would be a set S ∈ U with x ∉ S such that S ∪ {x} = T ∈ U. But the previous step showed no such pair can exist in U. Therefore, the intersection is empty and its cardinality is 0.

    lines 70–85

    uses card_eq_zero, eq_empty_iff_forall_notMem, mem_inter, mem_filter, mem_image, insert_erase

      have hover : ((U.filter (fun S => x ∉ S)) ∩
          ((U.filter (fun S => x ∈ S)).image (fun S => S.erase x))).card = 0 := by
        apply card_eq_zero.mpr
        rw [eq_empty_iff_forall_notMem]
        intro S hS
        obtain ⟨hP, hQ⟩ := mem_inter.mp hS
        have hSU : S ∈ U := (mem_filter.mp hP).1
        have hxS : x ∉ S := (mem_filter.mp hP).2
        obtain ⟨T, hT, hTS⟩ := mem_image.mp hQ
        have hTU : T ∈ U := (mem_filter.mp hT).1
        have hxT : x ∈ T := (mem_filter.mp hT).2
        have hTeq : T = insert x S := by
          have he := insert_erase hxT
          rw [hTS] at he
          exact he.symm
        exact hno S hSU hxS (hTeq ▸ hTU)
  10. The total size ∑ i, #(𝒜 i) is at most 2^(n-1) - 2.

    Applying the lemma op1370_zero_fiber_count to U and x with the facts that ∅, {x}, univ.erase x, univ ∉ U and that the fiber overlap is 0 yields #U ≤ 2^(n-1) - 2. Substituting #U = ∑ i, #(𝒜 i) completes the proof.

    lines 86–87

    uses op1370_zero_fiber_count

      have h := op1370_zero_fiber_count n hn U x hempty hx hV huniv hover
      rwa [hsum] at h
disjoint_left
Two finite sets are disjoint if and only if no element of the first belongs to the second.
Subset.refl
Every set is a subset of itself.
card_biUnion
The cardinality of a pairwise disjoint union of finite sets is the sum of their cardinalities.
mem_biUnion
An element belongs to a union of families if and only if it belongs to at least one family in the collection.
empty_subset
The empty set is a subset of every set.
subset_univ
Every set in a finite universe is a subset of the universal set.
mem_erase
An element belongs to s.erase b if and only if it is not equal to b and belongs to s.
mem_univ
Every element belongs to the universal set.
mem_compl
An element belongs to the complement of s if and only if it does not belong to s.
subset_insert
Any set s is a subset of insert a s.
mem_insert
An element belongs to insert b s if and only if it equals b or belongs to s.
mem_singleton
An element belongs to the singleton {a} if and only if it equals a.
mem_insert_self
An element a belongs to insert a s.
mem_insert_of_mem
If an element belongs to s, then it belongs to insert b s.
not_or
The negation of a disjunction is the conjunction of the negations: ¬(p ∨ q) ↔ ¬p ∧ ¬q.
card_eq_zero
A finite set has cardinality 0 if and only if it is empty.
eq_empty_iff_forall_notMem
A set is empty if and only if it contains no elements.
mem_inter
An element belongs to the intersection of two sets if and only if it belongs to both.
mem_filter
An element belongs to filter p s if and only if it belongs to s and satisfies predicate p.
mem_image
An element belongs to image f s if and only if it is the image of some element in s.
insert_erase
Reinserting an element into a set from which it was removed recovers the set, provided the element was originally in the set.
op1370_zero_fiber_count
For n ≥ 3, any family of subsets of Fin n that omits ∅, {x}, univ.erase x, and univ, and has zero fiber overlap at coordinate x, has size at most 2^(n-1) - 2.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem op1370_two_set_complement_block_bound (n t : ℕ) (hn : 3 ≤ n)    (𝒜 : Fin t → Finset (Finset (Fin n))) (hinc : strongly_incomparable 𝒜)    (x : Fin n)    (hblock : ∀ i : Fin t, (𝒜 i).Nonempty → ∃ j k : Fin t, j ≠ i ∧ k ≠ i ∧      ∃ y : Fin n, ({x, y} : Finset (Fin n)) ∈ 𝒜 j ∧ ({x, y} : Finset (Fin n))ᶜ ∈ 𝒜 k) :    ∑ i, (𝒜 i).card ≤ 2 ^ (n - 1) - 2 := by  open Finset in  classical  let U := univ.biUnion 𝒜  have hdisj : ∀ i j : Fin t, i ≠ j → Disjoint (𝒜 i) (𝒜 j) := by    intro i j hij    rw [disjoint_left]    intro S hSi hSj    exact hinc i j hij S hSi S hSj (Subset.refl S)  have hsum : U.card = ∑ i, (𝒜 i).card := by    dsimp [U]    rw [card_biUnion (fun i _ j _ hij => hdisj i j hij)]  have hempty : (∅ : Finset (Fin n)) ∉ U := by    intro h    obtain ⟨i, _, hi⟩ := mem_biUnion.mp h    obtain ⟨j, k, hji, hki, y, hw, hc⟩ := hblock i ⟨∅, hi⟩    exact hinc i j hji.symm ∅ hi {x, y} hw (empty_subset _)  have huniv : (univ : Finset (Fin n)) ∉ U := by    intro h    obtain ⟨i, _, hi⟩ := mem_biUnion.mp h    obtain ⟨j, k, hji, hki, y, hw, hc⟩ := hblock i ⟨univ, hi⟩    exact hinc j i hji {x, y} hw univ hi (subset_univ _)  have hx : ({x} : Finset (Fin n)) ∉ U := by    intro h    obtain ⟨i, _, hi⟩ := mem_biUnion.mp h    obtain ⟨j, k, hji, hki, y, hw, hc⟩ := hblock i ⟨{x}, hi⟩    have hsub : ({x} : Finset (Fin n)) ⊆ {x, y} := by simp    exact hinc i j hji.symm {x} hi {x, y} hw hsub  have hV : (univ.erase x : Finset (Fin n)) ∉ U := by    intro h    obtain ⟨i, _, hi⟩ := mem_biUnion.mp h    obtain ⟨j, k, hji, hki, y, hw, hc⟩ := hblock i ⟨univ.erase x, hi⟩    have hsub : ({x, y} : Finset (Fin n))ᶜ ⊆ univ.erase x := by      intro z hz      rw [mem_erase]      refine ⟨?_, mem_univ _⟩      intro hzx      subst z      exact (mem_compl.mp hz) (by simp)    exact hinc k i hki ({x,y} : Finset (Fin n))ᶜ hc (univ.erase x) hi hsub  have hno : ∀ S ∈ U, x ∉ S → insert x S ∉ U := by    intro S hS hxS hSx    obtain ⟨i, _, hSi⟩ := mem_biUnion.mp hS    obtain ⟨i', _, hSxi⟩ := mem_biUnion.mp hSx    have heq : i = i' := by      by_contra hne      exact hinc i i' hne S hSi (insert x S) hSxi (subset_insert x S)    subst i'    obtain ⟨j, k, hji, hki, y, hw, hc⟩ := hblock i ⟨S, hSi⟩    have hy : y ∉ S := by      intro hyS      have hsub : ({x,y} : Finset (Fin n)) ⊆ insert x S := by        intro z hz        simp only [mem_insert, mem_singleton] at hz        rcases hz with rfl | rfl        · exact mem_insert_self _ _        · exact mem_insert_of_mem hyS      exact hinc j i hji {x,y} hw (insert x S) hSxi hsub    have hsub : S ⊆ ({x,y} : Finset (Fin n))ᶜ := by      intro z hz      rw [mem_compl]      simp only [mem_insert, mem_singleton, not_or]      exact ⟨fun hzx => hxS (hzx ▸ hz), fun hzy => hy (hzy ▸ hz)⟩    exact hinc i k hki.symm S hSi ({x,y} : Finset (Fin n))ᶜ hc hsub  have hover : ((U.filter (fun S => x ∉ S)) ∩      ((U.filter (fun S => x ∈ S)).image (fun S => S.erase x))).card = 0 := by    apply card_eq_zero.mpr    rw [eq_empty_iff_forall_notMem]    intro S hS    obtain ⟨hP, hQ⟩ := mem_inter.mp hS    have hSU : S ∈ U := (mem_filter.mp hP).1    have hxS : x ∉ S := (mem_filter.mp hP).2    obtain ⟨T, hT, hTS⟩ := mem_image.mp hQ    have hTU : T ∈ U := (mem_filter.mp hT).1    have hxT : x ∈ T := (mem_filter.mp hT).2    have hTeq : T = insert x S := by      have he := insert_erase hxT      rw [hTS] at he      exact he.symm    exact hno S hSU hxS (hTeq ▸ hTU)  have h := op1370_zero_fiber_count n hn U x hempty hx hV huniv hover  rwa [hsum] at h
See it in the graphDiscuss this resultChallenge it