op_1370_small_shatterer_threshold_counterexample
There exist three nonempty uncomplemented mutually strongly incomparable families on Fin 4 such that the first two contain four sets in total, but their union shatters a complementary pair. Thus the strict size condition in the small-shatterer lemma cannot be replaced by a non-strict one, even with a third incomparable family.
Statement
theorem op_1370_small_shatterer_threshold_counterexample : ∃ 𝒜 : Fin 3 → Finset (Finset (Fin 4)), (∀ i, (𝒜 i).Nonempty) ∧ (∀ i, is_uncomplemented (𝒜 i)) ∧ strongly_incomparable 𝒜 ∧ (𝒜 0).card + (𝒜 1).card = 4 ∧ ¬ is_uncomplemented (𝒜 0 ∪ 𝒜 1).shatterer- Source
- Sharpness counterexample for the trace-counting lemma related to arXiv:2611.12199, Conjecture 4.3.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
The proof, explained
The theorem is proved by constructing an explicit counterexample consisting of three families of 2-element subsets of Fin 4: $F_0 = \{\{0, 3\}, \{1, 3\}\}$, $F_1 = \{\{0, 2\}, \{1, 2\}\}$, and $F_2 = \{\{0, 1\}\}$. Each family is nonempty and uncomplemented (the complement of any 2-set in Fin 4 is another 2-set outside the family), and the families are mutually strongly incomparable because all five sets across the three families are distinct sets of the same size. While $|F_0| + |F_1| = 4$, their union shatters both $\{0, 3\}$ and its complement $\{1, 2\}$, so its shatterer is not uncomplemented.
Each of the three families in `op1370_threshold_families` is nonempty. automation
Since $F_0$ and $F_1$ each have two elements and $F_2$ has one element, all three families are nonempty; this is verified by finite kernel evaluation.
lemma op1370_threshold_nonempty : ∀ i, (op1370_threshold_families i).Nonempty := by decide +kernel
Each of the three families is uncomplemented (contains no set together with its complement in Fin 4). automation
Unfolding the definition of `is_uncomplemented`, the goal is to show that for every set $A$ in each family, its complement $A^c$ is not in that family. Since each family consists of 2-element subsets whose complements are distinct 2-element subsets not in that family, this holds and is verified by kernel computation.
unfold is_uncomplemented decide +kernel
The three families are mutually strongly incomparable: no element of one family is a subset of an element of a different family. automation
Unfolding `strongly_incomparable`, we check that for $i \neq j$, no $A \in F_i$ satisfies $A \subseteq B$ for $B \in F_j$. Because all sets across all three families are distinct 2-element subsets of Fin 4, two distinct sets of the same cardinality cannot have an inclusion between them. Lean checks this by kernel computation.
unfold strongly_incomparable decide +kernel
The sum of the cardinalities of the first two families $F_0$ and $F_1$ is 4. automation
Both $F_0$ and $F_1$ contain exactly 2 sets, so $|F_0| + |F_1| = 2 + 2 = 4$, verified by kernel evaluation.
lemma op1370_threshold_count : op1370_threshold_f0.card + op1370_threshold_f1.card = 4 := by decide +kernel
The shatterer of $F_0 \cup F_1$ is not uncomplemented. automation
Unfolding `is_uncomplemented`, the goal is to show that the shatterer contains a set along with its complement. The 4-element union $F_0 \cup F_1 = \{\{0, 3\}, \{1, 3\}, \{0, 2\}, \{1, 2\}\}$ shatters both $\{0, 3\}$ and its complement $\{1, 2\}$, which Lean confirms by kernel evaluation.
unfold is_uncomplemented decide +kernel
There exist three nonempty, uncomplemented, strongly incomparable families on Fin 4 whose first two sum to size 4 but whose union has a shatterer that is not uncomplemented.
The existential witness is provided by the triple of families `op1370_threshold_families`, along with the proofs of the five required properties established by `op1370_threshold_nonempty`, `op1370_threshold_unc`, `op1370_threshold_inc`, `op1370_threshold_count`, and `op1370_threshold_shat`.
uses
op1370_threshold_nonempty,op1370_threshold_unc,op1370_threshold_inc,op1370_threshold_count,op1370_threshold_shatexact ⟨op1370_threshold_families, op1370_threshold_nonempty, op1370_threshold_unc, op1370_threshold_inc, op1370_threshold_count, op1370_threshold_shat⟩
op1370_threshold_nonempty- Each of the three families in `op1370_threshold_families` is nonempty.
op1370_threshold_unc- Each of the three families in `op1370_threshold_families` is uncomplemented (contains no set together with its complement).
op1370_threshold_inc- The three families in `op1370_threshold_families` are mutually strongly incomparable: no set in one family is a subset of any set in another.
op1370_threshold_count- The sum of the cardinalities of the first two families `op1370_threshold_f0` and `op1370_threshold_f1` is 4.
op1370_threshold_shat- The shatterer of the union `op1370_threshold_f0 ∪ op1370_threshold_f1` is not uncomplemented (it contains a complementary pair of sets).
- The five prerequisite lemmas (nonemptiness, uncomplementedness, strong incomparability, cardinality sum, and failure of uncomplementedness of the shatterer) are all verified via finite exhaustive evaluation by the Lean kernel using `decide +kernel`.
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 1500000set_option maxRecDepth 8192def op1370_threshold_f0 : Finset (Finset (Fin 4)) := {{0,3}, {1,3}}def op1370_threshold_f1 : Finset (Finset (Fin 4)) := {{0,2}, {1,2}}def op1370_threshold_f2 : Finset (Finset (Fin 4)) := {{0,1}}def op1370_threshold_families : Fin 3 → Finset (Finset (Fin 4)) := ![op1370_threshold_f0, op1370_threshold_f1, op1370_threshold_f2]lemma op1370_threshold_nonempty : ∀ i, (op1370_threshold_families i).Nonempty := by decide +kernellemma op1370_threshold_unc : ∀ i, is_uncomplemented (op1370_threshold_families i) := by unfold is_uncomplemented decide +kernellemma op1370_threshold_inc : strongly_incomparable op1370_threshold_families := by unfold strongly_incomparable decide +kernellemma op1370_threshold_count : op1370_threshold_f0.card + op1370_threshold_f1.card = 4 := by decide +kernellemma op1370_threshold_shat : ¬ is_uncomplemented (op1370_threshold_f0 ∪ op1370_threshold_f1).shatterer := by unfold is_uncomplemented decide +kerneltheorem op_1370_small_shatterer_threshold_counterexample : ∃ 𝒜 : Fin 3 → Finset (Finset (Fin 4)), (∀ i, (𝒜 i).Nonempty) ∧ (∀ i, is_uncomplemented (𝒜 i)) ∧ strongly_incomparable 𝒜 ∧ (𝒜 0).card + (𝒜 1).card = 4 ∧ ¬ is_uncomplemented (𝒜 0 ∪ 𝒜 1).shatterer := by exact ⟨op1370_threshold_families, op1370_threshold_nonempty, op1370_threshold_unc, op1370_threshold_inc, op1370_threshold_count, op1370_threshold_shat⟩