AFTD Auto-Formalizing Theoretical Domains

op_1370_small_shatterer_threshold_counterexample

theoremverified

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 all i j : ι with i ≠ 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.

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

    line 8

    lemma op1370_threshold_nonempty : ∀ i, (op1370_threshold_families i).Nonempty := by decide +kernel
  2. 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.

    lines 10–11

      unfold is_uncomplemented
      decide +kernel
  3. 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.

    lines 13–14

      unfold strongly_incomparable
      decide +kernel
  4. 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.

    line 15

    lemma op1370_threshold_count : op1370_threshold_f0.card + op1370_threshold_f1.card = 4 := by decide +kernel
  5. 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.

    lines 17–18

      unfold is_uncomplemented
      decide +kernel
  6. 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`.

    line 21

    uses op1370_threshold_nonempty, op1370_threshold_unc, op1370_threshold_inc, op1370_threshold_count, op1370_threshold_shat

      exact ⟨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).

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