AFTD Auto-Formalizing Theoretical Domains

op_1370_private_without_uncomplemented_counterexample

theoremverified

There are three nonempty mutually strongly incomparable families of subsets of Fin 4 for which element 0 appears only in the first family, the total size is eight, and the first family contains a complementary pair. Thus the private-element bound fails if uncomplementedness of the exceptional family is removed.

Statement

theorem op_1370_private_without_uncomplemented_counterexample : ∃ 𝒜 : Fin 3 → Finset (Finset (Fin 4)), (∀ i, (𝒜 i).Nonempty) ∧ strongly_incomparable 𝒜 ∧ (∀ j : Fin 3, j ≠ 0 → ∀ S ∈ 𝒜 j, (0 : Fin 4) ∉ S) ∧ (∑ i, (𝒜 i).card) = 8 ∧ ¬ is_uncomplemented (𝒜 0)
Source
Counterexample to dropping an assumption of op_1370_private_element_bound, related to 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 exhibiting an explicit counterexample: a triple of families of subsets of {0, 1, 2, 3} given by 𝒜₀ = {{0}, {0,1}, {0,2}, {0,3}, {2,3}, {0,2,3}}, 𝒜₁ = {{1,2}}, and 𝒜₂ = {{1,3}}. The proof supplies this witness and verifies each of the five required properties—nonemptiness, mutual strong incomparability, privacy of element 0 to 𝒜₀, total size 8, and the presence of the complementary pair {0,1} and {2,3} in 𝒜₀—by finite kernel evaluation.

  1. We instantiate the existential quantifier with the candidate triple of families 𝒜₀, 𝒜₁, 𝒜₂.

    To prove existence, we provide the concrete witness op1370_private_unc_families consisting of 𝒜₀ = {{0}, {0,1}, {0,2}, {0,3}, {2,3}, {0,2,3}}, 𝒜₁ = {{1,2}}, and 𝒜₂ = {{1,3}}. This reduces the theorem to five verification goals.

    line 10

      refine ⟨op1370_private_unc_families, ?_, ?_, ?_, ?_, ?_⟩
  2. Each of the three families is nonempty. automation

    The families have sizes 6, 1, and 1, respectively, so none is empty; this finite check is verified by kernel evaluation.

    line 11

      · decide +kernel
  3. The three families are mutually strongly incomparable: no set in one family is a subset of any set in another family. automation

    We unfold the definition of strongly_incomparable and verify by exhaustive finite comparison that no set from 𝒜ᵢ is contained in any set from 𝒜ⱼ for i ≠ j.

    line 12

    uses strongly_incomparable

      · unfold strongly_incomparable; decide +kernel
  4. The element 0 is private to 𝒜₀: it does not appear in any set belonging to 𝒜₁ or 𝒜₂. automation

    The sets in 𝒜₁ and 𝒜₂ are {1, 2} and {1, 3}, neither of which contains 0; kernel evaluation checks all elements of both families.

    line 13

      · decide +kernel
  5. The total number of sets across all three families is eight. automation

    The sizes are |𝒜₀| = 6, |𝒜₁| = 1, and |𝒜₂| = 1, giving 6 + 1 + 1 = 8, verified by kernel computation.

    line 14

      · decide +kernel
  6. The family 𝒜₀ contains a complementary pair of sets, so it is not uncomplemented. automation

    We unfold the definition of is_uncomplemented; kernel evaluation confirms that 𝒜₀ fails this condition because both {0, 1} and its complement in Fin 4, namely {2, 3}, belong to 𝒜₀.

    line 15

    uses is_uncomplemented

      · unfold is_uncomplemented; decide +kernel
strongly_incomparable
A collection of families of sets is strongly incomparable if for any distinct indices i ≠ j, no set in the i-th family is a subset of any set in the j-th family.
is_uncomplemented
A family of sets on a finite universe is uncomplemented if for every set A in the family, its complement Aᶜ is not in 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 1000000set_option maxRecDepth 8192def op1370_private_unc_f0 : Finset (Finset (Fin 4)) := {{0}, {0,1}, {0,2}, {0,3}, {2,3}, {0,2,3}}def op1370_private_unc_f1 : Finset (Finset (Fin 4)) := {{1,2}}def op1370_private_unc_f2 : Finset (Finset (Fin 4)) := {{1,3}}def op1370_private_unc_families : Fin 3 → Finset (Finset (Fin 4)) := ![op1370_private_unc_f0, op1370_private_unc_f1, op1370_private_unc_f2]theorem op_1370_private_without_uncomplemented_counterexample : ∃ 𝒜 : Fin 3 → Finset (Finset (Fin 4)), (∀ i, (𝒜 i).Nonempty) ∧ strongly_incomparable 𝒜 ∧ (∀ j : Fin 3, j ≠ 0 → ∀ S ∈ 𝒜 j, (0 : Fin 4) ∉ S) ∧ (∑ i, (𝒜 i).card) = 8 ∧ ¬ is_uncomplemented (𝒜 0) := by  refine ⟨op1370_private_unc_families, ?_, ?_, ?_, ?_, ?_⟩  · decide +kernel  · unfold strongly_incomparable; decide +kernel  · decide +kernel  · decide +kernel  · unfold is_uncomplemented; decide +kernel
See it in the graphDiscuss this resultChallenge it