op_1370_private_without_uncomplemented_counterexample
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 alli j : ιwithi ≠ 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.
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.
refine ⟨op1370_private_unc_families, ?_, ?_, ?_, ?_, ?_⟩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.
· decide +kernelThe 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.
uses
strongly_incomparable· unfold strongly_incomparable; decide +kernel
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.
· decide +kernelThe 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.
· decide +kernelThe 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 𝒜₀.
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.
- All five conditions on the explicit families on the universe {0, 1, 2, 3} are verified by the kernel decision procedure (`decide +kernel`). In particular, the pair witnessing that 𝒜₀ is not uncomplemented is {0, 1} and its complement {2, 3}.
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_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