AFTD Auto-Formalizing Theoretical Domains

op_1370_low_vcdim_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 union of the others has VC dimension strictly less than ceil(n/2). Then the total size is at most 2^(n-1)-1. No uncomplementedness is required of the other families.

Statement

theorem op_1370_low_vcdim_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)) (hvc : ((Finset.univ.erase i).biUnion 𝒜).vcDim < (n + 1) / 2) : ∑ j, (𝒜 j).card ≤ 2 ^ (n - 1) - 1
Related work
Low-shattering-dimension partial case of arXiv:2611.12199, Conjecture 4.3; no uncomplementedness is needed outside the designated 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 all i j : ι with i ≠ 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_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 all natural numbers $n \ge 3$ and $t \ge 3$, and every collection $\mathcal{A} : \text{Fin } t \to \text{Finset}(\text{Finset}(\text{Fin } n))$ such that: 1. For every index $j \in \text{Fin } t$, the family $\mathcal{A}(j)$ is nonempty, 2. $\mathcal{A}$ is strongly incomparable (for all $j_1 \ne j_2$, no set in $\mathcal{A}(j_1)$ is a subset of any set in $\mathcal{A}(j_2)$), and for any index $i \in \text{Fin } t$ such that: 3. $\mathcal{A}(i)$ is uncomplemented (no set in $\mathcal{A}(i)$ has its complement in $\mathcal{A}(i)$), and 4. The VC-dimension of the union of all other families $\bigcup_{j \ne i} \mathcal{A}(j)$ is strictly less than $\lfloor (n + 1) / 2 \rfloor$ (via Lean natural number division), the sum of the cardinalities of all families $\sum_{j \in \text{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 upper bound on the total size of the families to op_1370_uncomplemented_shatterer_others_bound, which applies whenever one family is uncomplemented and the shatterer of the union of the remaining families is also uncomplemented. The key step is a helper lemma establishing that any family on Fin n with VC dimension strictly less than ⌈n/2⌉ has an uncomplemented shatterer: if both S and Sᶜ were shattered, both would have size at most the VC dimension, forcing n = |S| + |Sᶜ| ≤ 2 · vcDim < n, a contradiction. Applying this helper lemma to the union of the remaining families discharges the final condition.

  1. If both a set S and its complement Sᶜ are in the shatterer of F, then |S| ≤ vcDim(F) and |Sᶜ| ≤ vcDim(F).

    To show that the shatterer of F is uncomplemented, assume for contradiction that both S and Sᶜ are shattered by F. By definition, membership in the shatterer means the family shatters the set (Finset.mem_shatterer.mp), and any shattered set has cardinality bounded above by the VC dimension of F (card_le_vcDim).

    lines 6–9

    uses Finset.mem_shatterer.mp, card_le_vcDim

      classical
      intro S hS hSc
      have hs := (Finset.mem_shatterer.mp hS).card_le_vcDim
      have hsc := (Finset.mem_shatterer.mp hSc).card_le_vcDim
  2. The sum of the sizes of S and its complement Sᶜ is n.

    The subset S has size at most n = |Fin n| (Finset.card_le_univ, Fintype.card_fin). Rewriting |Sᶜ| as n - |S| (Finset.card_compl), integer arithmetic confirms |S| + (n - |S|) = n.

    lines 10–14

    uses Finset.card_le_univ, Finset.card_compl, Fintype.card_fin

      have hSn : S.card ≤ n := by simpa using Finset.card_le_univ S
      have hsum : S.card + (Sᶜ).card = n := by
        rw [Finset.card_compl]
        simp only [Fintype.card_fin]
        omega
  3. The shatterer of F is uncomplemented.

    Combining |S| ≤ vcDim(F) and |Sᶜ| ≤ vcDim(F) gives n = |S| + |Sᶜ| ≤ 2 · vcDim(F). But the assumption vcDim(F) < (n + 1) / 2 means 2 · vcDim(F) < n, a contradiction. Linear integer arithmetic (omega) derives False and closes the helper lemma.

    line 15

      omega
  4. The total cardinality satisfies ∑ j, |𝒜 j| ≤ 2^(n-1) - 1.

    We apply op_1370_uncomplemented_shatterer_others_bound, which yields the desired bound once the shatterer of the union of the remaining families ⋃_{j ≠ i} 𝒜 j is known to be uncomplemented. That condition is discharged directly by our helper lemma op1370_vc_shatterer_uncomp, since this union has VC dimension strictly less than (n + 1) / 2.

    lines 18–19

    uses op_1370_uncomplemented_shatterer_others_bound, op1370_vc_shatterer_uncomp

      apply op_1370_uncomplemented_shatterer_others_bound n t hn ht 𝒜 hne hinc i hunc
      exact op1370_vc_shatterer_uncomp n ((Finset.univ.erase i).biUnion 𝒜) hvc
Finset.mem_shatterer.mp
A set belongs to the shatterer of a family if and only if the family shatters that set.
card_le_vcDim
Any set shattered by a family has cardinality at most the VC dimension of that family.
Finset.card_le_univ
The cardinality of any finset of a finite type is at most the cardinality of the type.
Finset.card_compl
The cardinality of the complement of a subset s in a finite type is the cardinality of the ambient type minus |s|.
Fintype.card_fin
The cardinality of the finite type Fin n is n.
op_1370_uncomplemented_shatterer_others_bound
For at least three nonempty strongly incomparable families in Fin n with n ≥ 3, if one family is uncomplemented and the shatterer of the union of the remaining families is uncomplemented, the sum of all their sizes is at most 2^(n-1) - 1.
op1370_vc_shatterer_uncomp
If a family of subsets of Fin n has VC dimension strictly less than (n + 1) / 2, its shatterer is uncomplemented.

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

open Finsetset_option maxHeartbeats 1000000lemma op1370_vc_shatterer_uncomp (n : ℕ) (F : Finset (Finset (Fin n)))    (hvc : F.vcDim < (n + 1) / 2) : is_uncomplemented F.shatterer := by  classical  intro S hS hSc  have hs := (Finset.mem_shatterer.mp hS).card_le_vcDim  have hsc := (Finset.mem_shatterer.mp hSc).card_le_vcDim  have hSn : S.card ≤ n := by simpa using Finset.card_le_univ S  have hsum : S.card + (Sᶜ).card = n := by    rw [Finset.card_compl]    simp only [Fintype.card_fin]    omega  omegatheorem op_1370_low_vcdim_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)) (hvc : ((Finset.univ.erase i).biUnion 𝒜).vcDim < (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  exact op1370_vc_shatterer_uncomp n ((Finset.univ.erase i).biUnion 𝒜) hvc
See it in the graphDiscuss this resultChallenge it