op_1370_uncomplemented_shatterer_others_bound
For at least three nonempty mutually strongly incomparable families on Fin n, with n at least three, suppose a designated family is uncomplemented and the shattered-set family of the union of the others is also uncomplemented. Then their total size is at most 2^(n-1)-1. No uncomplementedness is needed for the individual other families.
Statement
theorem op_1370_uncomplemented_shatterer_others_bound (n t : ℕ) (hn : 3 ≤ n) (ht : 3 ≤ t) (𝒜 : Fin t → Finset (Finset (Fin n))) (hne : ∀ i, (𝒜 i).Nonempty) (hinc : strongly_incomparable 𝒜) (i : Fin t) (hunc : is_uncomplemented (𝒜 i)) (hSh0 : is_uncomplemented ((Finset.univ.erase i).biUnion 𝒜).shatterer) : ∑ j, (𝒜 j).card ≤ 2 ^ (n - 1) - 1- Source
- Reusable shattering criterion for arXiv:2611.12199, Conjecture 4.3.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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.
- Used by 2
- op_1370_sparse_others_boundFor at least three nonempty mutually strongly incomparable families of subsets of Fin n, with n at least three, suppose one designated…
- op_1370_low_vcdim_others_boundFor at least three nonempty mutually strongly incomparable families of subsets of Fin n, with n at least three, suppose one designated…
The proof, explained
The proof bounds the total size of t strongly incomparable families 𝒜_1, ..., 𝒜_t on Fin n by isolating a designated uncomplemented family 𝒜_i and setting B = ⋃_{j ≠ i} 𝒜_j. Because t ≥ 3, B decomposes into at least two incomparable nonempty subfamilies, so strict shattering gives |B| < |shatterer(B)|. Strong incomparability ensures that neither any shattered set nor its complement can belong to 𝒜_i, so shatterer(B) and 𝒜_i are disjoint and their union is uncomplemented. Applying the uncomplemented family bound gives |shatterer(B)| + |𝒜_i| ≤ 2^(n-1), and combining this with the strict inequality |B| < |shatterer(B)| yields ∑_j |𝒜_j| ≤ 2^(n-1) - 1.
An uncomplemented family F on Fin n has size at most 2^(n-1), so 2|F| ≤ 2^n. automation
If F is uncomplemented, no set in F has its complement in F, which means F is disjoint from its image under complementation Fᶜ = {sᶜ | s ∈ F}. Since complementation is injective, |Fᶜ| = |F|. The union F ∪ Fᶜ is a subset of the full power set of Fin n (size 2^n), so |F| + |F| = |F ∪ Fᶜ| ≤ 2^n, which gives 2|F| ≤ 2^n by linear arithmetic.
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 B = ⋃_{j ≠ i} 𝒜_j is the disjoint union of the families 𝒜_j for j ≠ i, so |B| = ∑_{j ≠ i} |𝒜_j|.
Let I = Fin t \ {i} and B = ⋃_{j ∈ I} 𝒜_j. For any distinct j, k ∈ I, the families 𝒜_j and 𝒜_k are disjoint: if they shared a set A, then A ⊆ A would contradict strong incomparability between 𝒜_j and 𝒜_k. Because the families are pairwise disjoint, the cardinality of their union B is the sum of their individual cardinalities.
uses
disjoint_iff_ne,subset_refl,card_biUnionclassical let I := (Finset.univ : Finset (Fin t)).erase i let B : Finset (Finset (Fin n)) := I.biUnion 𝒜 have hdisj : (↑I : Set (Fin t)).PairwiseDisjoint 𝒜 := by intro j hj k hk hjk change Disjoint (𝒜 j) (𝒜 k) rw [disjoint_iff_ne] intro A hA C hC rintro rfl exact hinc j k hjk A hA A hC (subset_refl A) have hBcard : B.card = ∑ j ∈ I, (𝒜 j).card := card_biUnion hdisj
The total size ∑_j |𝒜_j| equals |𝒜_i| + |B|.
Splitting the sum over all indices into the term for i and the sum over the remaining indices I expresses the total size as |𝒜_i| + ∑_{j ∈ I} |𝒜_j|. Substituting the cardinality of B gives |𝒜_i| + |B|.
uses
add_sum_erase,mem_univhave hsum : (∑ j, (𝒜 j).card) = (𝒜 i).card + B.card := by have hh := add_sum_erase (univ : Finset (Fin t)) (fun j => (𝒜 j).card) (mem_univ i) change (𝒜 i).card + ∑ j ∈ I, (𝒜 j).card = _ at hh rw [← hBcard] at hh exact hh.symm
The index set I has at least two elements, allowing B to be decomposed as 𝒜_j ∪ B' for some j ∈ I with both 𝒜_j and B' nonempty.
Since t ≥ 3, |I| = t - 1 ≥ 2 > 1, so there exist distinct indices j, k ∈ I. Removing j from I leaves a set of indices J = I \ {j} that contains k. Decomposing B as 𝒜_j ∪ B', where B' = ⋃_{l ∈ J} 𝒜_l, the family B' is nonempty because it contains the nonempty family 𝒜_k.
uses
insert_erasehave hI : 1 < I.card := by have : I.card = t - 1 := by simp [I] omega obtain ⟨j, hj, k, hk, hjk⟩ := one_lt_card.mp hI let J := I.erase j let B' : Finset (Finset (Fin n)) := J.biUnion 𝒜 have hBsplit : B = 𝒜 j ∪ B' := by calc B = (insert j (I.erase j)).biUnion 𝒜 := by rw [insert_erase hj] _ = 𝒜 j ∪ B' := by simp [B', J] have hB' : B'.Nonempty := by obtain ⟨S, hS⟩ := hne k refine ⟨S, mem_biUnion.mpr ⟨k, ?_, hS⟩⟩ exact mem_erase.mpr ⟨hjk.symm, hk⟩
The shatterer of B has strictly greater cardinality than B: |B| < |shatterer(B)|.
For any A ∈ 𝒜_j and T ∈ B', T belongs to some 𝒜_k with k ≠ j. By strong incomparability between distinct families, neither set is a subset of the other. Thus B = 𝒜_j ∪ B' is the union of two nonempty, mutually incomparable families. Applying the strict shattering theorem for incomparable families (op_1370_incomparable_strict_shattering), the shatterer of B is strictly larger than B.
uses
op_1370_incomparable_strict_shatteringhave hcross : ∀ A ∈ 𝒜 j, ∀ T ∈ B', ¬ A ⊆ T ∧ ¬ T ⊆ A := by intro A hA T hT obtain ⟨k, hk, hTk⟩ := mem_biUnion.mp hT have hkj : k ≠ j := (mem_erase.mp hk).1 exact ⟨hinc j k hkj.symm A hA T hTk, hinc k j hkj T hTk A hA⟩ have hstrict : B.card < B.shatterer.card := by rw [hBsplit] exact op_1370_incomparable_strict_shattering (𝒜 j) B' (hne j) hB' hcross
No set in B is comparable by inclusion to any set in 𝒜_i, and the shatterer of B is uncomplemented.
The shatterer of B is uncomplemented by assumption. Furthermore, since every set in B belongs to some 𝒜_j with j ≠ i, strong incomparability between 𝒜_j and 𝒜_i implies that for any A ∈ B and C ∈ 𝒜_i, neither A ⊆ C nor C ⊆ A holds.
have hSh : is_uncomplemented B.shatterer := hSh0 have hinc2 : ∀ A ∈ B, ∀ C ∈ 𝒜 i, ¬ A ⊆ C ∧ ¬ C ⊆ A := by intro A hA C hC obtain ⟨j, hj, hAj⟩ := mem_biUnion.mp hA have hji : j ≠ i := (mem_erase.mp hj).1 exact ⟨hinc j i hji A hAj C hC, hinc i j hji.symm C hC A hAj⟩
No set S in the shatterer of B, nor its complement Sᶜ, belongs to 𝒜_i; hence shatterer(B) and 𝒜_i are disjoint.
Let S be shattered by B. Shattering provides an element T ∈ B with S ⊆ T; if S were in 𝒜_i, this would contradict the incomparability of T ∈ B and S ∈ 𝒜_i, so S ∉ 𝒜_i. Shattering also provides an element W ∈ B with S ∩ W = ∅, which implies W ⊆ Sᶜ; if Sᶜ were in 𝒜_i, this would contradict the incomparability of W ∈ B and Sᶜ ∈ 𝒜_i, so Sᶜ ∉ 𝒜_i. In particular, shatterer(B) and 𝒜_i have no elements in common.
uses
Finset.mem_shatterer.mp,Finset.empty_subset,Finset.mem_compl,Finset.mem_inter.mpr,Finset.disjoint_lefthave hblocked : ∀ S ∈ B.shatterer, S ∉ 𝒜 i ∧ Sᶜ ∉ 𝒜 i := 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 B.shatterer (𝒜 i) := by rw [Finset.disjoint_left] intro S hS hSi exact (hblocked S hS).1 hSi
The union shatterer(B) ∪ 𝒜_i is uncomplemented.
Suppose for contradiction that S and Sᶜ both belong to shatterer(B) ∪ 𝒜_i. By case analysis: both being in shatterer(B) contradicts uncomplementedness of the shatterer; both being in 𝒜_i contradicts uncomplementedness of 𝒜_i; and one being in shatterer(B) while the other is in 𝒜_i contradicts the previous step that no shattered set or complement belongs to 𝒜_i.
uses
Finset.mem_union.mphave hu : is_uncomplemented (B.shatterer ∪ 𝒜 i) := by intro S hS hSc rcases Finset.mem_union.mp hS with hS | hS · rcases Finset.mem_union.mp hSc with hSc | hSc · exact hSh S hS hSc · exact (hblocked S hS).2 hSc · rcases Finset.mem_union.mp hSc with hSc | hSc · have h := (hblocked Sᶜ hSc).2 exact h (by simpa using hS) · exact hunc S hS hSc
The total size ∑_j |𝒜_j| is at most 2^(n-1) - 1. automation
Applying the uncomplemented size bound lemma (op1370_vc_uncomp_card) to the uncomplemented union shatterer(B) ∪ 𝒜_i, and using that the two sets are disjoint, yields 2(|shatterer(B)| + |𝒜_i|) ≤ 2^n. Since n ≥ 3, 2^n = 2 · 2^(n-1), so |shatterer(B)| + |𝒜_i| ≤ 2^(n-1). Since |B| < |shatterer(B)|, we have |B| ≤ |shatterer(B)| - 1, and the total size ∑_j |𝒜_j| = |𝒜_i| + |B| ≤ |𝒜_i| + |shatterer(B)| - 1 ≤ 2^(n-1) - 1. Linear integer arithmetic closes the goal.
uses
op1370_vc_uncomp_card,Finset.card_union_of_disjoint,Nat.exists_eq_succ_of_ne_zero,pow_succ,Nat.mul_commhave hsize := op1370_vc_uncomp_card n (B.shatterer ∪ 𝒜 i) hu rw [Finset.card_union_of_disjoint hdu] at hsize have hpow : 2 ^ n = 2 * 2 ^ (n - 1) := by obtain ⟨r, rfl⟩ := Nat.exists_eq_succ_of_ne_zero (by omega : n ≠ 0) simp [pow_succ, Nat.mul_comm] rw [hpow] at hsize 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- If an element belongs to the image of a set under a function, it is the image of some element of that set.
Finset.card_image_of_injective- The image of a finite set under an injective function has the same cardinality as the original set.
compl_injective- Complementation on a Boolean algebra is an injective function.
Finset.card_le_card- A subset of a finite set has cardinality at most that of the ambient set.
Finset.subset_univ- Every finite set of elements of a finite type is a subset of the universal finite set.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
disjoint_iff_ne- Two finite sets are disjoint if and only if no element of the first equals any element of the second.
subset_refl- Every set is a subset of itself.
card_biUnion- The cardinality of a union of pairwise disjoint finite sets is the sum of their individual cardinalities.
add_sum_erase- The sum of a function over a finite set equals its value at an element plus the sum over the set with that element removed.
mem_univ- Every element of a finite type belongs to the universal finite set.
insert_erase- Reinserting an element into a finite set from which it was removed recovers the original set.
op_1370_incomparable_strict_shattering- The union of two nonempty, mutually incomparable families has strictly smaller cardinality than its shatterer.
Finset.mem_shatterer.mp- If a set belongs to the shatterer of a family, then the family shatters that set.
Finset.empty_subset- The empty set is a subset of every finite set.
Finset.mem_compl- An element belongs to the complement of a subset of a finite universe if and only if it does not belong to the subset.
Finset.mem_inter.mpr- If an element belongs to both sets, it belongs to their intersection.
Finset.mem_union.mp- An element of a union of two sets belongs to at least one of the sets.
op1370_vc_uncomp_card- An uncomplemented family of subsets on an n-element set has size at most 2^(n-1).
Nat.exists_eq_succ_of_ne_zero- Every nonzero natural number is the successor of some natural number.
pow_succ- Raising a base to the successor power equals the base to that power times the base.
Nat.mul_comm- Multiplication of natural numbers is commutative.
- The proof begins with a helper lemma (op1370_vc_uncomp_card) bounding the size of any uncomplemented family on Fin n by 2^(n-1). The main theorem then uses omega for linear integer arithmetic, combining strict shattering (|B| < |shatterer(B)|) with this bound to reach the strict 2^(n-1) - 1 bound.
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_vc_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_uncomplemented_shatterer_others_bound (n t : ℕ) (hn : 3 ≤ n) (ht : 3 ≤ t) (𝒜 : Fin t → Finset (Finset (Fin n))) (hne : ∀ i, (𝒜 i).Nonempty) (hinc : strongly_incomparable 𝒜) (i : Fin t) (hunc : is_uncomplemented (𝒜 i)) (hSh0 : is_uncomplemented ((Finset.univ.erase i).biUnion 𝒜).shatterer) : ∑ j, (𝒜 j).card ≤ 2 ^ (n - 1) - 1 := by classical let I := (Finset.univ : Finset (Fin t)).erase i let B : Finset (Finset (Fin n)) := I.biUnion 𝒜 have hdisj : (↑I : Set (Fin t)).PairwiseDisjoint 𝒜 := by intro j hj k hk hjk change Disjoint (𝒜 j) (𝒜 k) rw [disjoint_iff_ne] intro A hA C hC rintro rfl exact hinc j k hjk A hA A hC (subset_refl A) have hBcard : B.card = ∑ j ∈ I, (𝒜 j).card := card_biUnion hdisj have hsum : (∑ j, (𝒜 j).card) = (𝒜 i).card + B.card := by have hh := add_sum_erase (univ : Finset (Fin t)) (fun j => (𝒜 j).card) (mem_univ i) change (𝒜 i).card + ∑ j ∈ I, (𝒜 j).card = _ at hh rw [← hBcard] at hh exact hh.symm have hI : 1 < I.card := by have : I.card = t - 1 := by simp [I] omega obtain ⟨j, hj, k, hk, hjk⟩ := one_lt_card.mp hI let J := I.erase j let B' : Finset (Finset (Fin n)) := J.biUnion 𝒜 have hBsplit : B = 𝒜 j ∪ B' := by calc B = (insert j (I.erase j)).biUnion 𝒜 := by rw [insert_erase hj] _ = 𝒜 j ∪ B' := by simp [B', J] have hB' : B'.Nonempty := by obtain ⟨S, hS⟩ := hne k refine ⟨S, mem_biUnion.mpr ⟨k, ?_, hS⟩⟩ exact mem_erase.mpr ⟨hjk.symm, hk⟩ have hcross : ∀ A ∈ 𝒜 j, ∀ T ∈ B', ¬ A ⊆ T ∧ ¬ T ⊆ A := by intro A hA T hT obtain ⟨k, hk, hTk⟩ := mem_biUnion.mp hT have hkj : k ≠ j := (mem_erase.mp hk).1 exact ⟨hinc j k hkj.symm A hA T hTk, hinc k j hkj T hTk A hA⟩ have hstrict : B.card < B.shatterer.card := by rw [hBsplit] exact op_1370_incomparable_strict_shattering (𝒜 j) B' (hne j) hB' hcross have hSh : is_uncomplemented B.shatterer := hSh0 have hinc2 : ∀ A ∈ B, ∀ C ∈ 𝒜 i, ¬ A ⊆ C ∧ ¬ C ⊆ A := by intro A hA C hC obtain ⟨j, hj, hAj⟩ := mem_biUnion.mp hA have hji : j ≠ i := (mem_erase.mp hj).1 exact ⟨hinc j i hji A hAj C hC, hinc i j hji.symm C hC A hAj⟩ have hblocked : ∀ S ∈ B.shatterer, S ∉ 𝒜 i ∧ Sᶜ ∉ 𝒜 i := 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 B.shatterer (𝒜 i) := by rw [Finset.disjoint_left] intro S hS hSi exact (hblocked S hS).1 hSi have hu : is_uncomplemented (B.shatterer ∪ 𝒜 i) := by intro S hS hSc rcases Finset.mem_union.mp hS with hS | hS · rcases Finset.mem_union.mp hSc with hSc | hSc · exact hSh S hS hSc · exact (hblocked S hS).2 hSc · rcases Finset.mem_union.mp hSc with hSc | hSc · have h := (hblocked Sᶜ hSc).2 exact h (by simpa using hS) · exact hunc S hS hSc have hsize := op1370_vc_uncomp_card n (B.shatterer ∪ 𝒜 i) hu rw [Finset.card_union_of_disjoint hdu] at hsize have hpow : 2 ^ n = 2 * 2 ^ (n - 1) := by obtain ⟨r, rfl⟩ := Nat.exists_eq_succ_of_ne_zero (by omega : n ≠ 0) simp [pow_succ, Nat.mul_comm] rw [hpow] at hsize omega