op_1370_unrestricted_shattered_orbits_counterexample
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.
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).
uses
op1370_arbitrary_orbit_familyrefine ⟨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}}
- The three conjuncts (cardinality 8, incomparability with {0, 1}, and the cardinality of the shattered sets together with their complements being 14) are verified entirely by Lean's kernel decision procedure (`decide +kernel`) via finite exhaustive computation.
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 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