AFTD Auto-Formalizing Theoretical Domains

op_1370_shattered_capacity

theoremverified

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|.

  1. 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}.

    lines 5–12

    uses card_powerset

      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
  2. 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.

    lines 13–16

      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)
  3. 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̄.

    lines 17–21

    uses image_subset_image

      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
  4. |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|.

    lines 22–33

    uses card_image_of_injOn, congrArg, Finset.sdiff_sdiff_eq_self

      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
  5. 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̄.

    lines 34–47

    uses filter_subset, sdiff_subset, disjoint_left

      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
  6. |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|.

    lines 48–49

    uses union_subset, card_union_of_disjoint, card_le_card

      have hcap := card_le_card (union_subset hDP (union_subset hH hCbarP))
      rw [card_union_of_disjoint hdis, hP] at hcap
  7. 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̄.

    lines 50–77

    uses empty_subset, notMem_empty, sdiff_subset, congrArg, Finset.sdiff_sdiff_eq_self

      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
  8. |B.shatterer| ≤ |H \ Q̄|.

    From the inclusion T̄ ⊆ H \ Q̄, card_le_card gives |T̄| ≤ |H \ Q̄|. Substituting |T̄| = |B.shatterer| yields the inequality.

    lines 78–79

    uses card_le_card

      have htcard := card_le_card hT
      rw [hTbar] at htcard
  9. |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.

    lines 80–84

    uses card_le_card, inter_subset_inter_left, card_union_add_card_inter, card_sdiff_add_card_inter

      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
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|.

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 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
See it in the graphDiscuss this resultChallenge it