AFTD Auto-Formalizing Theoretical Domains

op_1370_shattered_orbit_without_uncomplemented_counterexample

theoremverified

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 all i j : ι with i ≠ 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`).

  1. 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.

    line 10

      refine ⟨op1370_nouncomp_families, ?_, ?_, ?_, ?_, ?_, ?_⟩
  2. 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.

    line 11

      · decide +kernel
  3. The 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.

    line 12

    uses strongly_incomparable

      · unfold strongly_incomparable; decide +kernel
  4. 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.

    lines 13–14

      · decide +kernel
      · decide +kernel
  5. 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.

    line 15

      · decide +kernel
  6. The 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.

    line 16

    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.

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_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
See it in the graphDiscuss this resultChallenge it