AFTD Auto-Formalizing Theoretical Domains

op_1370_unrestricted_shattered_orbits_counterexample

theoremverified

There is a family of eight subsets of Fin 4, all incomparable to {0,1}, whose shattered sets occupy only seven complementary orbits.

Statement

theorem op_1370_unrestricted_shattered_orbits_counterexample : ∃ F : Finset (Finset (Fin 4)), F.card = 8 ∧ (∀ S ∈ F, ¬ ({0,1} : Finset (Fin 4)) ⊆ S ∧ ¬ S ⊆ ({0,1} : Finset (Fin 4))) ∧ (F.shatterer ∪ F.shatterer.image compl).card = 14
Source
Counterexample to a proposed unrestricted shattered-orbit inequality while studying arXiv:2611.12199, Conjecture 4.3.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The theorem establishes the existence of the desired family by exhibiting an explicit witness, `op1370_arbitrary_orbit_family`, consisting of eight subsets of {0, 1, 2, 3}. All three required properties—that the family has cardinality 8, that each of its elements is incomparable to {0, 1}, and that the union of its shattered sets with their complements has size 14 (occupying 7 complementary orbits)—are finite decidable propositions verified directly by Lean's kernel decision procedure.

  1. The family `op1370_arbitrary_orbit_family` satisfies all required conditions: it contains 8 subsets of `Fin 4`, every member is incomparable with `{0, 1}` under inclusion, and the union of its shattered sets with their complements has cardinality 14. automation

    The existential statement is witnessed by the explicit candidate family `op1370_arbitrary_orbit_family`. The three resulting goals are then discharged by kernel computation (`decide +kernel`): verifying that the family has 8 distinct elements, checking that none of the 8 members contains or is contained in `{0, 1}`, and computing the collection of shattered sets (namely ∅, {0}, {1}, {2}, {3}, {0, 2}, {1, 2}, and {1, 3}) and verifying that their union with their complements has exactly 14 elements (representing 7 complementary orbits).

    line 7

    uses op1370_arbitrary_orbit_family

      refine ⟨op1370_arbitrary_orbit_family, ?_, ?_, ?_⟩ <;> decide +kernel
op1370_arbitrary_orbit_family
the explicit family of eight subsets of {0, 1, 2, 3}, defined as {{2}, {1, 2}, {3}, {0, 3}, {1, 3}, {2, 3}, {0, 2, 3}, {1, 2, 3}}

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 1000000set_option maxRecDepth 8192def op1370_arbitrary_orbit_family : Finset (Finset (Fin 4)) := {{2}, {1,2}, {3}, {0,3}, {1,3}, {2,3}, {0,2,3}, {1,2,3}}theorem op_1370_unrestricted_shattered_orbits_counterexample : ∃ F : Finset (Finset (Fin 4)), F.card = 8 ∧ (∀ S ∈ F, ¬ ({0,1} : Finset (Fin 4)) ⊆ S ∧ ¬ S ⊆ ({0,1} : Finset (Fin 4))) ∧ (F.shatterer ∪ F.shatterer.image compl).card = 14 := by  refine ⟨op1370_arbitrary_orbit_family, ?_, ?_, ?_⟩ <;> decide +kernel
See it in the graphDiscuss this resultChallenge it