op_1370_shattered_capacity
For set families B, C and D on a finite ground set V, assume each member of C is incomparable with every member of B, no member of D contains a member of B, and the complement within V of each member of C is absent from D. Then the cardinalities of C, D and the family shattered by B sum to at most 2^|V|.
Statement
theorem op_1370_shattered_capacity {α : Type*} [DecidableEq α] (V : Finset α) (B C D : Finset (Finset α)) (hB : ∀ S ∈ B, S ⊆ V) (hC : ∀ S ∈ C, S ⊆ V) (hD : ∀ S ∈ D, S ⊆ V) (hCB : ∀ c ∈ C, ∀ b ∈ B, ¬ c ⊆ b ∧ ¬ b ⊆ c) (hDB : ∀ d ∈ D, ∀ b ∈ B, ¬ b ⊆ d) (hCD : ∀ c ∈ C, V \ c ∉ D) : C.card + D.card + B.shatterer.card ≤ 2 ^ V.card
- Source
- Counting reduction for the private-element case of OP-1370.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- op_1370_private_element_boundLet at least three nonempty set families on an n-element ground set be mutually strongly incomparable. Suppose some element occurs in sets…
The proof, explained
We consider the powerset 𝒫(V) and two subfamilies: H (subsets containing some member of B) and Q (subsets incomparable with all members of B), together with the elementwise complement families C̄, Q̄, and T̄ for C, Q, and the shattered family T = B.shatterer. The hypotheses that no member of D contains any member of B and no complement of a member of C lies in D imply that D is disjoint from H ∪ C̄, so |D| + |H ∪ C̄| ≤ 2^|V|. By the definition of shattering, the complement of every shattered set contains some member of B disjoint from it yet cannot lie in Q̄, which shows T̄ ⊆ H \ Q̄ and thus |T| ≤ |H \ Q̄|. Finally, using C̄ ⊆ Q̄ and inclusion-exclusion on H with C̄ and Q̄, we deduce |C| + |T| ≤ |H ∪ C̄|, concluding that |C| + |D| + |T| ≤ 2^|V|.
Define the ambient powerset P = 𝒫(V) of size 2^|V|, the filter H of subsets containing a member of B, the family Q of subsets incomparable with every member of B, and their complement families C̄, Q̄, and T̄.
We let P = 𝒫(V), whose cardinality is 2^|V| by card_powerset. We define H as the family of subsets of V that contain at least one member of B, and Q as the family of subsets of V that are incomparable with all members of B. For any set family, we denote complementation relative to V with an overline, defining C̄ = {V \ c : c ∈ C}, Q̄ = {V \ q : q ∈ Q}, and T̄ = {V \ s : s ∈ B.shatterer}.
uses
card_powersetclassical let P := V.powerset let H := P.filter (fun S => ∃ b ∈ B, b ⊆ S) let Q := P.filter (fun S => ∀ b ∈ B, ¬ S ⊆ b ∧ ¬ b ⊆ S) let Cbar := C.image (V \ ·) let Qbar := Q.image (V \ ·) let Tbar := B.shatterer.image (V \ ·) have hP : P.card = 2 ^ V.card := card_powerset V
Every set shattered by B is a subset of the ground set V.
By the definition of shattering, any set s shattered by B has a superset in B. Since every member of B is a subset of V (hypothesis hB), transitivity of subset inclusion shows s ⊆ V.
have hshV : ∀ s ∈ B.shatterer, s ⊆ V := by intro s hs obtain ⟨b, hb, hsb⟩ := (mem_shatterer.mp hs).exists_superset exact hsb.trans (hB b hb)
C is contained in Q, and therefore C̄ ⊆ Q̄.
Every member c ∈ C is a subset of V (by hC) and is incomparable with every member of B (by hCB), which means c ∈ Q. Since C ⊆ Q, taking images under the complement map preserves inclusion (image_subset_image), yielding C̄ ⊆ Q̄.
uses
image_subset_imagehave hQ : C ⊆ Q := by intro c hc apply mem_filter.mpr exact ⟨mem_powerset.mpr (hC c hc), hCB c hc⟩ have hbar : Cbar ⊆ Qbar := image_subset_image hQ
|C̄| = |C| and |T̄| = |B.shatterer|.
The map s ↦ V \ s is injective on any collection of subsets of V, because taking the complement twice recovers the original set (Finset.sdiff_sdiff_eq_self). Since all members of C and all sets shattered by B are subsets of V, the map is injective on both families. By card_image_of_injOn and congrArg, |C̄| = |C| and |T̄| = |B.shatterer|.
uses
card_image_of_injOn,congrArg,Finset.sdiff_sdiff_eq_selfhave hCbar : Cbar.card = C.card := by apply card_image_of_injOn intro a ha b hb he have h := congrArg (fun s : Finset α => V \ s) he rw [Finset.sdiff_sdiff_eq_self (hC a ha), Finset.sdiff_sdiff_eq_self (hC b hb)] at h exact h have hTbar : Tbar.card = B.shatterer.card := by apply card_image_of_injOn intro a ha b hb he have h := congrArg (fun s : Finset α => V \ s) he rw [Finset.sdiff_sdiff_eq_self (hshV a ha), Finset.sdiff_sdiff_eq_self (hshV b hb)] at h exact h
The families H, C̄, and D are all subfamilies of P, and D is disjoint from H ∪ C̄.
By filter_subset and sdiff_subset, both H and C̄ consist of subsets of V, as does D by hD. To verify disjointness via disjoint_left, consider any d ∈ D: d cannot belong to H because no member of B is contained in d (hypothesis hDB), and d cannot belong to C̄ because the complement of no member of C belongs to D (hypothesis hCD). Thus D is disjoint from H ∪ C̄.
uses
filter_subset,sdiff_subset,disjoint_lefthave hH : H ⊆ P := filter_subset _ _ have hCbarP : Cbar ⊆ P := by intro s hs obtain ⟨c, hc, rfl⟩ := mem_image.mp hs exact mem_powerset.mpr (sdiff_subset) have hDP : D ⊆ P := by intro d hd; exact mem_powerset.mpr (hD d hd) have hdis : Disjoint D (H ∪ Cbar) := by rw [disjoint_left] intro d hd hm rcases mem_union.mp hm with hm | hm · obtain ⟨_, b, hb, hbd⟩ := mem_filter.mp hm exact hDB d hd b hb hbd · obtain ⟨c, hc, rfl⟩ := mem_image.mp hm exact hCD c hc hd
|D| + |H ∪ C̄| ≤ 2^|V|.
Because D and H ∪ C̄ are both subsets of P, their union D ∪ (H ∪ C̄) is a subset of P (union_subset). Since D and H ∪ C̄ are disjoint, the cardinality of their union is |D| + |H ∪ C̄| (card_union_of_disjoint). Applying monotonicity of cardinality (card_le_card) and |P| = 2^|V| yields |D| + |H ∪ C̄| ≤ 2^|V|.
uses
union_subset,card_union_of_disjoint,card_le_cardhave hcap := card_le_card (union_subset hDP (union_subset hH hCbarP)) rw [card_union_of_disjoint hdis, hP] at hcap
T̄ is a subfamily of H \ Q̄.
Let s ∈ T̄, so s = V \ t for some set t shattered by B. By definition of shattering applied to ∅ ⊆ t (empty_subset), there is some b₀ ∈ B with t ∩ b₀ = ∅, which via notMem_empty implies b₀ ⊆ V \ t = s, so s ∈ H. Furthermore, s ∉ Q̄: if s = V \ q for some q ∈ Q, double complementation (Finset.sdiff_sdiff_eq_self) would imply q = t, so t ∈ Q; but shattering applied to t ⊆ t provides a superset b₁ ∈ B of t, contradicting the incomparability requirement for members of Q. Hence s ∈ H \ Q̄.
uses
empty_subset,notMem_empty,sdiff_subset,congrArg,Finset.sdiff_sdiff_eq_selfhave hT : Tbar ⊆ H \ Qbar := by intro s hs obtain ⟨t, ht, rfl⟩ := mem_image.mp hs have htV := hshV t ht have htsh := mem_shatterer.mp ht obtain ⟨b1, hb1, htb1⟩ := htsh.exists_superset obtain ⟨b0, hb0, ht0⟩ := htsh (empty_subset t) have hb0sub : b0 ⊆ V \ t := by intro z hz refine mem_sdiff.mpr ⟨hB b0 hb0 hz, ?_⟩ intro hzt have hz0 : z ∈ t ∩ b0 := mem_inter.mpr ⟨hzt, hz⟩ rw [ht0] at hz0 exact notMem_empty _ hz0 apply mem_sdiff.mpr constructor · apply mem_filter.mpr exact ⟨mem_powerset.mpr sdiff_subset, ⟨b0, hb0, hb0sub⟩⟩ · intro hqbar obtain ⟨q, hq, he⟩ := mem_image.mp hqbar have hqV : q ⊆ V := mem_powerset.mp (mem_filter.mp hq).1 have hqt : q = t := by have eq := congrArg (fun s : Finset α => V \ s) he rw [Finset.sdiff_sdiff_eq_self hqV, Finset.sdiff_sdiff_eq_self htV] at eq exact eq have hqinc := (mem_filter.mp hq).2 b1 hb1 apply hqinc.1 simpa [hqt] using htb1
|B.shatterer| ≤ |H \ Q̄|.
From the inclusion T̄ ⊆ H \ Q̄, card_le_card gives |T̄| ≤ |H \ Q̄|. Substituting |T̄| = |B.shatterer| yields the inequality.
uses
card_le_cardhave htcard := card_le_card hT rw [hTbar] at htcard
|C| + |D| + |B.shatterer| ≤ 2^|V|. automation
Because C̄ ⊆ Q̄, intersection monotonicity (inter_subset_inter_left) implies |H ∩ C̄| ≤ |H ∩ Q̄| via card_le_card. Inclusion-exclusion (card_union_add_card_inter) gives |H ∪ C̄| + |H ∩ C̄| = |H| + |C|, while partitioning H (card_sdiff_add_card_inter) gives |H \ Q̄| + |H ∩ Q̄| = |H|. Combining these with |D| + |H ∪ C̄| ≤ 2^|V| and |B.shatterer| ≤ |H \ Q̄| ensures |C| + |B.shatterer| ≤ |H ∪ C̄|, and linear arithmetic (omega) closes the goal.
uses
card_le_card,inter_subset_inter_left,card_union_add_card_inter,card_sdiff_add_card_interhave hinter := card_le_card (inter_subset_inter_left (s := H) hbar) have hunion := card_union_add_card_inter H Cbar have hsplit := card_sdiff_add_card_inter H Qbar rw [hCbar] at hunion omega
card_powerset- The powerset of a finite set s has cardinality 2^|s|.
image_subset_image- Taking the image under a function preserves set inclusion.
card_image_of_injOn- The image of a finite set under a function injective on that set has the same cardinality as the set.
congrArg- Applying a function to both sides of an equality preserves the equality.
Finset.sdiff_sdiff_eq_self- For finite sets t ⊆ s, the double set difference s \ (s \ t) equals t.
filter_subset- Filtering a finite set by a predicate produces a subset of the original set.
sdiff_subset- The set difference s \ t is a subset of s.
disjoint_left- Two finite sets are disjoint if and only if no element of the first belongs to the second.
union_subset- If two sets are each subsets of a third, their union is also a subset of the third.
card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
card_le_card- If a finite set is a subset of another, its cardinality is less than or equal to that of the other.
empty_subset- The empty set is a subset of any set.
notMem_empty- No element belongs to the empty set.
inter_subset_inter_left- If t ⊆ u, then for any set s, s ∩ t ⊆ s ∩ u.
card_union_add_card_inter- For any two finite sets, the sum of the cardinalities of their union and intersection equals the sum of their individual cardinalities.
card_sdiff_add_card_inter- For any two finite sets s and t, |s \ t| + |s ∩ t| = |s|.
- The final step uses the `omega` decision procedure to perform linear integer arithmetic, combining the inclusion-exclusion equalities and subadditivity inequalities to bound the sum of cardinalities.
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 800000theorem op_1370_shattered_capacity {α : Type*} [DecidableEq α] (V : Finset α) (B C D : Finset (Finset α)) (hB : ∀ S ∈ B, S ⊆ V) (hC : ∀ S ∈ C, S ⊆ V) (hD : ∀ S ∈ D, S ⊆ V) (hCB : ∀ c ∈ C, ∀ b ∈ B, ¬ c ⊆ b ∧ ¬ b ⊆ c) (hDB : ∀ d ∈ D, ∀ b ∈ B, ¬ b ⊆ d) (hCD : ∀ c ∈ C, V \ c ∉ D) : C.card + D.card + B.shatterer.card ≤ 2 ^ V.card := by classical let P := V.powerset let H := P.filter (fun S => ∃ b ∈ B, b ⊆ S) let Q := P.filter (fun S => ∀ b ∈ B, ¬ S ⊆ b ∧ ¬ b ⊆ S) let Cbar := C.image (V \ ·) let Qbar := Q.image (V \ ·) let Tbar := B.shatterer.image (V \ ·) have hP : P.card = 2 ^ V.card := card_powerset V have hshV : ∀ s ∈ B.shatterer, s ⊆ V := by intro s hs obtain ⟨b, hb, hsb⟩ := (mem_shatterer.mp hs).exists_superset exact hsb.trans (hB b hb) have hQ : C ⊆ Q := by intro c hc apply mem_filter.mpr exact ⟨mem_powerset.mpr (hC c hc), hCB c hc⟩ have hbar : Cbar ⊆ Qbar := image_subset_image hQ have hCbar : Cbar.card = C.card := by apply card_image_of_injOn intro a ha b hb he have h := congrArg (fun s : Finset α => V \ s) he rw [Finset.sdiff_sdiff_eq_self (hC a ha), Finset.sdiff_sdiff_eq_self (hC b hb)] at h exact h have hTbar : Tbar.card = B.shatterer.card := by apply card_image_of_injOn intro a ha b hb he have h := congrArg (fun s : Finset α => V \ s) he rw [Finset.sdiff_sdiff_eq_self (hshV a ha), Finset.sdiff_sdiff_eq_self (hshV b hb)] at h exact h have hH : H ⊆ P := filter_subset _ _ have hCbarP : Cbar ⊆ P := by intro s hs obtain ⟨c, hc, rfl⟩ := mem_image.mp hs exact mem_powerset.mpr (sdiff_subset) have hDP : D ⊆ P := by intro d hd; exact mem_powerset.mpr (hD d hd) have hdis : Disjoint D (H ∪ Cbar) := by rw [disjoint_left] intro d hd hm rcases mem_union.mp hm with hm | hm · obtain ⟨_, b, hb, hbd⟩ := mem_filter.mp hm exact hDB d hd b hb hbd · obtain ⟨c, hc, rfl⟩ := mem_image.mp hm exact hCD c hc hd have hcap := card_le_card (union_subset hDP (union_subset hH hCbarP)) rw [card_union_of_disjoint hdis, hP] at hcap have hT : Tbar ⊆ H \ Qbar := by intro s hs obtain ⟨t, ht, rfl⟩ := mem_image.mp hs have htV := hshV t ht have htsh := mem_shatterer.mp ht obtain ⟨b1, hb1, htb1⟩ := htsh.exists_superset obtain ⟨b0, hb0, ht0⟩ := htsh (empty_subset t) have hb0sub : b0 ⊆ V \ t := by intro z hz refine mem_sdiff.mpr ⟨hB b0 hb0 hz, ?_⟩ intro hzt have hz0 : z ∈ t ∩ b0 := mem_inter.mpr ⟨hzt, hz⟩ rw [ht0] at hz0 exact notMem_empty _ hz0 apply mem_sdiff.mpr constructor · apply mem_filter.mpr exact ⟨mem_powerset.mpr sdiff_subset, ⟨b0, hb0, hb0sub⟩⟩ · intro hqbar obtain ⟨q, hq, he⟩ := mem_image.mp hqbar have hqV : q ⊆ V := mem_powerset.mp (mem_filter.mp hq).1 have hqt : q = t := by have eq := congrArg (fun s : Finset α => V \ s) he rw [Finset.sdiff_sdiff_eq_self hqV, Finset.sdiff_sdiff_eq_self htV] at eq exact eq have hqinc := (mem_filter.mp hq).2 b1 hb1 apply hqinc.1 simpa [hqt] using htb1 have htcard := card_le_card hT rw [hTbar] at htcard have hinter := card_le_card (inter_subset_inter_left (s := H) hbar) have hunion := card_union_add_card_inter H Cbar have hsplit := card_sdiff_add_card_inter H Qbar rw [hCbar] at hunion omega