op_1370_shattered_orbit_without_uncomplemented_counterexample
There exist three nonempty strongly incomparable families on four elements such that the first has six members, the second has one, and the orbit closure of the sets shattered by their union has cardinality fourteen; the first family contains a complementary pair. Consequently, the number of shattered complementary orbits can equal the sum of the first two family sizes if their uncomplementedness is omitted.
Statement
theorem op_1370_shattered_orbit_without_uncomplemented_counterexample : ∃ 𝒜 : Fin 3 → Finset (Finset (Fin 4)), (∀ i, (𝒜 i).Nonempty) ∧ strongly_incomparable 𝒜 ∧ (𝒜 0).card = 6 ∧ (𝒜 1).card = 1 ∧ (((𝒜 0 ∪ 𝒜 1).shatterer ∪ ((𝒜 0 ∪ 𝒜 1).shatterer.image compl)).card = 14) ∧ ¬ is_uncomplemented (𝒜 0)- Source
- Counterexample to a proposed strengthening of the shattered-orbit route 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 alli j : ιwithi ≠ j, for all…
The proof, explained
The proof exhibits an explicit counterexample of three families of subsets of a 4-element set: 𝒜₀ containing six sets, and 𝒜₁ and 𝒜₂ each containing a single set. All conditions—nonemptiness, strong incomparability, the family cardinalities, the size of the shattered complementary orbit closure being fourteen, and the fact that 𝒜₀ contains a complementary pair {1, 2} and {0, 3}—are verified by finite exhaustive computation using Lean's kernel decision procedure (`decide +kernel`).
It suffices to verify the six conditions for the explicit three-family collection op1370_nouncomp_families.
We provide op1370_nouncomp_families as the witness for the existential quantifier. It consists of the three families 𝒜₀ = {{1, 2}, {3}, {0, 3}, {1, 3}, {2, 3}, {1, 2, 3}}, 𝒜₁ = {{0, 2}}, and 𝒜₂ = {{0, 1}} of subsets of Fin 4 = {0, 1, 2, 3}. This splits the goal into six concrete verification subgoals.
refine ⟨op1370_nouncomp_families, ?_, ?_, ?_, ?_, ?_, ?_⟩Each of the three families is nonempty. automation
The families 𝒜₀, 𝒜₁, and 𝒜₂ have 6, 1, and 1 elements respectively; none is empty. The kernel verifies this by finite evaluation.
· decide +kernelThe three families are strongly incomparable. automation
Unfolding strongly_incomparable, we must check that for any distinct indices i ≠ j, no set A ∈ 𝒜 i is a subset of any set B ∈ 𝒜 j. The kernel verifies all pairs across distinct families by direct evaluation.
uses
strongly_incomparable· unfold strongly_incomparable; decide +kernel
The first family has size 6 and the second has size 1. automation
Direct counting of the finite sets yields |𝒜₀| = 6 and |𝒜₁| = 1, each evaluated by the kernel.
· decide +kernel · decide +kernel
The complementary orbit closure of the family of sets shattered by 𝒜₀ ∪ 𝒜₁ has cardinality 14. automation
A subset of {0, 1, 2, 3} is shattered by 𝒜₀ ∪ 𝒜₁ if all of its subsets are obtained as traces of members of 𝒜₀ ∪ 𝒜₁. The union of these shattered sets together with their complements in {0, 1, 2, 3} yields a collection of 14 subsets (out of 16 in the powerset), which the kernel computes and verifies.
· decide +kernelThe family 𝒜₀ is not uncomplemented. automation
Unfolding is_uncomplemented, the condition requires that no set in 𝒜₀ has its complement in 𝒜₀. However, {1, 2} ∈ 𝒜₀ and its complement {0, 3} is also in 𝒜₀, so 𝒜₀ contains a complementary pair; the kernel confirms this violation.
uses
is_uncomplemented· unfold is_uncomplemented; decide +kernel
strongly_incomparable- A collection of families of sets is strongly incomparable if no set in one family is a subset of any set in another family.
is_uncomplemented- A family of sets is uncomplemented if no member's complement (in the ambient universe) belongs to the family.
- All verification subgoals (lines 11–16) are closed by `decide +kernel`, which delegates the finite combinatorial checking to Lean's kernel evaluator rather than producing symbolic deduction steps.
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 1500000set_option maxRecDepth 8192def op1370_nouncomp_f0 : Finset (Finset (Fin 4)) := {{1,2}, {3}, {0,3}, {1,3}, {2,3}, {1,2,3}}def op1370_nouncomp_f1 : Finset (Finset (Fin 4)) := {{0,2}}def op1370_nouncomp_f2 : Finset (Finset (Fin 4)) := {{0,1}}def op1370_nouncomp_families : Fin 3 → Finset (Finset (Fin 4)) := ![op1370_nouncomp_f0, op1370_nouncomp_f1, op1370_nouncomp_f2]theorem op_1370_shattered_orbit_without_uncomplemented_counterexample : ∃ 𝒜 : Fin 3 → Finset (Finset (Fin 4)), (∀ i, (𝒜 i).Nonempty) ∧ strongly_incomparable 𝒜 ∧ (𝒜 0).card = 6 ∧ (𝒜 1).card = 1 ∧ (((𝒜 0 ∪ 𝒜 1).shatterer ∪ ((𝒜 0 ∪ 𝒜 1).shatterer.image compl)).card = 14) ∧ ¬ is_uncomplemented (𝒜 0) := by refine ⟨op1370_nouncomp_families, ?_, ?_, ?_, ?_, ?_, ?_⟩ · decide +kernel · unfold strongly_incomparable; decide +kernel · decide +kernel · decide +kernel · decide +kernel · unfold is_uncomplemented; decide +kernel