AFTD Auto-Formalizing Theoretical Domains

op_1370_private_element_bound

theoremverifiedoriginal

Let at least three nonempty set families on an n-element ground set be mutually strongly incomparable. Suppose some element occurs in sets from at most one family, and that family is uncomplemented. Then the total size is at most 2^(n-1)-1. No uncomplementedness hypothesis is needed for the other families.

Statement

theorem op_1370_private_element_bound (n t : ℕ) (ht : 3 ≤ t) (𝒜 : Fin t → Finset (Finset (Fin n))) (hne : ∀ i, (𝒜 i).Nonempty) (hinc : strongly_incomparable 𝒜) (i : Fin t) (x : Fin n) (hunc : is_uncomplemented (𝒜 i)) (hx : ∀ j, j ≠ i → ∀ S ∈ 𝒜 j, x ∉ S) : ∑ j, (𝒜 j).card ≤ 2 ^ (n - 1) - 1
Related work
arXiv:2611.12199, Conjecture 4.3, for systems in which an element occurs in at most one family.
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 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.
  • op_1370_shattered_capacityFor 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…
Used by 3
  • op_1370_four_elements_boundAny at least three nonempty uncomplemented mutually strongly incomparable families on a four-element ground set have total size at most…
  • op_1370_private_absence_boundAt least three nonempty mutually strongly incomparable families have total size at most 2^(n-1)-1 if an element occurs in every set…
  • op_1370_no_private_reductionFor at least three nonempty, uncomplemented, mutually strongly incomparable families, the conjectured bound follows if it holds with a…

Read back from the Lean

For all natural numbers $n$ and $t$ with $3 \le t$, and any family $\mathcal{A} : \mathrm{Fin}\ t \to \mathrm{Finset}(\mathrm{Finset}(\mathrm{Fin}\ n))$ of $t$ collections of subsets of $\mathrm{Fin}\ n$, suppose: 1. Each collection $\mathcal{A}(j)$ is nonempty (for all $j \in \mathrm{Fin}\ t$). 2. $\mathcal{A}$ is strongly incomparable: for all $j_1 \ne j_2$ in $\mathrm{Fin}\ t$, no set $A \in \mathcal{A}(j_1)$ is a subset of any set $B \in \mathcal{A}(j_2)$. 3. There exists an index $i \in \mathrm{Fin}\ t$ and an element $x \in \mathrm{Fin}\ n$ such that: a. $\mathcal{A}(i)$ is uncomplemented (for every $A \in \mathcal{A}(i)$, the complement $A^c = \mathrm{Fin}\ n \setminus A$ is not in $\mathcal{A}(i)$). b. For all $j \ne i$ and every $S \in \mathcal{A}(j)$, $x \notin S$ (i.e., $x$ does not appear in any set belonging to any collection other than $\mathcal{A}(i)$). Then the total number of sets across all collections, $\sum_{j \in \mathrm{Fin}\ t} |\mathcal{A}(j)|$, is at most $2^{n-1} - 1$ (with subtraction in $\mathbb{N}$).

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

To bound the total size of t ≥ 3 strongly incomparable families, we isolate the private element x belonging only to sets in 𝒜 i and restrict to the (n-1)-element ground set V = {x}ᶜ. The family 𝒜 i is split into sets C avoiding x and sets D containing x with x deleted, while B is the union of all other families. Uncomplementedness of 𝒜 i and strong incomparability allow the capacity bound |C| + |D| + |shatterer(B)| ≤ 2^(n-1) to apply. Because t ≥ 3, the family B decomposes into at least two nonempty incomparable subfamilies, which strictly shatters more sets than its size (|B| < |shatterer(B)|), yielding the saving of 1 and the final bound 2^(n-1) - 1.

  1. Define the reduced ground set V = {x}ᶜ, the remaining index set I = univ \ {i}, the union of the other families B = ⋃_{j ∈ I} 𝒜 j, and the partition of 𝒜 i into sets C avoiding x and sets D containing x with x deleted.

    Working classically, we introduce the (n-1)-element universe V by removing the private element x. The families 𝒜 j for j ≠ i are combined into B. The special family 𝒜 i is split into C (sets not containing x) and D (sets containing x, projected into V by removing x).

    lines 5–10

      classical
      let V : Finset (Fin n) := {x}ᶜ
      let I : Finset (Fin t) := univ.erase i
      let B : Finset (Finset (Fin n)) := I.biUnion 𝒜
      let C : Finset (Finset (Fin n)) := (𝒜 i).filter (fun s => x ∉ s)
      let D : Finset (Finset (Fin n)) := ((𝒜 i).filter (fun s => x ∈ s)).image (erase · x)
  2. Every set in B, C, and D is a subset of V.

    By the private element hypothesis hx, no set in any 𝒜 j (j ≠ i) contains x, so every set in B is contained in V = {x}ᶜ. By definition, sets in C avoid x, so C ⊆ 𝒫(V). Sets in D are formed by deleting x, so they do not contain x and lie in 𝒫(V).

    lines 11–31

      have hB : ∀ S ∈ B, S ⊆ V := by
        intro S hS z hz
        obtain ⟨j, hj, hSj⟩ := mem_biUnion.mp hS
        have hji : j ≠ i := (mem_erase.mp hj).1
        simp only [V, mem_compl, mem_singleton]
        intro hzx
        subst z
        exact hx j hji S hSj hz
      have hC : ∀ S ∈ C, S ⊆ V := by
        intro S hS z hz
        have hnot := (mem_filter.mp hS).2
        simp only [V, mem_compl, mem_singleton]
        intro hzx
        subst z
        exact hnot hz
      have hD : ∀ S ∈ D, S ⊆ V := by
        intro S hS
        obtain ⟨T, hT, rfl⟩ := mem_image.mp hS
        intro z hz
        simp only [V, mem_compl, mem_singleton]
        exact (mem_erase.mp hz).1
  3. No set in C contains or is contained in any set in B.

    Any set c ∈ C belongs to 𝒜 i, and any b ∈ B belongs to 𝒜 j for some j ≠ i. By strong incomparability of the family collection 𝒜, neither c ⊆ b nor b ⊆ c can hold.

    lines 32–37

      have hCB : ∀ c ∈ C, ∀ b ∈ B, ¬ c ⊆ b ∧ ¬ b ⊆ c := by
        intro c hc b hb
        have hci := (mem_filter.mp hc).1
        obtain ⟨j, hj, hbj⟩ := mem_biUnion.mp hb
        have hji : j ≠ i := (mem_erase.mp hj).1
        exact ⟨hinc i j hji.symm c hci b hbj, hinc j i hji b hbj c hci⟩
  4. No set in B is a subset of any set in D.

    If b ⊆ d for some b ∈ 𝒜 j (j ≠ i) and d ∈ D, then d = s \ {x} for some s ∈ 𝒜 i. Since s \ {x} ⊆ s by erase_subset, transitivity implies b ⊆ s, which contradicts strong incomparability between 𝒜 j and 𝒜 i.

    lines 38–43

    uses erase_subset

      have hDB : ∀ d ∈ D, ∀ b ∈ B, ¬ b ⊆ d := by
        intro d hd b hb hbd
        obtain ⟨s, hs, rfl⟩ := mem_image.mp hd
        obtain ⟨j, hj, hbj⟩ := mem_biUnion.mp hb
        have hji : j ≠ i := (mem_erase.mp hj).1
        exact hinc j i hji b hbj s (mem_filter.mp hs).1 (hbd.trans (erase_subset x s))
  5. For every c ∈ C, the relative complement V \ c does not belong to D.

    If V \ c ∈ D, then V \ c = s \ {x} for some s ∈ 𝒜 i containing x. Because x ∉ c, testing elements shows that s is the exact complement cᶜ in the full universe Fin n (using congrArg). But then both c and cᶜ would belong to 𝒜 i, contradicting that 𝒜 i is uncomplemented.

    lines 44–59

    uses congrArg

      have hCD : ∀ c ∈ C, V \ c ∉ D := by
        intro c hc hd
        obtain ⟨s, hs, he⟩ := mem_image.mp hd
        have hsx : x ∈ s := (mem_filter.mp hs).2
        have hcx : x ∉ c := (mem_filter.mp hc).2
        have hsc : s = cᶜ := by
          ext z
          by_cases hzx : z = x
          · subst z
            simp [hsx, hcx]
          · have hz := congrArg (fun T : Finset (Fin n) => z ∈ T) he
            simp [V, hzx] at hz ⊢
            exact hz
        apply hunc c (mem_filter.mp hc).1
        rw [← hsc]
        exact (mem_filter.mp hs).1
  6. The cardinalities satisfy |C| + |D| = |𝒜 i|.

    Deleting x is injective on the subcollection of sets in 𝒜 i that contain x, because reinserting x via insert_erase recovers the original set; thus |D| = |{s ∈ 𝒜 i | x ∈ s}| by card_image_of_injOn. Since C = {s ∈ 𝒜 i | x ∉ s}, card_filter_add_card_filter_not shows that their cardinalities sum to |𝒜 i|.

    lines 60–70

    uses card_image_of_injOn, insert_erase, card_filter_add_card_filter_not

      have hDcard : D.card = ((𝒜 i).filter (fun s => x ∈ s)).card := by
        apply card_image_of_injOn
        intro s hs t ht he
        have hsx := (mem_filter.mp hs).2
        have htx := (mem_filter.mp ht).2
        have h := congrArg (insert x) he
        simpa [insert_erase hsx, insert_erase htx] using h
      have hCDcard : C.card + D.card = (𝒜 i).card := by
        have hh := card_filter_add_card_filter_not (s := 𝒜 i) (fun s => x ∈ s)
        change ((𝒜 i).filter (fun s => x ∈ s)).card + C.card = (𝒜 i).card at hh
        omega
  7. The families 𝒜 j for j ∈ I are pairwise disjoint, |B| = ∑_{j ∈ I} |𝒜 j|, and the total size across all t families is |𝒜 i| + |B|.

    If two distinct families 𝒜 j and 𝒜 k shared a set A, then A ⊆ A by subset_refl would violate strong incomparability; by disjoint_iff_ne they are disjoint. Hence |B| = ∑_{j ∈ I} |𝒜 j| by card_biUnion. Separating the index i from the full sum using add_sum_erase and mem_univ shows that the total sum equals |𝒜 i| + |B|.

    lines 71–83

    uses disjoint_iff_ne, subset_refl, card_biUnion, add_sum_erase, mem_univ

      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 B hB
        rintro rfl
        exact hinc j k hjk A hA A hB (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
  8. The union B shatters strictly more sets than its own cardinality: |B| < |shatterer(B)|.

    Since t ≥ 3, the remaining index set I contains at least two distinct elements j and k. We decompose B = 𝒜 j ∪ B' where B' = ⋃_{l ∈ I \ {j}} 𝒜 l using insert_erase. Both 𝒜 j and B' are nonempty (as 𝒜 k ⊆ B') and mutually incomparable. Applying op_1370_incomparable_strict_shattering to this union yields the strict inequality |B| < |shatterer(B)|.

    lines 84–105

    uses insert_erase, op_1370_incomparable_strict_shattering

      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
  9. The total size ∑_j |𝒜 j| is at most 2^(n-1) - 1.

    The complement V = {x}ᶜ has cardinality n - 1 by card_compl. The capacity bound op_1370_shattered_capacity applies to V, B, C, D to give |C| + |D| + |shatterer(B)| ≤ 2^(n-1). Since |C| + |D| = |𝒜 i| and |B| ≤ |shatterer(B)| - 1, linear arithmetic (omega) concludes that ∑_j |𝒜 j| = |𝒜 i| + |B| ≤ 2^(n-1) - 1.

    lines 106–109

    uses card_compl, op_1370_shattered_capacity

      have hV : V.card = n - 1 := by simp [V, card_compl]
      have hcapacity := op_1370_shattered_capacity V B C D hB hC hD hCB hDB hCD
      rw [hV] at hcapacity
      omega
erase_subset
Deleting an element from a finite set yields a subset of the original set.
congrArg
Applying a function to equal inputs produces equal outputs.
card_image_of_injOn
The image of a finite set under an injective map on that set has the same cardinality as the set.
insert_erase
Reinserting an element into a finite set from which it was removed recovers the original set.
card_filter_add_card_filter_not
The number of elements in a finite set satisfying a predicate plus the number not satisfying it equals the cardinality of the set.
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 pairwise disjoint union of finite sets is the sum of their individual cardinalities.
add_sum_erase
Splitting off an element from a sum over a finite set yields the term at that element plus the sum over the remaining elements.
mem_univ
Every element of a finite type belongs to the universal finset.
op_1370_incomparable_strict_shattering
The union of two nonempty, mutually incomparable families of sets strictly shatters more sets than the number of sets in the union.
card_compl
The cardinality of the complement of a subset of a finite type is the type's size minus the subset's size.
op_1370_shattered_capacity
For families B, C, D of subsets of V where C and B are mutually incomparable, no set in B is a subset of any set in D, and V \ c ∉ D for all c ∈ C, the sum |C| + |D| + |shatterer(B)| is at most 2^|V|.

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_private_element_bound (n t : ℕ) (ht : 3 ≤ t) (𝒜 : Fin t → Finset (Finset (Fin n))) (hne : ∀ i, (𝒜 i).Nonempty) (hinc : strongly_incomparable 𝒜) (i : Fin t) (x : Fin n) (hunc : is_uncomplemented (𝒜 i)) (hx : ∀ j, j ≠ i → ∀ S ∈ 𝒜 j, x ∉ S) : ∑ j, (𝒜 j).card ≤ 2 ^ (n - 1) - 1 := by  classical  let V : Finset (Fin n) := {x}ᶜ  let I : Finset (Fin t) := univ.erase i  let B : Finset (Finset (Fin n)) := I.biUnion 𝒜  let C : Finset (Finset (Fin n)) := (𝒜 i).filter (fun s => x ∉ s)  let D : Finset (Finset (Fin n)) := ((𝒜 i).filter (fun s => x ∈ s)).image (erase · x)  have hB : ∀ S ∈ B, S ⊆ V := by    intro S hS z hz    obtain ⟨j, hj, hSj⟩ := mem_biUnion.mp hS    have hji : j ≠ i := (mem_erase.mp hj).1    simp only [V, mem_compl, mem_singleton]    intro hzx    subst z    exact hx j hji S hSj hz  have hC : ∀ S ∈ C, S ⊆ V := by    intro S hS z hz    have hnot := (mem_filter.mp hS).2    simp only [V, mem_compl, mem_singleton]    intro hzx    subst z    exact hnot hz  have hD : ∀ S ∈ D, S ⊆ V := by    intro S hS    obtain ⟨T, hT, rfl⟩ := mem_image.mp hS    intro z hz    simp only [V, mem_compl, mem_singleton]    exact (mem_erase.mp hz).1  have hCB : ∀ c ∈ C, ∀ b ∈ B, ¬ c ⊆ b ∧ ¬ b ⊆ c := by    intro c hc b hb    have hci := (mem_filter.mp hc).1    obtain ⟨j, hj, hbj⟩ := mem_biUnion.mp hb    have hji : j ≠ i := (mem_erase.mp hj).1    exact ⟨hinc i j hji.symm c hci b hbj, hinc j i hji b hbj c hci⟩  have hDB : ∀ d ∈ D, ∀ b ∈ B, ¬ b ⊆ d := by    intro d hd b hb hbd    obtain ⟨s, hs, rfl⟩ := mem_image.mp hd    obtain ⟨j, hj, hbj⟩ := mem_biUnion.mp hb    have hji : j ≠ i := (mem_erase.mp hj).1    exact hinc j i hji b hbj s (mem_filter.mp hs).1 (hbd.trans (erase_subset x s))  have hCD : ∀ c ∈ C, V \ c ∉ D := by    intro c hc hd    obtain ⟨s, hs, he⟩ := mem_image.mp hd    have hsx : x ∈ s := (mem_filter.mp hs).2    have hcx : x ∉ c := (mem_filter.mp hc).2    have hsc : s = cᶜ := by      ext z      by_cases hzx : z = x      · subst z        simp [hsx, hcx]      · have hz := congrArg (fun T : Finset (Fin n) => z ∈ T) he        simp [V, hzx] at hz ⊢        exact hz    apply hunc c (mem_filter.mp hc).1    rw [← hsc]    exact (mem_filter.mp hs).1  have hDcard : D.card = ((𝒜 i).filter (fun s => x ∈ s)).card := by    apply card_image_of_injOn    intro s hs t ht he    have hsx := (mem_filter.mp hs).2    have htx := (mem_filter.mp ht).2    have h := congrArg (insert x) he    simpa [insert_erase hsx, insert_erase htx] using h  have hCDcard : C.card + D.card = (𝒜 i).card := by    have hh := card_filter_add_card_filter_not (s := 𝒜 i) (fun s => x ∈ s)    change ((𝒜 i).filter (fun s => x ∈ s)).card + C.card = (𝒜 i).card at hh    omega  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 B hB    rintro rfl    exact hinc j k hjk A hA A hB (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 hV : V.card = n - 1 := by simp [V, card_compl]  have hcapacity := op_1370_shattered_capacity V B C D hB hC hD hCB hDB hCD  rw [hV] at hcapacity  omega
See it in the graphDiscuss this resultChallenge it