AFTD Auto-Formalizing Theoretical Domains

op_1370_shattering_complement_dichotomy_counterexample

theoremverified

There is an uncomplemented family of subsets of Fin 6 which shatters both {0,1,2} and its complement {3,4,5}, while it shatters neither {0,2,3} nor its complement {1,4,5}.

Statement

theorem op_1370_shattering_complement_dichotomy_counterexample : ∃ F : Finset (Finset (Fin 6)), is_uncomplemented F ∧ ({0,1,2} : Finset (Fin 6)) ∈ F.shatterer ∧ ({3,4,5} : Finset (Fin 6)) ∈ F.shatterer ∧ ({0,2,3} : Finset (Fin 6)) ∉ F.shatterer ∧ ({1,4,5} : Finset (Fin 6)) ∉ F.shatterer
Source
Counterexample to a possible shattering dichotomy encountered while studying arXiv:2611.12199, Conjecture 4.3.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • is_uncomplementedA family of subsets of a finite set is uncomplemented if no set and its complement both belong to the family.

The proof, explained

The proof provides an explicit counterexample: a family of eight subsets of {0, 1, 2, 3, 4, 5} named op1370_eight_sets. The goal reduces to checking five concrete conditions on this family—that it is uncomplemented, shatters both {0, 1, 2} and {3, 4, 5}, and shatters neither {0, 2, 3} nor {1, 4, 5}—each of which is verified by finite kernel evaluation (decide +kernel).

  1. It suffices to verify the five required properties for the explicit family op1370_eight_sets.

    We provide the candidate family op1370_eight_sets—an explicit collection of eight subsets of {0, 1, 2, 3, 4, 5}—as a witness for the existential quantifier. This reduces the theorem to five subgoals: showing that op1370_eight_sets is uncomplemented, that it shatters {0, 1, 2}, that it shatters {3, 4, 5}, that it does not shatter {0, 2, 3}, and that it does not shatter {1, 4, 5}.

    line 7

      refine ⟨op1370_eight_sets, ?_, ?_, ?_, ?_, ?_⟩
  2. The family op1370_eight_sets is uncomplemented.

    Unfolding the definition of is_uncomplemented gives the condition that for every set A in op1370_eight_sets, its complement Aᶜ is not in op1370_eight_sets. Since the family contains only eight explicit subsets of a 6-element set, Lean's kernel verifies this universal condition over a finite domain by direct computational evaluation (decide +kernel).

    line 8

    uses is_uncomplemented

      · unfold is_uncomplemented; decide +kernel
  3. The family op1370_eight_sets shatters both {0, 1, 2} and its complement {3, 4, 5}.

    A set S is shattered by a family if its intersections with the members of the family yield all 2^|S| subsets of S. For both S = {0, 1, 2} and S = {3, 4, 5}, kernel evaluation (decide +kernel) computes the traces of the eight family members on S and confirms that all 2^3 = 8 subsets are present, so both sets belong to the shatterer of op1370_eight_sets.

    lines 9–10

      · decide +kernel
      · decide +kernel
  4. The family op1370_eight_sets shatters neither {0, 2, 3} nor its complement {1, 4, 5}.

    For S = {0, 2, 3} and S = {1, 4, 5}, kernel evaluation (decide +kernel) exhaustively computes the intersection of each member of op1370_eight_sets with S and verifies that the resulting trace fails to generate all 8 subsets (in fact, each produces only 4 distinct subsets), showing that neither set is shattered.

    lines 11–12

      · decide +kernel
      · decide +kernel
is_uncomplemented
A family of subsets 𝒜 of a finite type is uncomplemented if for every set A ∈ 𝒜, its complement Aᶜ is not in 𝒜.

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_eight_sets : Finset (Finset (Fin 6)) := {∅, {0,3}, {1,4}, {0,1,3,4}, {0,2,5}, {2,3,5}, {0,1,2,4,5}, {1,2,3,4,5}}theorem op_1370_shattering_complement_dichotomy_counterexample : ∃ F : Finset (Finset (Fin 6)), is_uncomplemented F ∧ ({0,1,2} : Finset (Fin 6)) ∈ F.shatterer ∧ ({3,4,5} : Finset (Fin 6)) ∈ F.shatterer ∧ ({0,2,3} : Finset (Fin 6)) ∉ F.shatterer ∧ ({1,4,5} : Finset (Fin 6)) ∉ F.shatterer := by  refine ⟨op1370_eight_sets, ?_, ?_, ?_, ?_, ?_⟩  · unfold is_uncomplemented; decide +kernel  · decide +kernel  · decide +kernel  · decide +kernel  · decide +kernel
See it in the graphDiscuss this resultChallenge it