op_1370_small_family_shatterer_uncomplemented
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.
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|.
uses
Finset.shatters_iff.mp,Finset.mem_shatterer.mp,Finset.card_image_le,Finset.card_powersethave 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
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|.
uses
op1370_local_shattered_card_lowerclassical 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
|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.
uses
Finset.card_le_univ,Finset.card_compl,Fintype.card_finhave 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
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.
by_cases hle : (n + 1) / 2 ≤ S.card · have hp : 2 ^ ((n + 1) / 2) ≤ 2 ^ S.card := by gcongr <;> omega omega
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.
· 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
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.
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