AFTD Auto-Formalizing Theoretical Domains

op_1370_two_exception_capacity_counterexample

theoremverified

There are four nonempty mutually strongly incomparable families on Fin 5, with the first two uncomplemented and with element 0 absent from the last two; the first two families have four sets each, while the union of the last two shatters nine sets. Thus eight plus nine exceeds the 16 subsets of the other four coordinates, disproving the direct two-exception extension of the private-element shattering-capacity inequality.

Statement

theorem op_1370_two_exception_capacity_counterexample : ∃ 𝒜 : Fin 4 → Finset (Finset (Fin 5)), (∀ i, (𝒜 i).Nonempty) ∧ strongly_incomparable 𝒜 ∧ is_uncomplemented (𝒜 0) ∧ is_uncomplemented (𝒜 1) ∧ (∀ S ∈ 𝒜 2, (0 : Fin 5) ∉ S) ∧ (∀ S ∈ 𝒜 3, (0 : Fin 5) ∉ S) ∧ (𝒜 0).card = 4 ∧ (𝒜 1).card = 4 ∧ (𝒜 2 ∪ 𝒜 3).shatterer.card = 9
Source
Counterexample to a proposed two-exception generalization of op_1370_shattered_capacity, 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 disproves the direct two-exception extension of the private-element shattering-capacity inequality by providing an explicit witness sequence of four families on Fin 5. The first two families have 4 sets each and contain 0, while the remaining two families avoid 0 and their union shatters 9 sets. Lean's kernel decision procedure checks that the families are nonempty, strongly incomparable, that the first two are uncomplemented, and that the cardinality counts hold. Since $4 + 4 + 9 = 17$ exceeds the 16 subsets of the remaining four coordinates, this produces the desired counterexample.

  1. Each of the four families is nonempty. automation

    The four families have sizes 4, 4, 3, and 1, respectively. Lean's kernel decision procedure `decide +kernel` verifies the nonemptiness of each family by finite computation.

    line 9

    lemma op1370_cap2_nonempty : ∀ i, (op1370_cap2_families i).Nonempty := by decide +kernel
  2. The four families are mutually strongly incomparable. automation

    Unfolding the definition of `strongly_incomparable` reduces the goal to checking that for all distinct family indices $i \ne j$, no set in family $i$ is a subset of any set in family $j$. The kernel decision procedure verifies this finite set of non-inclusions by exhaustive evaluation.

    lines 11–12

      unfold strongly_incomparable
      decide +kernel
  3. The first two families are uncomplemented. automation

    Unfolding `is_uncomplemented` reduces the goal to checking that the complement of every set in $\mathcal{A}_0$ (and $\mathcal{A}_1$) with respect to Fin 5 does not belong to that family. The kernel decision procedure computes the complements and verifies non-membership.

    lines 14–15

      unfold is_uncomplemented
      decide +kernel
  4. Element 0 is absent from every set in the third and fourth families. automation

    The sets of $\mathcal{A}_2$ are $\{1,2\}, \{1,4\}, \{3,4\}$ and the unique set of $\mathcal{A}_3$ is $\{2,3\}$. The kernel decision procedure checks that 0 is not an element of any of these sets.

    line 16

    lemma op1370_cap2_nozero : (∀ S ∈ op1370_cap2_f2, (0 : Fin 5) ∉ S) ∧ (∀ S ∈ op1370_cap2_f3, (0 : Fin 5) ∉ S) := by decide +kernel
  5. The first two families each have cardinality 4, and the union of the last two shatters 9 sets. automation

    The kernel decision procedure evaluates the cardinalities $|\mathcal{A}_0| = 4$ and $|\mathcal{A}_1| = 4$, and determines the shatterer of the 4-edge cycle $\mathcal{A}_2 \cup \mathcal{A}_3 = \{\{1,2\}, \{1,4\}, \{3,4\}, \{2,3\}\}$. It verifies that exactly 9 sets are shattered: the empty set, the 4 singletons $\{1\}, \{2\}, \{3\}, \{4\}$, and the 4 pairs $\{1,2\}, \{1,4\}, \{3,4\}, \{2,3\}$.

    line 17

    lemma op1370_cap2_counts : op1370_cap2_f0.card = 4 ∧ op1370_cap2_f1.card = 4 ∧ (op1370_cap2_f2 ∪ op1370_cap2_f3).shatterer.card = 9 := by decide +kernel
  6. The tuple of four families witnesses the counterexample to the capacity inequality.

    The existential goal is closed by supplying the sequence of four families `op1370_cap2_families` as the witness, along with the proofs of nonemptiness (`op1370_cap2_nonempty`), strong incomparability (`op1370_cap2_inc`), uncomplementedness (`op1370_cap2_unc`), absence of 0 (`op1370_cap2_nozero`), and the cardinality counts (`op1370_cap2_counts`).

    line 20

    uses op1370_cap2_nonempty, op1370_cap2_inc, op1370_cap2_unc, op1370_cap2_nozero, op1370_cap2_counts

      exact ⟨op1370_cap2_families, op1370_cap2_nonempty, op1370_cap2_inc, op1370_cap2_unc.1, op1370_cap2_unc.2, op1370_cap2_nozero.1, op1370_cap2_nozero.2, op1370_cap2_counts.1, op1370_cap2_counts.2.1, op1370_cap2_counts.2.2⟩
op1370_cap2_nonempty
Every family in the sequence `op1370_cap2_families` is nonempty.
op1370_cap2_inc
The four families in `op1370_cap2_families` are mutually strongly incomparable: no set in any family is a subset of any set in a different family.
op1370_cap2_unc
Both families `op1370_cap2_f0` and `op1370_cap2_f1` are uncomplemented, meaning no member set has its complement with respect to Fin 5 in the same family.
op1370_cap2_nozero
The coordinate 0 is not an element of any set in `op1370_cap2_f2` or `op1370_cap2_f3`.
op1370_cap2_counts
The families `op1370_cap2_f0` and `op1370_cap2_f1` each have cardinality 4, and the union `op1370_cap2_f2 ∪ op1370_cap2_f3` shatters exactly 9 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 1800000set_option maxRecDepth 8192def op1370_cap2_f0 : Finset (Finset (Fin 5)) := {{0,1}, {0,3}, {1,3}, {0,1,3}}def op1370_cap2_f1 : Finset (Finset (Fin 5)) := {{0,2}, {0,4}, {2,4}, {0,2,4}}def op1370_cap2_f2 : Finset (Finset (Fin 5)) := {{1,2}, {1,4}, {3,4}}def op1370_cap2_f3 : Finset (Finset (Fin 5)) := {{2,3}}def op1370_cap2_families : Fin 4 → Finset (Finset (Fin 5)) := ![op1370_cap2_f0, op1370_cap2_f1, op1370_cap2_f2, op1370_cap2_f3]lemma op1370_cap2_nonempty : ∀ i, (op1370_cap2_families i).Nonempty := by decide +kernellemma op1370_cap2_inc : strongly_incomparable op1370_cap2_families := by  unfold strongly_incomparable  decide +kernellemma op1370_cap2_unc : is_uncomplemented op1370_cap2_f0 ∧ is_uncomplemented op1370_cap2_f1 := by  unfold is_uncomplemented  decide +kernellemma op1370_cap2_nozero : (∀ S ∈ op1370_cap2_f2, (0 : Fin 5) ∉ S) ∧ (∀ S ∈ op1370_cap2_f3, (0 : Fin 5) ∉ S) := by decide +kernellemma op1370_cap2_counts : op1370_cap2_f0.card = 4 ∧ op1370_cap2_f1.card = 4 ∧ (op1370_cap2_f2 ∪ op1370_cap2_f3).shatterer.card = 9 := by decide +kerneltheorem op_1370_two_exception_capacity_counterexample : ∃ 𝒜 : Fin 4 → Finset (Finset (Fin 5)), (∀ i, (𝒜 i).Nonempty) ∧ strongly_incomparable 𝒜 ∧ is_uncomplemented (𝒜 0) ∧ is_uncomplemented (𝒜 1) ∧ (∀ S ∈ 𝒜 2, (0 : Fin 5) ∉ S) ∧ (∀ S ∈ 𝒜 3, (0 : Fin 5) ∉ S) ∧ (𝒜 0).card = 4 ∧ (𝒜 1).card = 4 ∧ (𝒜 2 ∪ 𝒜 3).shatterer.card = 9 := by  exact ⟨op1370_cap2_families, op1370_cap2_nonempty, op1370_cap2_inc, op1370_cap2_unc.1, op1370_cap2_unc.2, op1370_cap2_nozero.1, op1370_cap2_nozero.2, op1370_cap2_counts.1, op1370_cap2_counts.2.1, op1370_cap2_counts.2.2⟩
See it in the graphDiscuss this resultChallenge it