op_1370_sparse_others_bound
For at least three nonempty mutually strongly incomparable families of subsets of Fin n, with n at least three, suppose one designated family is uncomplemented and the total size of all the other families is less than 2^ceil(n/2). Then the total size is at most 2^(n-1)-1. No uncomplementedness of the other families is required.
Statement
theorem op_1370_sparse_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)) (hsmall : (∑ j ∈ Finset.univ.erase i, (𝒜 j).card) < 2 ^ ((n + 1) / 2)) : ∑ j, (𝒜 j).card ≤ 2 ^ (n - 1) - 1- Related work
- Sparse-other-families case of arXiv:2611.12199, Conjecture 4.3; no uncomplementedness is needed outside the designated family.
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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_small_family_shatterer_uncomplementedIf a family of subsets of Fin n has fewer than 2^ceil(n/2) members, then its family of shattered sets contains no complementary pair.
- op_1370_uncomplemented_shatterer_others_boundFor at least three nonempty mutually strongly incomparable families on Fin n, with n at least three, suppose a designated family is…
Read back from the Lean
For any natural numbers $n \ge 3$ and $t \ge 3$, and any family $\mathcal{A}$ of $t$ collections of subsets of $\mathrm{Fin}(n)$ (indexed by $\mathrm{Fin}(t)$) such that: 1. Each collection $\mathcal{A}(j)$ is nonempty, 2. $\mathcal{A}$ is strongly incomparable, and for any index $i \in \mathrm{Fin}(t)$ such that: 3. $\mathcal{A}(i)$ is uncomplemented, and 4. The sum of the cardinalities of all other collections $\sum_{j \ne i} |\mathcal{A}(j)|$ is strictly less than $2^{\lfloor (n + 1) / 2 \rfloor}$, the total number of sets across all collections $\sum_{j \in \mathrm{Fin}(t)} |\mathcal{A}(j)|$ is at most $2^{n - 1} - 1$.
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
The proof reduces the overall cardinality bound to showing that the shatterer of the union of the remaining families ⋃_{j ≠ i} 𝒜_j is uncomplemented, using the known result op_1370_uncomplemented_shatterer_others_bound. That shatterer is then shown to be uncomplemented via op_1370_small_family_shatterer_uncomplemented, which applies whenever a family has size strictly below 2^⌈n/2⌉. Finally, the union bound combines with the hypothesis on the sum of the remaining families' sizes to confirm this size threshold.
It suffices to show that the shatterer of the union of all other families, ⋃_{j ≠ i} 𝒜_j, is uncomplemented.
We invoke op_1370_uncomplemented_shatterer_others_bound, which establishes the total size bound ∑_j |𝒜_j| ≤ 2^(n - 1) - 1 under the existing hypotheses (n, t ≥ 3, families are nonempty and strongly incomparable, and 𝒜_i is uncomplemented) provided that the shatterer of the union of the other families is uncomplemented.
uses
op_1370_uncomplemented_shatterer_others_boundapply op_1370_uncomplemented_shatterer_others_bound n t hn ht 𝒜 hne hinc i huncThe shatterer of ⋃_{j ≠ i} 𝒜_j is uncomplemented.
Applying op_1370_small_family_shatterer_uncomplemented reduces this to verifying that |⋃_{j ≠ i} 𝒜_j| < 2^((n + 1) / 2). By the union bound Finset.card_biUnion_le, |⋃_{j ≠ i} 𝒜_j| ≤ ∑_{j ≠ i} |𝒜_j|, and by assumption hsmall, that sum is strictly less than 2^((n + 1) / 2). Combining these via lt_of_le_of_lt finishes the step.
uses
op_1370_small_family_shatterer_uncomplemented,Finset.card_biUnion_le,lt_of_le_of_ltapply op_1370_small_family_shatterer_uncomplemented exact lt_of_le_of_lt Finset.card_biUnion_le hsmall
op_1370_uncomplemented_shatterer_others_bound- For at least three nonempty mutually strongly incomparable families on a ground set of size at least three, if one family is uncomplemented and the shatterer of the union of the remaining families is also uncomplemented, then the sum of sizes of all families is at most 2^(n - 1) - 1.
op_1370_small_family_shatterer_uncomplemented- Any family of subsets of an n-element ground set with cardinality strictly less than 2^⌈n/2⌉ has an uncomplemented shatterer.
lt_of_le_of_lt- If a ≤ b and b < c, then a < c in a preorder.
Finset.card_biUnion_le- The cardinality of a union of finite sets is at most the sum of their individual cardinalities (the union bound).
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.
theorem op_1370_sparse_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)) (hsmall : (∑ j ∈ Finset.univ.erase i, (𝒜 j).card) < 2 ^ ((n + 1) / 2)) : ∑ j, (𝒜 j).card ≤ 2 ^ (n - 1) - 1 := by apply op_1370_uncomplemented_shatterer_others_bound n t hn ht 𝒜 hne hinc i hunc apply op_1370_small_family_shatterer_uncomplemented exact lt_of_le_of_lt Finset.card_biUnion_le hsmall