op_1370_two_exception_capacity_counterexample
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 alli j : ιwithi ≠ 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.
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.
lemma op1370_cap2_nonempty : ∀ i, (op1370_cap2_families i).Nonempty := by decide +kernel
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.
unfold strongly_incomparable decide +kernel
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.
unfold is_uncomplemented decide +kernel
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.
lemma op1370_cap2_nozero : (∀ S ∈ op1370_cap2_f2, (0 : Fin 5) ∉ S) ∧ (∀ S ∈ op1370_cap2_f3, (0 : Fin 5) ∉ S) := by decide +kernel
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\}$.
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
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`).
uses
op1370_cap2_nonempty,op1370_cap2_inc,op1370_cap2_unc,op1370_cap2_nozero,op1370_cap2_countsexact ⟨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.
- All verification steps—nonemptiness, strong incomparability, uncomplementedness, absence of coordinate 0, and the shattering cardinality—are performed by Lean's kernel evaluation tactic `decide +kernel` via exhaustive finite computation on `Fin 5`.
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 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⟩