AFTD Auto-Formalizing Theoretical Domains

op_1370_uncomplemented_shatterer_others_bound

theoremverified

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

  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.

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

    lines 20–30

    uses disjoint_iff_ne, subset_refl, card_biUnion

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

    lines 31–35

    uses add_sum_erase, mem_univ

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

    lines 36–49

    uses insert_erase

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

    lines 50–57

    uses op_1370_incomparable_strict_shattering

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

    lines 58–63

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

    lines 64–84

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

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

    lines 85–94

    uses Finset.mem_union.mp

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

    lines 95–101

    uses op1370_vc_uncomp_card, Finset.card_union_of_disjoint, Nat.exists_eq_succ_of_ne_zero, pow_succ, Nat.mul_comm

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

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