AFTD Auto-Formalizing Theoretical Domains

op_1370_uncomplemented_strongly_incomparable_upper_bound

theoremverifiedformalization

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 all i j : ΞΉ with i β‰  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).

  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.

    line 3

    uses op_1370_upper_bound_of_matrix, hilton_strong_incomparability_matrix

      exact 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

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