op_1370_uncomplemented_strongly_incomparable_upper_bound
Theorem 1.7 of arXiv:2611.12199: for all natural numbers n and t, if π : Fin t β Finset (Finset (Fin n)) is a family such that each π i is uncomplemented and π is strongly incomparable, then β i : Fin t, (π i).card β€ 2 ^ (n - 1).
Statement
theorem op_1370_uncomplemented_strongly_incomparable_upper_bound (n t : β) (π : Fin t β Finset (Finset (Fin n))) (hunc : β i, is_uncomplemented (π i)) (hinc : strongly_incomparable π) : β i, (π i).card β€ 2 ^ (n - 1)- Formalizes
- arXiv:2611.12199 Theorem 1.7
- Verified
- 11 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_upper_bound_of_matrixLet n be a natural number. Suppose there are a field K, a matrix L with rows indexed by the subsets of Fin n and 2^(n-1) columns, and aβ¦
- hilton_strong_incomparability_matrixFor every natural number n there are a field K, a matrix L over K with rows indexed by the subsets of Fin n and 2^(n-1) columns, and aβ¦
Read back from the Lean
For all natural numbers $n$ and $t$, and any family $\mathcal{A} = (\mathcal{A}_i)_{i \in \mathrm{Fin}(t)}$ of collections of subsets of $\mathrm{Fin}(n)$, if: 1. for each $i \in \mathrm{Fin}(t)$, $\mathcal{A}_i$ is uncomplemented (i.e., no set in $\mathcal{A}_i$ has its complement in $\mathcal{A}_i$), and 2. $\mathcal{A}$ is strongly incomparable (i.e., for all distinct indices $i \neq j$, no set in $\mathcal{A}_i$ is a subset of a set in $\mathcal{A}_j$), then the sum of the cardinalities of all the collections, $\sum_{i \in \mathrm{Fin}(t)} |\mathcal{A}_i|$, is at most $2^{n - 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 theorem is proved by applying the general matrix-rank bound op_1370_upper_bound_of_matrix. That result bounds the sum of sizes of strongly incomparable uncomplemented families by the inner dimension of a matrix factorization that vanishes off comparable pairs and has invertible principal submatrices on uncomplemented families; hilton_strong_incomparability_matrix supplies exactly such a matrix of rank at most 2^(n-1).
β i, (π i).card β€ 2 ^ (n - 1)
Apply the matrix-rank upper bound theorem op_1370_upper_bound_of_matrix, supplying the matrix factorization provided by hilton_strong_incomparability_matrix n together with the hypotheses that each π i is uncomplemented and that π is strongly incomparable.
uses
op_1370_upper_bound_of_matrix,hilton_strong_incomparability_matrixexact op_1370_upper_bound_of_matrix n (hilton_strong_incomparability_matrix n) t π hunc hinc
op_1370_upper_bound_of_matrix- If there exists a factorization of a matrix over a field through dimension 2^(n-1) that vanishes on incomparable pairs of subsets and has invertible principal submatrices on all uncomplemented families, then any collection of strongly incomparable uncomplemented families has total size at most 2^(n-1).
hilton_strong_incomparability_matrix- For any n, there exists a field and a matrix factored through dimension 2^(n-1) that vanishes on incomparable pairs of subsets and whose principal submatrix indexed by any uncomplemented family is non-singular.
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 1.7 of arXiv:2611.12199: uncomplemented and strongly incomparable families have total size at most 2^(n-1). -/theorem op_1370_uncomplemented_strongly_incomparable_upper_bound (n t : β) (π : Fin t β Finset (Finset (Fin n))) (hunc : β i, is_uncomplemented (π i)) (hinc : strongly_incomparable π) : β i, (π i).card β€ 2 ^ (n - 1) := by exact op_1370_upper_bound_of_matrix n (hilton_strong_incomparability_matrix n) t π hunc hinc