AFTD Auto-Formalizing Theoretical Domains

op_1370_sparse_others_bound

theoremverifiedoriginal

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

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.

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

    line 2

    uses op_1370_uncomplemented_shatterer_others_bound

      apply op_1370_uncomplemented_shatterer_others_bound n t hn ht 𝒜 hne hinc i hunc
  2. The 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.

    lines 3–4

    uses op_1370_small_family_shatterer_uncomplemented, Finset.card_biUnion_le, lt_of_le_of_lt

      apply 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

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