op_1370_small_pair_bound
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 alli j : ιwithi ≠ 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.
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.
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_disjointclassical 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
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⌉.
uses
Finset.disjoint_left,subset_refl,Finset.card_union_of_disjointclassical 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
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)|.
uses
op_1370_small_family_shatterer_uncomplemented,op_1370_incomparable_strict_shatteringhave 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
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.
uses
Finset.mem_union.mphave 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⟩
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.
uses
Finset.mem_shatterer.mp,Finset.empty_subset,Finset.mem_compl,Finset.mem_inter.mprhave 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
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.
uses
Finset.disjoint_lefthave hdu : Disjoint H.shatterer (𝒜 2) := by rw [Finset.disjoint_left] intro S hS hS2 exact (hcross S hS).1 hS2
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.
uses
Finset.mem_union.mphave 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
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.
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_assochave 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.
- The Lean expression (n + 1) / 2 computes ⌈n/2⌉ using natural number floor division.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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