AFTD Auto-Formalizing Theoretical Domains

op_1370_small_pair_bound

theoremverifiedoriginal

For three nonempty strongly incomparable families on Fin n with n at least three, if the last family is uncomplemented and the first two together have fewer than 2^ceil(n/2) sets, then their total size is at most 2^(n-1)-1. The first two families need not be uncomplemented.

Statement

theorem op_1370_small_pair_bound (n : ℕ) (hn : 3 ≤ n) (𝒜 : Fin 3 → Finset (Finset (Fin n))) (hne : ∀ i, (𝒜 i).Nonempty) (hinc : strongly_incomparable 𝒜) (hunc : is_uncomplemented (𝒜 2)) (hsmall : (𝒜 0).card + (𝒜 1).card < 2 ^ ((n + 1) / 2)) : ∑ i, (𝒜 i).card ≤ 2 ^ (n - 1) - 1
Related work
Sparse-pair case of arXiv:2611.12199, Conjecture 4.3; the first two families need not be uncomplemented.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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…
  • op_1370_incomparable_strict_shatteringThe union of two nonempty mutually strongly incomparable finite set families shatters strictly more sets than it contains.
  • op_1370_small_family_shatterer_uncomplementedIf a family of subsets of Fin n has fewer than 2^ceil(n/2) members, then its family of shattered sets contains no complementary pair.

Read back from the Lean

For any natural number $n \ge 3$, and any family $\mathcal{A} = (\mathcal{A}_0, \mathcal{A}_1, \mathcal{A}_2)$ of three families of subsets of $\mathrm{Fin}(n)$ (i.e. $\mathcal{A} : \mathrm{Fin}(3) \to \mathrm{Finset}(\mathrm{Finset}(\mathrm{Fin}(n)))$): if 1. each $\mathcal{A}_i$ is nonempty (for $i \in \{0, 1, 2\}$); 2. $\mathcal{A}$ is strongly incomparable: for all $i \neq j$ in $\{0, 1, 2\}$, no set $A \in \mathcal{A}_i$ is a subset of any set $B \in \mathcal{A}_j$; 3. $\mathcal{A}_2$ is uncomplemented: for every $A \in \mathcal{A}_2$, its complement $A^c = \mathrm{Fin}(n) \setminus A$ is not in $\mathcal{A}_2$; and 4. $|\mathcal{A}_0| + |\mathcal{A}_1| < 2^{\lfloor (n+1)/2 \rfloor}$; then the total number of sets across all three families satisfies $\sum_{i \in \mathrm{Fin}(3)} |\mathcal{A}_i| \le 2^{n - 1} - 1$.

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 argument bounds the total size of the three families by replacing the union H = 𝒜 0 ∪ 𝒜 1 with its shatterer. Because 𝒜 0 and 𝒜 1 are nonempty and mutually incomparable, a strict shattering inequality ensures that |H| < |shatterer(H)|. The small size of H implies that its shatterer is uncomplemented, and strong incomparability prevents any set in the shatterer or its complement from belonging to 𝒜 2. Consequently, shatterer(H) and 𝒜 2 are disjoint, and their union is an uncomplemented family on {0, …, n - 1}, which therefore has size at most 2^(n - 1). The strict inequality |H| < |shatterer(H)| then sharpens the sum |𝒜 0| + |𝒜 1| + |𝒜 2| to at most 2^(n - 1) - 1.

  1. Every uncomplemented family F of subsets of {0, …, n - 1} satisfies 2|F| ≤ 2^n.

    Because F is uncomplemented, no set and its complement can both belong to F, so F is disjoint from its image under complementation Fᶜ = {Sᶜ : S ∈ F}. Complementation is an injective map, so |Fᶜ| = |F|. The disjoint union F ∪ Fᶜ is contained in the full power set of size 2^n, giving |F| + |Fᶜ| = 2|F| ≤ 2^n.

    lines 6–17

    uses Finset.disjoint_left, Finset.mem_image.mp, Finset.card_image_of_injective, compl_injective, Finset.card_le_card, Finset.subset_univ, Finset.card_union_of_disjoint

      classical
      have hd : Disjoint F (F.image compl) := by
        rw [Finset.disjoint_left]
        intro s hs hc
        obtain ⟨t, ht, rfl⟩ := Finset.mem_image.mp hc
        exact hu t ht hs
      have hi : (F.image compl).card = F.card := Finset.card_image_of_injective _ compl_injective
      have hc : (F ∪ F.image compl).card ≤ (Finset.univ : Finset (Finset (Fin n))).card :=
        Finset.card_le_card (Finset.subset_univ _)
      rw [Finset.card_union_of_disjoint hd, hi] at hc
      have hh : F.card + F.card ≤ 2 ^ n := by simpa using hc
      omega
  2. The union H = 𝒜 0 ∪ 𝒜 1 is disjoint, so |H| = |𝒜 0| + |𝒜 1| < 2^⌈n/2⌉.

    By strong incomparability, no set in 𝒜 0 is a subset of any set in 𝒜 1, and conversely. Thus 𝒜 0 and 𝒜 1 cannot share any element A (since A ⊆ A), meaning they are disjoint. Therefore |H| = |𝒜 0| + |𝒜 1|, and the smallness assumption implies |H| < 2^⌈n/2⌉.

    lines 20–30

    uses Finset.disjoint_left, subset_refl, Finset.card_union_of_disjoint

      classical
      let H := 𝒜 0 ∪ 𝒜 1
      have hab : ∀ A ∈ 𝒜 0, ∀ B ∈ 𝒜 1, ¬ A ⊆ B ∧ ¬ B ⊆ A := by
        intro A hA B hB
        exact ⟨hinc 0 1 (by decide) A hA B hB, hinc 1 0 (by decide) B hB A hA⟩
      have hd01 : Disjoint (𝒜 0) (𝒜 1) := by
        rw [Finset.disjoint_left]
        intro A hA hB
        exact (hab A hA A hB).1 (subset_refl A)
      have hHcard : H.card = (𝒜 0).card + (𝒜 1).card := Finset.card_union_of_disjoint hd01
      have hHsmall : H.card < 2 ^ ((n + 1) / 2) := by simpa [hHcard] using hsmall
  3. The shatterer of H is uncomplemented and satisfies the strict inequality |H| < |shatterer(H)|.

    Because |H| < 2^⌈n/2⌉, the small-family theorem ensures that shatterer(H) is uncomplemented. Furthermore, because 𝒜 0 and 𝒜 1 are nonempty and mutually incomparable, the strict shattering inequality gives |H| < |shatterer(H)|.

    lines 31–33

    uses op_1370_small_family_shatterer_uncomplemented, op_1370_incomparable_strict_shattering

      have hU : is_uncomplemented H.shatterer := op_1370_small_family_shatterer_uncomplemented n H hHsmall
      have hstrict : H.card < H.shatterer.card :=
        op_1370_incomparable_strict_shattering (𝒜 0) (𝒜 1) (hne 0) (hne 1) hab
  4. No set in H contains or is contained in any set in 𝒜 2.

    Every set A ∈ H belongs to either 𝒜 0 or 𝒜 1. In either case, the strong incomparability assumption implies that A neither contains nor is contained in any B ∈ 𝒜 2.

    lines 34–38

    uses Finset.mem_union.mp

      have hinc2 : ∀ A ∈ H, ∀ B ∈ 𝒜 2, ¬ A ⊆ B ∧ ¬ B ⊆ A := by
        intro A hA B hB
        rcases Finset.mem_union.mp hA with hA | hA
        · exact ⟨hinc 0 2 (by decide) A hA B hB, hinc 2 0 (by decide) B hB A hA⟩
        · exact ⟨hinc 1 2 (by decide) A hA B hB, hinc 2 1 (by decide) B hB A hA⟩
  5. For every set S in the shatterer of H, neither S nor its complement Sᶜ belongs to 𝒜 2.

    By definition of shattering, H induces all traces on S. In particular, S itself is a trace, so there exists T ∈ H with S ⊆ T; if S ∈ 𝒜 2, this would contradict strong incomparability between H and 𝒜 2. Similarly, ∅ is a trace on S, so there exists W ∈ H with S ∩ W = ∅, which means W ⊆ Sᶜ; if Sᶜ ∈ 𝒜 2, this would again contradict incomparability.

    lines 39–55

    uses Finset.mem_shatterer.mp, Finset.empty_subset, Finset.mem_compl, Finset.mem_inter.mpr

      have hcross : ∀ S ∈ H.shatterer, S ∉ 𝒜 2 ∧ Sᶜ ∉ 𝒜 2 := by
        intro S hS
        have hs := Finset.mem_shatterer.mp hS
        obtain ⟨T, hT, hST⟩ := hs.exists_superset
        constructor
        · intro hSA
          exact (hinc2 T hT S hSA).2 hST
        · intro hSc
          obtain ⟨W, hW, hSW⟩ := hs (Finset.empty_subset S)
          have hwc : W ⊆ Sᶜ := by
            intro x hx
            simp only [Finset.mem_compl]
            intro hxs
            have : x ∈ S ∩ W := Finset.mem_inter.mpr ⟨hxs, hx⟩
            rw [hSW] at this
            simpa using this
          exact (hinc2 W hW Sᶜ hSc).1 hwc
  6. The shatterer of H and 𝒜 2 are disjoint.

    Since no set in the shatterer of H belongs to 𝒜 2, the intersection of the two families is empty.

    lines 56–59

    uses Finset.disjoint_left

      have hdu : Disjoint H.shatterer (𝒜 2) := by
        rw [Finset.disjoint_left]
        intro S hS hS2
        exact (hcross S hS).1 hS2
  7. The union shatterer(H) ∪ 𝒜 2 is uncomplemented.

    Suppose for contradiction that both S and Sᶜ belong to shatterer(H) ∪ 𝒜 2. They cannot both belong to shatterer(H) because it is uncomplemented, nor can they both belong to 𝒜 2 because 𝒜 2 is uncomplemented. They cannot be split between the two families because no set in shatterer(H) has its complement in 𝒜 2.

    lines 60–69

    uses Finset.mem_union.mp

      have hu : is_uncomplemented (H.shatterer ∪ 𝒜 2) := by
        intro S hS hSc
        rcases Finset.mem_union.mp hS with hS | hS
        · rcases Finset.mem_union.mp hSc with hSc | hSc
          · exact hU S hS hSc
          · exact (hcross S hS).2 hSc
        · rcases Finset.mem_union.mp hSc with hSc | hSc
          · have h := (hcross Sᶜ hSc).2
            exact h (by simpa using hS)
          · exact hunc S hS hSc
  8. The total size ∑ i, |𝒜 i| is at most 2^(n - 1) - 1.

    Applying the uncomplemented bound to the disjoint union shatterer(H) ∪ 𝒜 2 gives 2(|shatterer(H)| + |𝒜 2|) ≤ 2^n = 2 · 2^(n - 1), so |shatterer(H)| + |𝒜 2| ≤ 2^(n - 1). Because |H| < |shatterer(H)| strictly, we obtain |H| + |𝒜 2| ≤ 2^(n - 1) - 1. Since ∑ i, |𝒜 i| = |H| + |𝒜 2|, the result follows by integer arithmetic.

    lines 70–79

    uses op1370_local_uncomp_card, Finset.card_union_of_disjoint, Nat.exists_eq_succ_of_ne_zero, pow_succ, Nat.mul_comm, Fin.sum_univ_succ, Nat.add_assoc

      have hsize := op1370_local_uncomp_card n (H.shatterer ∪ 𝒜 2) hu
      rw [Finset.card_union_of_disjoint hdu] at hsize
      have hn1 : 1 ≤ n := by omega
      have hpow : 2 ^ n = 2 * 2 ^ (n - 1) := by
        obtain ⟨k, rfl⟩ := Nat.exists_eq_succ_of_ne_zero (by omega : n ≠ 0)
        simp [pow_succ, Nat.mul_comm]
      rw [hpow] at hsize
      have hsum : (∑ i, (𝒜 i).card) = (𝒜 0).card + (𝒜 1).card + (𝒜 2).card := by
        simp [Fin.sum_univ_succ, Nat.add_assoc]
      omega
Finset.disjoint_left
Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.mem_image.mp
An element belongs to the image of a set under a function if and only if it is the image of some element of that set.
Finset.card_image_of_injective
The image of a finite set under an injective map has the same cardinality as the original set.
compl_injective
Set complementation is an injective map.
Finset.card_le_card
A subset of a finite set has cardinality less than or equal to the containing set.
Finset.subset_univ
Every finite set of elements of a finite type is a subset of the universal set.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
subset_refl
Every set is a subset of itself.
op_1370_small_family_shatterer_uncomplemented
If a family of subsets of Fin n has cardinality strictly less than 2^⌈n/2⌉, its shatterer is uncomplemented.
op_1370_incomparable_strict_shattering
For any two nonempty mutually incomparable families of sets, the shatterer of their union is strictly larger than the union itself.
Finset.mem_union.mp
An element in the union of two sets belongs to the first set or the second set.
Finset.mem_shatterer.mp
An element belongs to the shatterer of a family if and only if the family shatters it.
Finset.empty_subset
The empty set is a subset of every set.
Finset.mem_compl
An element belongs to the complement of a set if and only if it does not belong to the set.
Finset.mem_inter.mpr
An element belongs to the intersection of two sets if and only if it belongs to both sets.
op1370_local_uncomp_card
Any uncomplemented family of subsets of Fin n satisfies 2 * |F| ≤ 2^n.
Nat.exists_eq_succ_of_ne_zero
Every non-zero natural number is the successor of some natural number.
pow_succ
Raising a base to n + 1 equals multiplying the base raised to n by the base.
Nat.mul_comm
Multiplication of natural numbers is commutative.
Fin.sum_univ_succ
A sum over Fin (n + 1) splits into the term at 0 and the sum over the remaining terms.
Nat.add_assoc
Addition of natural numbers is associative.

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

open Finsetset_option maxHeartbeats 1000000lemma op1370_local_uncomp_card (n : ℕ) (F : Finset (Finset (Fin n)))    (hu : is_uncomplemented F) : 2 * F.card ≤ 2 ^ n := by  classical  have hd : Disjoint F (F.image compl) := by    rw [Finset.disjoint_left]    intro s hs hc    obtain ⟨t, ht, rfl⟩ := Finset.mem_image.mp hc    exact hu t ht hs  have hi : (F.image compl).card = F.card := Finset.card_image_of_injective _ compl_injective  have hc : (F ∪ F.image compl).card ≤ (Finset.univ : Finset (Finset (Fin n))).card :=    Finset.card_le_card (Finset.subset_univ _)  rw [Finset.card_union_of_disjoint hd, hi] at hc  have hh : F.card + F.card ≤ 2 ^ n := by simpa using hc  omegatheorem op_1370_small_pair_bound (n : ℕ) (hn : 3 ≤ n) (𝒜 : Fin 3 → Finset (Finset (Fin n))) (hne : ∀ i, (𝒜 i).Nonempty) (hinc : strongly_incomparable 𝒜) (hunc : is_uncomplemented (𝒜 2)) (hsmall : (𝒜 0).card + (𝒜 1).card < 2 ^ ((n + 1) / 2)) : ∑ i, (𝒜 i).card ≤ 2 ^ (n - 1) - 1 := by  classical  let H := 𝒜 0 ∪ 𝒜 1  have hab : ∀ A ∈ 𝒜 0, ∀ B ∈ 𝒜 1, ¬ A ⊆ B ∧ ¬ B ⊆ A := by    intro A hA B hB    exact ⟨hinc 0 1 (by decide) A hA B hB, hinc 1 0 (by decide) B hB A hA⟩  have hd01 : Disjoint (𝒜 0) (𝒜 1) := by    rw [Finset.disjoint_left]    intro A hA hB    exact (hab A hA A hB).1 (subset_refl A)  have hHcard : H.card = (𝒜 0).card + (𝒜 1).card := Finset.card_union_of_disjoint hd01  have hHsmall : H.card < 2 ^ ((n + 1) / 2) := by simpa [hHcard] using hsmall  have hU : is_uncomplemented H.shatterer := op_1370_small_family_shatterer_uncomplemented n H hHsmall  have hstrict : H.card < H.shatterer.card :=    op_1370_incomparable_strict_shattering (𝒜 0) (𝒜 1) (hne 0) (hne 1) hab  have hinc2 : ∀ A ∈ H, ∀ B ∈ 𝒜 2, ¬ A ⊆ B ∧ ¬ B ⊆ A := by    intro A hA B hB    rcases Finset.mem_union.mp hA with hA | hA    · exact ⟨hinc 0 2 (by decide) A hA B hB, hinc 2 0 (by decide) B hB A hA⟩    · exact ⟨hinc 1 2 (by decide) A hA B hB, hinc 2 1 (by decide) B hB A hA⟩  have hcross : ∀ S ∈ H.shatterer, S ∉ 𝒜 2 ∧ Sᶜ ∉ 𝒜 2 := by    intro S hS    have hs := Finset.mem_shatterer.mp hS    obtain ⟨T, hT, hST⟩ := hs.exists_superset    constructor    · intro hSA      exact (hinc2 T hT S hSA).2 hST    · intro hSc      obtain ⟨W, hW, hSW⟩ := hs (Finset.empty_subset S)      have hwc : W ⊆ Sᶜ := by        intro x hx        simp only [Finset.mem_compl]        intro hxs        have : x ∈ S ∩ W := Finset.mem_inter.mpr ⟨hxs, hx⟩        rw [hSW] at this        simpa using this      exact (hinc2 W hW Sᶜ hSc).1 hwc  have hdu : Disjoint H.shatterer (𝒜 2) := by    rw [Finset.disjoint_left]    intro S hS hS2    exact (hcross S hS).1 hS2  have hu : is_uncomplemented (H.shatterer ∪ 𝒜 2) := by    intro S hS hSc    rcases Finset.mem_union.mp hS with hS | hS    · rcases Finset.mem_union.mp hSc with hSc | hSc      · exact hU S hS hSc      · exact (hcross S hS).2 hSc    · rcases Finset.mem_union.mp hSc with hSc | hSc      · have h := (hcross Sᶜ hSc).2        exact h (by simpa using hS)      · exact hunc S hS hSc  have hsize := op1370_local_uncomp_card n (H.shatterer ∪ 𝒜 2) hu  rw [Finset.card_union_of_disjoint hdu] at hsize  have hn1 : 1 ≤ n := by omega  have hpow : 2 ^ n = 2 * 2 ^ (n - 1) := by    obtain ⟨k, rfl⟩ := Nat.exists_eq_succ_of_ne_zero (by omega : n ≠ 0)    simp [pow_succ, Nat.mul_comm]  rw [hpow] at hsize  have hsum : (∑ i, (𝒜 i).card) = (𝒜 0).card + (𝒜 1).card + (𝒜 2).card := by    simp [Fin.sum_univ_succ, Nat.add_assoc]  omega
See it in the graphDiscuss this resultChallenge it