AFTD Auto-Formalizing Theoretical Domains

op_1370_orbit_equal_nonstrict_counterexample

theoremverified

There is an uncomplemented family of 15 subsets of Fin 5, all incomparable to {0,1}, which shatters 17 sets in exactly 15 complementary orbits. Hence equality between family size and shattered-orbit count does not imply ordinary shattering equality, even with an incomparable witness and with empty and full sets absent.

Statement

theorem op_1370_orbit_equal_nonstrict_counterexample : ∃ F : Finset (Finset (Fin 5)), is_uncomplemented F ∧ F.card = 15 ∧ (∀ S ∈ F, ¬ ({0,1} : Finset (Fin 5)) ⊆ S ∧ ¬ S ⊆ ({0,1} : Finset (Fin 5))) ∧ (F.shatterer ∪ F.shatterer.image compl).card = 30 ∧ F.shatterer.card = 17
Source
Counterexample to an orbit-equality simplification in the study of 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 theorem is proved by exhibiting an explicit candidate family of 15 subsets of Fin 5, named `op1370_orbit_equal_family`. All five properties—that the family is uncomplemented, has size 15, contains only sets incomparable to {0, 1}, spans 30 sets under complementary orbit closure (15 orbits), and shatters 17 sets—are verified by finite exhaustive computation using Lean's kernel decision procedure.

  1. It suffices to verify the five required conditions for the candidate family `op1370_orbit_equal_family`.

    We instantiate the existential quantifier with the explicit 15-element family of subsets of Fin 5 defined on line 4, producing five subgoals corresponding to the conjuncts of the theorem.

    line 7

      refine ⟨op1370_orbit_equal_family, ?_, ?_, ?_, ?_, ?_⟩
  2. The family is uncomplemented: no member has its complement also in the family.

    Unfolding `is_uncomplemented` turns the goal into checking that for every set A in the family, Aᶜ is not in the family. Lean's kernel decision procedure evaluates this finite condition over all 15 elements and confirms it holds.

    line 8

      · unfold is_uncomplemented; decide +kernel
  3. The family has cardinality exactly 15.

    The cardinality of the explicitly defined finite set of sets is verified directly by kernel computation, confirming that all 15 listed subsets are pairwise distinct.

    line 9

      · decide +kernel
  4. Every member of the family is incomparable to {0, 1}.

    For each of the 15 sets S in the family, the kernel evaluates both {0, 1} ⊈ S and S ⊈ {0, 1}, confirming that none contains {0, 1} and none is a subset of {0, 1}.

    line 10

      · decide +kernel
  5. The union of the shattered sets and their complements has cardinality 30.

    The kernel computes which of the 32 subsets of Fin 5 are shattered by the family, forms their union with their complements, and checks that this collection contains exactly 30 sets, corresponding to 15 complementary orbits.

    line 11

      · decide +kernel
  6. The family shatters exactly 17 sets.

    The kernel computes the shattering set of the family across all 32 subsets of Fin 5 and verifies that its cardinality is 17.

    line 12

      · decide +kernel

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_orbit_equal_family : Finset (Finset (Fin 5)) := {{2}, {0,2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}, {4}, {1,4}, {2,4}, {1,2,4}, {3,4}, {2,3,4}, {0,2,3,4}, {1,2,3,4}}theorem op_1370_orbit_equal_nonstrict_counterexample : ∃ F : Finset (Finset (Fin 5)), is_uncomplemented F ∧ F.card = 15 ∧ (∀ S ∈ F, ¬ ({0,1} : Finset (Fin 5)) ⊆ S ∧ ¬ S ⊆ ({0,1} : Finset (Fin 5))) ∧ (F.shatterer ∪ F.shatterer.image compl).card = 30 ∧ F.shatterer.card = 17 := by  refine ⟨op1370_orbit_equal_family, ?_, ?_, ?_, ?_, ?_⟩  · unfold is_uncomplemented; decide +kernel  · decide +kernel  · decide +kernel  · decide +kernel  · decide +kernel
See it in the graphDiscuss this resultChallenge it