AFTD Auto-Formalizing Theoretical Domains

op_1370_small_family_shatterer_uncomplemented

theoremverified

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

Statement

theorem op_1370_small_family_shatterer_uncomplemented (n : ℕ) (F : Finset (Finset (Fin n))) (hsmall : F.card < 2 ^ ((n + 1) / 2)) : is_uncomplemented F.shatterer
Source
Trace-counting reduction for arXiv:2611.12199, Conjecture 4.3.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • is_uncomplementedA family of subsets of a finite set is uncomplemented if no set and its complement both belong to the family.
Used by 2
  • op_1370_small_pair_boundFor three nonempty strongly incomparable families on Fin n with n at least three, if the last family is uncomplemented and the first two…
  • op_1370_sparse_others_boundFor at least three nonempty mutually strongly incomparable families of subsets of Fin n, with n at least three, suppose one designated…

The proof, explained

The theorem is proved by contradiction: if the family of shattered sets contained a complementary pair S and Sᶜ, then both S and Sᶜ would be shattered by F. For any shattered set, the projections of F onto it must cover all its subsets, which forces |F| ≥ 2^|S| and |F| ≥ 2^|Sᶜ|. Since |S| + |Sᶜ| = n, at least one of |S| or |Sᶜ| must have size at least ⌈n/2⌉ = (n + 1) / 2, which implies |F| ≥ 2^((n + 1) / 2), contradicting the cardinality assumption on F.

  1. If S is in the shatterer of F, then 2^|S| ≤ |F|.

    By definition of shattering, the image of F under intersection with S equals the power set of S. Since the cardinality of an image is at most the cardinality of F, and the power set of S has cardinality 2^|S|, we obtain 2^|S| ≤ |F|.

    lines 6–10

    uses Finset.shatters_iff.mp, Finset.mem_shatterer.mp, Finset.card_image_le, Finset.card_powerset

      have hs : F.image (fun T => S ∩ T) = S.powerset :=
        Finset.shatters_iff.mp (Finset.mem_shatterer.mp hS)
      have h := Finset.card_image_le (s := F) (f := fun T => S ∩ T)
      rw [hs, Finset.card_powerset] at h
      exact h
  2. Assuming for contradiction that S and Sᶜ are both shattered by F, we have 2^|S| ≤ |F| and 2^|Sᶜ| ≤ |F|.

    Suppose for contradiction that there is a set S such that both S and its complement Sᶜ are in the shatterer of F. Applying the helper lemma to S and Sᶜ gives 2^|S| ≤ |F| and 2^|Sᶜ| ≤ |F|.

    lines 13–16

    uses op1370_local_shattered_card_lower

      classical
      intro S hS hSc
      have hs := op1370_local_shattered_card_lower n F S hS
      have hsc := op1370_local_shattered_card_lower n F Sᶜ hSc
  3. |S| ≤ n and |S| + |Sᶜ| = n.

    Since S is a subset of Fin n, its cardinality is at most n. The complement formula gives |Sᶜ| = n - |S|, so |S| + |Sᶜ| = n.

    lines 17–21

    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
  4. In the case where |S| ≥ (n + 1) / 2, we reach a contradiction. automation

    If |S| ≥ (n + 1) / 2, then 2^((n + 1) / 2) ≤ 2^|S| by monotonicity of powers of 2. Combining this with 2^|S| ≤ |F| contradicts the hypothesis |F| < 2^((n + 1) / 2). Linear integer arithmetic closes the goal.

    lines 22–24

      by_cases hle : (n + 1) / 2 ≤ S.card
      · have hp : 2 ^ ((n + 1) / 2) ≤ 2 ^ S.card := by gcongr <;> omega
        omega
  5. In the case where |S| < (n + 1) / 2, we have |Sᶜ| ≥ (n + 1) / 2, which also leads to a contradiction. automation

    Since |S| + |Sᶜ| = n, if |S| < (n + 1) / 2, then |Sᶜ| ≥ (n + 1) / 2. By monotonicity of exponentiation, 2^((n + 1) / 2) ≤ 2^|Sᶜ| ≤ |F|, which again contradicts |F| < 2^((n + 1) / 2). Linear integer arithmetic closes the goal.

    lines 25–27

      · have hle' : (n + 1) / 2 ≤ (Sᶜ).card := by omega
        have hp : 2 ^ ((n + 1) / 2) ≤ 2 ^ (Sᶜ).card := by gcongr <;> omega
        omega
Finset.shatters_iff.mp
If a set S is shattered by a family F, the projections of F onto S form the power set of S.
Finset.mem_shatterer.mp
A set S is in the shatterer of F if and only if F shatters S.
Finset.card_image_le
The cardinality of the image of a finite set is at most the cardinality of the domain set.
Finset.card_powerset
The power set of a finite set S has cardinality 2^|S|.
op1370_local_shattered_card_lower
If S is shattered by F, then 2^|S| ≤ |F|.
Finset.card_le_univ
The cardinality of any subset of a finite type is at most the cardinality of the type.
Finset.card_compl
The cardinality of the complement of a subset is the cardinality of the ambient type minus the subset's cardinality.
Fintype.card_fin
The type Fin n has cardinality n.

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_local_shattered_card_lower (n : ℕ) (F : Finset (Finset (Fin n)))    (S : Finset (Fin n)) (hS : S ∈ F.shatterer) : 2 ^ S.card ≤ F.card := by  have hs : F.image (fun T => S ∩ T) = S.powerset :=    Finset.shatters_iff.mp (Finset.mem_shatterer.mp hS)  have h := Finset.card_image_le (s := F) (f := fun T => S ∩ T)  rw [hs, Finset.card_powerset] at h  exact htheorem op_1370_small_family_shatterer_uncomplemented (n : ℕ) (F : Finset (Finset (Fin n))) (hsmall : F.card < 2 ^ ((n + 1) / 2)) : is_uncomplemented F.shatterer := by  classical  intro S hS hSc  have hs := op1370_local_shattered_card_lower n F S hS  have hsc := op1370_local_shattered_card_lower n F Sᶜ hSc  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  by_cases hle : (n + 1) / 2 ≤ S.card  · have hp : 2 ^ ((n + 1) / 2) ≤ 2 ^ S.card := by gcongr <;> omega    omega  · have hle' : (n + 1) / 2 ≤ (Sᶜ).card := by omega    have hp : 2 ^ ((n + 1) / 2) ≤ 2 ^ (Sᶜ).card := by gcongr <;> omega    omega
See it in the graphDiscuss this resultChallenge it