AFTD Auto-Formalizing Theoretical Domains

op_1370_no_private_stability_sharp_six

theoremverified

There are three nonempty uncomplemented mutually strongly incomparable families on six elements such that every element appears in sets in two different families, every element is absent from sets in two different families, and the sum of their sizes is 30.

Statement

theorem op_1370_no_private_stability_sharp_six : ∃ 𝒜 : Fin 3 → Finset (Finset (Fin 6)), (∀ i, (𝒜 i).Nonempty) ∧ (∀ i, is_uncomplemented (𝒜 i)) ∧ strongly_incomparable 𝒜 ∧ (∀ x, ∃ i j : Fin 3, i ≠ j ∧ (∃ S ∈ 𝒜 i, x ∈ S) ∧ (∃ T ∈ 𝒜 j, x ∈ T)) ∧ (∀ x, ∃ i j : Fin 3, i ≠ j ∧ (∃ S ∈ 𝒜 i, x ∉ S) ∧ (∃ T ∈ 𝒜 j, x ∉ T)) ∧ (∑ i, (𝒜 i).card) = 30
Source
An exact construction for the proposed no-private stability strengthening of 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 theorem is proved by constructing an explicit triple of set families on a 6-element ground set and verifying all six required conditions by finite computation. The three families have sizes 13, 1, and 16, which sum to 30. Kernel evaluation (`decide +kernel`) verifies that each family is nonempty, that no family contains complementary sets, that no set in one family is contained in a set from another family, and that every ground element both appears in and is absent from sets in at least two distinct families.

  1. Each of the three families is nonempty.

    Direct kernel evaluation (`decide +kernel`) checks that each of the three explicitly defined families has at least one element; in fact, their sizes are 13, 1, and 16.

    line 8

    lemma op1370_sharp6_nonempty : ∀ i, (op1370_sharp6_families i).Nonempty := by decide +kernel
  2. Each of the three families is uncomplemented.

    Unfolding the definition of `is_uncomplemented` reduces the goal to checking that for every family and every member set $A$, the complement $A^c$ is not in that family. This finite condition is verified by kernel computation (`decide +kernel`).

    lines 9–11

    lemma op1370_sharp6_unc : ∀ i, is_uncomplemented (op1370_sharp6_families i) := by
      unfold is_uncomplemented
      decide +kernel
  3. The three families are mutually strongly incomparable.

    Unfolding `strongly_incomparable` reduces the goal to checking that for any two distinct families $i \neq j$, no set in family $i$ is a subset of any set in family $j$. This condition is verified by exhaustive kernel evaluation (`decide +kernel`).

    lines 12–14

    lemma op1370_sharp6_inc : strongly_incomparable op1370_sharp6_families := by
      unfold strongly_incomparable
      decide +kernel
  4. Every element of the ground set appears in sets in at least two different families.

    For each of the six elements, kernel evaluation (`decide +kernel`) verifies the existence of two distinct families that each contain a set holding the element.

    line 15

    lemma op1370_sharp6_pos : ∀ x : Fin 6, ∃ i j : Fin 3, i ≠ j ∧ (∃ S ∈ op1370_sharp6_families i, x ∈ S) ∧ (∃ T ∈ op1370_sharp6_families j, x ∈ T) := by decide +kernel
  5. Every element of the ground set is absent from sets in at least two different families.

    For each of the six elements, kernel evaluation (`decide +kernel`) verifies the existence of two distinct families that each contain a set not holding the element.

    line 16

    lemma op1370_sharp6_neg : ∀ x : Fin 6, ∃ i j : Fin 3, i ≠ j ∧ (∃ S ∈ op1370_sharp6_families i, x ∉ S) ∧ (∃ T ∈ op1370_sharp6_families j, x ∉ T) := by decide +kernel
  6. The sum of the sizes of the three families is 30.

    Kernel evaluation computes the cardinalities of the three families (13, 1, and 16) and verifies that their sum equals 30.

    line 17

    lemma op1370_sharp6_card : (∑ i, (op1370_sharp6_families i).card) = 30 := by decide +kernel
  7. There exists a triple of families on six elements satisfying all required conditions.

    The existential goal is closed by supplying the explicit family triple `op1370_sharp6_families` along with the six proofs established in the preceding lemmas: nonemptiness, uncomplementedness, strong incomparability, positive coverage, negative coverage, and total cardinality.

    lines 19–20

    uses op1370_sharp6_families, op1370_sharp6_nonempty, op1370_sharp6_unc, op1370_sharp6_inc, op1370_sharp6_pos, op1370_sharp6_neg, op1370_sharp6_card

    theorem op_1370_no_private_stability_sharp_six : ∃ 𝒜 : Fin 3 → Finset (Finset (Fin 6)), (∀ i, (𝒜 i).Nonempty) ∧ (∀ i, is_uncomplemented (𝒜 i)) ∧ strongly_incomparable 𝒜 ∧ (∀ x, ∃ i j : Fin 3, i ≠ j ∧ (∃ S ∈ 𝒜 i, x ∈ S) ∧ (∃ T ∈ 𝒜 j, x ∈ T)) ∧ (∀ x, ∃ i j : Fin 3, i ≠ j ∧ (∃ S ∈ 𝒜 i, x ∉ S) ∧ (∃ T ∈ 𝒜 j, x ∉ T)) ∧ (∑ i, (𝒜 i).card) = 30 := by
      exact ⟨op1370_sharp6_families, op1370_sharp6_nonempty, op1370_sharp6_unc, op1370_sharp6_inc, op1370_sharp6_pos, op1370_sharp6_neg, op1370_sharp6_card⟩
op1370_sharp6_families
The explicit triple of families of subsets of a 6-element ground set.
op1370_sharp6_nonempty
Each of the three families in `op1370_sharp6_families` contains at least one set.
op1370_sharp6_unc
Each of the three families is uncomplemented: no family contains both a set and its complement.
op1370_sharp6_inc
The three families are mutually strongly incomparable: no set in one family is a subset of any set in another family.
op1370_sharp6_pos
Every element of the ground set belongs to at least one set in each of two distinct families.
op1370_sharp6_neg
Every element of the ground set is absent from at least one set in each of two distinct families.
op1370_sharp6_card
The sum of the cardinalities of the three families is 30.

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 2000000set_option maxRecDepth 8192def op1370_sharp6_f0 : Finset (Finset (Fin 6)) := {{0, 1}, {0, 1, 2}, {0, 1, 3}, {0, 1, 4}, {0, 5}, {0, 1, 5}, {0, 2, 5}, {1, 2, 5}, {0, 1, 2, 5}, {0, 3, 5}, {0, 4, 5}, {1, 4, 5}, {0, 1, 4, 5}}def op1370_sharp6_f1 : Finset (Finset (Fin 6)) := {{1, 3, 5}}def op1370_sharp6_f2 : Finset (Finset (Fin 6)) := {{2, 3}, {0, 2, 3}, {1, 2, 3}, {2, 4}, {0, 2, 4}, {1, 2, 4}, {3, 4}, {0, 3, 4}, {1, 3, 4}, {2, 3, 4}, {0, 2, 3, 4}, {1, 2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}, {2, 3, 4, 5}}def op1370_sharp6_families : Fin 3 → Finset (Finset (Fin 6)) := ![op1370_sharp6_f0, op1370_sharp6_f1, op1370_sharp6_f2]lemma op1370_sharp6_nonempty : ∀ i, (op1370_sharp6_families i).Nonempty := by decide +kernellemma op1370_sharp6_unc : ∀ i, is_uncomplemented (op1370_sharp6_families i) := by  unfold is_uncomplemented  decide +kernellemma op1370_sharp6_inc : strongly_incomparable op1370_sharp6_families := by  unfold strongly_incomparable  decide +kernellemma op1370_sharp6_pos : ∀ x : Fin 6, ∃ i j : Fin 3, i ≠ j ∧ (∃ S ∈ op1370_sharp6_families i, x ∈ S) ∧ (∃ T ∈ op1370_sharp6_families j, x ∈ T) := by decide +kernellemma op1370_sharp6_neg : ∀ x : Fin 6, ∃ i j : Fin 3, i ≠ j ∧ (∃ S ∈ op1370_sharp6_families i, x ∉ S) ∧ (∃ T ∈ op1370_sharp6_families j, x ∉ T) := by decide +kernellemma op1370_sharp6_card : (∑ i, (op1370_sharp6_families i).card) = 30 := by decide +kerneltheorem op_1370_no_private_stability_sharp_six : ∃ 𝒜 : Fin 3 → Finset (Finset (Fin 6)), (∀ i, (𝒜 i).Nonempty) ∧ (∀ i, is_uncomplemented (𝒜 i)) ∧ strongly_incomparable 𝒜 ∧ (∀ x, ∃ i j : Fin 3, i ≠ j ∧ (∃ S ∈ 𝒜 i, x ∈ S) ∧ (∃ T ∈ 𝒜 j, x ∈ T)) ∧ (∀ x, ∃ i j : Fin 3, i ≠ j ∧ (∃ S ∈ 𝒜 i, x ∉ S) ∧ (∃ T ∈ 𝒜 j, x ∉ T)) ∧ (∑ i, (𝒜 i).card) = 30 := by  exact ⟨op1370_sharp6_families, op1370_sharp6_nonempty, op1370_sharp6_unc, op1370_sharp6_inc, op1370_sharp6_pos, op1370_sharp6_neg, op1370_sharp6_card⟩
See it in the graphDiscuss this resultChallenge it