op_1370_pair_shatter_surplus_counterexample
There are three families indexed by Fin 3 of subsets of Fin 6, each with nine sets, which are nonempty, uncomplemented, and mutually strongly incomparable; every element appears in at least two families and is absent from at least two families. For each of the pairs (0,1), (0,2), and (1,2), the union of that pair shatters sets whose union with their complements has cardinality 38.
Statement
theorem op_1370_pair_shatter_surplus_counterexample :
∃ 𝒜 : Fin 3 → Finset (Finset (Fin 6)),
(∀ i, (𝒜 i).Nonempty) ∧ (∀ i, is_uncomplemented (𝒜 i)) ∧
strongly_incomparable 𝒜 ∧
(∀ x, ∃ i j : Fin 3, i ≠ j ∧ (∃ S ∈ 𝒜 i, x ∈ S) ∧ (∃ T ∈ 𝒜 j, x ∈ T)) ∧
(∀ x, ∃ i j : Fin 3, i ≠ j ∧ (∃ S ∈ 𝒜 i, x ∉ S) ∧ (∃ T ∈ 𝒜 j, x ∉ T)) ∧
(∀ i, (𝒜 i).card = 9) ∧
(((𝒜 0 ∪ 𝒜 1).shatterer ∪ ((𝒜 0 ∪ 𝒜 1).shatterer.image compl)).card = 38) ∧
(((𝒜 0 ∪ 𝒜 2).shatterer ∪ ((𝒜 0 ∪ 𝒜 2).shatterer.image compl)).card = 38) ∧
(((𝒜 1 ∪ 𝒜 2).shatterer ∪ ((𝒜 1 ∪ 𝒜 2).shatterer.image compl)).card = 38)- Related work
- Explicit counterexample to a proposed two-extra-shattered-orbits shortcut toward 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…
Read back from the Lean
There exists a family 𝒜 of 3 collections of subsets of Fin 6 (indexed by Fin 3, so 𝒜₀, 𝒜₁, 𝒜₂) such that:
1. For each i : Fin 3, 𝒜 i is nonempty.
2. For each i : Fin 3, 𝒜 i is uncomplemented (i.e., for every set A ∈ 𝒜 i, its complement Aᶜ ∉ 𝒜 i).
3. The family 𝒜 is strongly incomparable (for all i ≠ j in Fin 3, no set A ∈ 𝒜 i is a subset of any set B ∈ 𝒜 j).
4. For every element x : Fin 6, there exist distinct i, j : Fin 3 such that x belongs to at least one set in 𝒜 i and to at least one set in 𝒜 j.
5. For every element x : Fin 6, there exist distinct i, j : Fin 3 such that x does not belong to at least one set in 𝒜 i and does not belong to at least one set in 𝒜 j.
6. For each i : Fin 3, 𝒜 i has cardinality exactly 9.
7. For the pair (0, 1), the union of the shattered sets of 𝒜 0 ∪ 𝒜 1 and the complements of those shattered sets has cardinality exactly 38.
8. For the pair (0, 2), the union of the shattered sets of 𝒜 0 ∪ 𝒜 2 and the complements of those shattered sets has cardinality exactly 38.
9. For the pair (1, 2), the union of the shattered sets of 𝒜 1 ∪ 𝒜 2 and the complements of those shattered sets has cardinality exactly 38.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
We exhibit an explicit counterexample consisting of three families of subsets of a 6-element set, each of cardinality 9, constructed symmetrically around disjoint pairs of elements. We instantiate the existential quantifier with this construction and verify the required properties: nonemptiness, uncomplementedness, strong incomparability, element coverage and noncoverage, and the condition that the orbit closure under complementation of shattered sets for every pair of families has cardinality exactly 38. The verification reduces to finite combinatorial checks solved by decision procedures and kernel evaluation.
Each of the three families is nonempty. automation
By exhaustive finite set verification via kernel evaluation (`decide +kernel`), each of the three explicitly defined families contains at least one set.
lemma op1370_family_nonempty : ∀ i, (op1370_families i).Nonempty := by decide +kernel
Each of the three families is uncomplemented. automation
We unfold the definition of `is_uncomplemented` to require that for every index $i \\in \\{0, 1, 2\\}$ and every set $A$ in the family, the complement $A^c$ is not in that family. This finite condition is verified by kernel evaluation.
unfold is_uncomplemented decide +kernel
The three families are mutually strongly incomparable. automation
We unfold `strongly_incomparable` to state that whenever $i \\neq j$, no set $A \\in \\mathcal{A}_i$ is a subset of any set $B \\in \\mathcal{A}_j$. This finite property is checked exhaustively by kernel evaluation.
unfold strongly_incomparable decide +kernel
Every element of the ground set Fin 6 appears in at least two distinct families. automation
For each of the six ground elements, kernel evaluation verifies that there exist two distinct family indices containing that element in at least one of their member sets.
lemma op1370_family_coverage : ∀ x : Fin 6, ∃ i j : Fin 3, i ≠ j ∧ (∃ S ∈ op1370_families i, x ∈ S) ∧ (∃ T ∈ op1370_families j, x ∈ T) := by decide +kernel
Every element of the ground set Fin 6 is absent from at least two distinct families. automation
For each ground element, kernel evaluation verifies that there exist two distinct family indices with at least one member set omitting that element.
lemma op1370_family_noncoverage : ∀ x : Fin 6, ∃ i j : Fin 3, i ≠ j ∧ (∃ S ∈ op1370_families i, x ∉ S) ∧ (∃ T ∈ op1370_families j, x ∉ T) := by decide +kernel
The orbit closure of the union of family 0 and family 1 has cardinality 38. automation
Kernel evaluation computes all sets shattered by the union $\\mathcal{A}_0 \\cup \\mathcal{A}_1$, forms their union with their complements, and confirms the resulting family has exactly 38 sets.
lemma op1370_orbit_01 : (op1370_orbit_closure (op1370_family_0 ∪ op1370_family_1)).card = 38 := by decide +kernel
The orbit closure of the union of family 0 and family 2 has cardinality 38. automation
Similarly, kernel evaluation computes the orbit closure of $\\mathcal{A}_0 \\cup \\mathcal{A}_2$ and confirms its cardinality is 38.
lemma op1370_orbit_02 : (op1370_orbit_closure (op1370_family_0 ∪ op1370_family_2)).card = 38 := by decide +kernel
The orbit closure of the union of family 1 and family 2 has cardinality 38. automation
Similarly, kernel evaluation computes the orbit closure of $\\mathcal{A}_1 \\cup \\mathcal{A}_2$ and confirms its cardinality is 38.
lemma op1370_orbit_12 : (op1370_orbit_closure (op1370_family_1 ∪ op1370_family_2)).card = 38 := by decide +kernel
The candidate triple of families satisfies nonemptiness, uncomplementedness, strong incomparability, coverage, and noncoverage.
We instantiate the existential quantifier with the explicit triple `op1370_families` and provide the pre-established helper lemmas for nonemptiness, uncomplementedness, strong incomparability, coverage, and noncoverage, leaving four remaining goals.
uses
op1370_family_nonempty,op1370_family_uncomp,op1370_family_incomp,op1370_family_coverage,op1370_family_noncoveragerefine ⟨op1370_families, op1370_family_nonempty, op1370_family_uncomp, op1370_family_incomp, op1370_family_coverage, op1370_family_noncoverage, ?_, ?_, ?_, ?_⟩Each of the three families has cardinality exactly 9. automation
For an arbitrary index $i \\in \\text{Fin } 3$, we perform case analysis over $i = 0, 1, 2$. In each branch, kernel evaluation verifies that the explicitly defined finite set has cardinality 9.
· intro i fin_cases i <;> decide +kernel
The orbit closure of the union of family 0 and family 1 has cardinality 38.
This goal is resolved by supplying the pre-computed lemma `op1370_orbit_01`.
uses
op1370_orbit_01· exact op1370_orbit_01The orbit closure of the union of family 0 and family 2 has cardinality 38.
This goal is resolved by supplying the pre-computed lemma `op1370_orbit_02`.
uses
op1370_orbit_02· exact op1370_orbit_02The orbit closure of the union of family 1 and family 2 has cardinality 38.
This goal is resolved by supplying the pre-computed lemma `op1370_orbit_12`.
uses
op1370_orbit_12· exact op1370_orbit_12
op1370_family_nonempty- Each of the three families op1370_families i is nonempty.
op1370_family_uncomp- Each of the three families is uncomplemented: no set in the family has its complement also in the family.
op1370_family_incomp- The three families are mutually strongly incomparable: no set in one family is a subset of any set in another family.
op1370_family_coverage- Every element of Fin 6 belongs to at least one set in at least two distinct families.
op1370_family_noncoverage- Every element of Fin 6 is omitted by at least one set in at least two distinct families.
op1370_orbit_01- The orbit closure (the shattered subsets together with their complements) of the union of family 0 and family 1 has cardinality 38.
op1370_orbit_02- The orbit closure of the union of family 0 and family 2 has cardinality 38.
op1370_orbit_12- The orbit closure of the union of family 1 and family 2 has cardinality 38.
- The proof relies extensively on finite combinatorial verification via kernel computation (`decide +kernel`), which checks nonemptiness, uncomplementedness, strong incomparability, coverage, noncoverage, family cardinalities, and the orbit closure sizes of pair unions by exhaustive enumeration over finite 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
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 2000000set_option maxRecDepth 8192def op1370_family_0 : Finset (Finset (Fin 6)) := {{0, 1}, {0, 1, 2}, {0, 1, 3}, {0, 1, 2, 3}, {0, 1, 4}, {0, 1, 3, 4}, {0, 1, 5}, {0, 1, 2, 5}, {0, 1, 4, 5}}def op1370_family_1 : Finset (Finset (Fin 6)) := {{3, 5}, {0, 3, 5}, {1, 3, 5}, {2, 3, 5}, {0, 2, 3, 5}, {1, 2, 3, 5}, {3, 4, 5}, {0, 3, 4, 5}, {1, 3, 4, 5}}def op1370_family_2 : Finset (Finset (Fin 6)) := {{2, 4}, {0, 2, 4}, {1, 2, 4}, {2, 3, 4}, {0, 2, 3, 4}, {1, 2, 3, 4}, {2, 4, 5}, {0, 2, 4, 5}, {1, 2, 4, 5}}def op1370_families : Fin 3 → Finset (Finset (Fin 6)) := ![op1370_family_0, op1370_family_1, op1370_family_2]def op1370_orbit_closure (F : Finset (Finset (Fin 6))) : Finset (Finset (Fin 6)) := F.shatterer ∪ F.shatterer.image compllemma op1370_family_nonempty : ∀ i, (op1370_families i).Nonempty := by decide +kernellemma op1370_family_uncomp : ∀ i, is_uncomplemented (op1370_families i) := by unfold is_uncomplemented decide +kernellemma op1370_family_incomp : strongly_incomparable op1370_families := by unfold strongly_incomparable decide +kernellemma op1370_family_coverage : ∀ x : Fin 6, ∃ i j : Fin 3, i ≠ j ∧ (∃ S ∈ op1370_families i, x ∈ S) ∧ (∃ T ∈ op1370_families j, x ∈ T) := by decide +kernellemma op1370_family_noncoverage : ∀ x : Fin 6, ∃ i j : Fin 3, i ≠ j ∧ (∃ S ∈ op1370_families i, x ∉ S) ∧ (∃ T ∈ op1370_families j, x ∉ T) := by decide +kernellemma op1370_orbit_01 : (op1370_orbit_closure (op1370_family_0 ∪ op1370_family_1)).card = 38 := by decide +kernellemma op1370_orbit_02 : (op1370_orbit_closure (op1370_family_0 ∪ op1370_family_2)).card = 38 := by decide +kernellemma op1370_orbit_12 : (op1370_orbit_closure (op1370_family_1 ∪ op1370_family_2)).card = 38 := by decide +kerneltheorem op_1370_pair_shatter_surplus_counterexample : ∃ 𝒜 : Fin 3 → Finset (Finset (Fin 6)), (∀ i, (𝒜 i).Nonempty) ∧ (∀ i, is_uncomplemented (𝒜 i)) ∧ strongly_incomparable 𝒜 ∧ (∀ x, ∃ i j : Fin 3, i ≠ j ∧ (∃ S ∈ 𝒜 i, x ∈ S) ∧ (∃ T ∈ 𝒜 j, x ∈ T)) ∧ (∀ x, ∃ i j : Fin 3, i ≠ j ∧ (∃ S ∈ 𝒜 i, x ∉ S) ∧ (∃ T ∈ 𝒜 j, x ∉ T)) ∧ (∀ i, (𝒜 i).card = 9) ∧ (((𝒜 0 ∪ 𝒜 1).shatterer ∪ ((𝒜 0 ∪ 𝒜 1).shatterer.image compl)).card = 38) ∧ (((𝒜 0 ∪ 𝒜 2).shatterer ∪ ((𝒜 0 ∪ 𝒜 2).shatterer.image compl)).card = 38) ∧ (((𝒜 1 ∪ 𝒜 2).shatterer ∪ ((𝒜 1 ∪ 𝒜 2).shatterer.image compl)).card = 38) := by refine ⟨op1370_families, op1370_family_nonempty, op1370_family_uncomp, op1370_family_incomp, op1370_family_coverage, op1370_family_noncoverage, ?_, ?_, ?_, ?_⟩ · intro i fin_cases i <;> decide +kernel · exact op1370_orbit_01 · exact op1370_orbit_02 · exact op1370_orbit_12