AFTD Auto-Formalizing Theoretical Domains

op_1370_pair_shatter_surplus_counterexample

theoremverifiedoriginal

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

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

    line 12

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

    lines 14–15

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

    lines 17–18

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

    line 19

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

    line 20

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

    line 21

    lemma op1370_orbit_01 : (op1370_orbit_closure (op1370_family_0 ∪ op1370_family_1)).card = 38 := by decide +kernel
  7. 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.

    line 22

    lemma op1370_orbit_02 : (op1370_orbit_closure (op1370_family_0 ∪ op1370_family_2)).card = 38 := by decide +kernel
  8. 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.

    line 23

    lemma op1370_orbit_12 : (op1370_orbit_closure (op1370_family_1 ∪ op1370_family_2)).card = 38 := by decide +kernel
  9. 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.

    lines 35–36

    uses op1370_family_nonempty, op1370_family_uncomp, op1370_family_incomp, op1370_family_coverage, op1370_family_noncoverage

      refine ⟨op1370_families, op1370_family_nonempty, op1370_family_uncomp, op1370_family_incomp,
        op1370_family_coverage, op1370_family_noncoverage, ?_, ?_, ?_, ?_⟩
  10. 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.

    lines 37–38

      · intro i
        fin_cases i <;> decide +kernel
  11. 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`.

    line 39

    uses op1370_orbit_01

      · exact op1370_orbit_01
  12. The 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`.

    line 40

    uses op1370_orbit_02

      · exact op1370_orbit_02
  13. The 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`.

    line 41

    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.

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