op_1370_private_element_bound
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 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.
- 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.
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).
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)
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).
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
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.
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⟩
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.
uses
erase_subsethave 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))
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.
uses
congrArghave 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
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|.
uses
card_image_of_injOn,insert_erase,card_filter_add_card_filter_nothave 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
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|.
uses
disjoint_iff_ne,subset_refl,card_biUnion,add_sum_erase,mem_univhave 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
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)|.
uses
insert_erase,op_1370_incomparable_strict_shatteringhave 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
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.
uses
card_compl,op_1370_shattered_capacityhave 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|.
- The strict shattering bound requires at least three families ($t \ge 3$) so that the remaining index set $I = \{1, \dots, t\} \setminus \{i\}$ has at least two elements, allowing the union $B$ to be split into two nonempty incomparable subfamilies.
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_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