op_1370_twoblock_nonprivate_equality_counterexample
There exist two strongly incomparable uncomplemented families of subsets of a six-element set, each varying at every coordinate, whose total size is 32. Equality for two families therefore does not force a coordinate to be uniformly present or absent in one of the families.
Statement
theorem op_1370_twoblock_nonprivate_equality_counterexample : ∃ 𝒜 : Fin 2 → Finset (Finset (Fin 6)),
(∀ i, is_uncomplemented (𝒜 i)) ∧ strongly_incomparable 𝒜 ∧
(∀ i, ∀ x, (∃ S ∈ 𝒜 i, x ∈ S) ∧ (∃ T ∈ 𝒜 i, x ∉ T)) ∧
(∑ i, (𝒜 i).card = 2^5)- Related work
- Counterexample to a proposed two-family equality-structure route for OP-1370, arXiv:2611.12199, Conjecture 4.3.
- Verified
- 16 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…
Read back from the Lean
There exists a pair of families of subsets of a 6-element set (represented as a function $\mathcal{A} : \mathrm{Fin}\ 2 \to \mathrm{Finset} (\mathrm{Finset} (\mathrm{Fin}\ 6))$) such that: 1. For each $i \in \mathrm{Fin}\ 2$, $\mathcal{A}_i$ is uncomplemented (no set in $\mathcal{A}_i$ has its complement also in $\mathcal{A}_i$); 2. $\mathcal{A}$ is strongly incomparable (for distinct indices $i \neq j$, no set in $\mathcal{A}_i$ is a subset of any set in $\mathcal{A}_j$); 3. For each $i \in \mathrm{Fin}\ 2$ and each element $x \in \mathrm{Fin}\ 6$, there exists some $S \in \mathcal{A}_i$ containing $x$ and some $T \in \mathcal{A}_i$ not containing $x$; and 4. The sum of the sizes of the two families, $\sum_{i \in \mathrm{Fin}\ 2} |\mathcal{A}_i|$, equals $2^5 = 32$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem proves the existence of two strongly incomparable uncomplemented families of subsets of a six-element set, each varying at every coordinate, with total size $2^5 = 32$. This provides a counterexample to the conjecture that equality in the size bound forces some coordinate to be uniformly present or absent (private) in either family. The proof is constructive: two explicit families of 16 subsets each are defined, their uncomplementedness, strong incomparability, coordinate variation, and cardinality sum are each verified by kernel evaluation (`decide +kernel`), and these facts are packaged together to witness the existential statement.
The family `op1370_twoblock_eq_a` is uncomplemented.
Unfolding the definition `is_uncomplemented` produces the goal that no subset in the family has its complement also in the family. Because `op1370_twoblock_eq_a` consists of 16 explicit subsets of a six-element universe, this finite check is evaluated directly in the kernel via `decide +kernel`.
lemma op1370_twoblock_eq_a_uncomp : is_uncomplemented op1370_twoblock_eq_a := by unfold is_uncomplemented; decide +kernel
The family `op1370_twoblock_eq_b` is uncomplemented.
Similarly, unfolding `is_uncomplemented` for `op1370_twoblock_eq_b` requires that no member has its complement in the family, which the kernel evaluates and confirms via `decide +kernel` across all 16 members.
lemma op1370_twoblock_eq_b_uncomp : is_uncomplemented op1370_twoblock_eq_b := by unfold is_uncomplemented; decide +kernel
Every family in the pair `op1370_twoblock_eq_f` is uncomplemented.
Introducing the index $i : \\mathrm{Fin}\\ 2$ and performing a case split on $i$ reduces the goal to $i = 0$ and $i = 1$. The simplifier rewrites `op1370_twoblock_eq_f 0` to `op1370_twoblock_eq_a` and `op1370_twoblock_eq_f 1` to `op1370_twoblock_eq_b`, closing the respective goals using `op1370_twoblock_eq_a_uncomp` and `op1370_twoblock_eq_b_uncomp`.
uses
op1370_twoblock_eq_a_uncomp,op1370_twoblock_eq_b_uncomplemma op1370_twoblock_eq_f_uncomp : ∀ i, is_uncomplemented (op1370_twoblock_eq_f i) := by intro i; fin_cases i <;> simp [op1370_twoblock_eq_f, op1370_twoblock_eq_a_uncomp, op1370_twoblock_eq_b_uncomp]
The pair of families `op1370_twoblock_eq_f` is strongly incomparable.
Unfolding `strongly_incomparable` transforms the goal into showing that for distinct indices $i \\ne j$, no set in family $i$ is a subset of any set in family $j$. This requires verifying that $A \\not\\subseteq B$ for all $A \\in \\mathcal{A}_0, B \\in \\mathcal{A}_1$ and vice versa, which is checked by exhaustive kernel computation via `decide +kernel`.
lemma op1370_twoblock_eq_f_incomp : strongly_incomparable op1370_twoblock_eq_f := by unfold strongly_incomparable decide +kernel
Every coordinate varies in each family.
The goal requires that for each family $i \\in \\{0, 1\\}$ and each coordinate $x \\in \\{0, \\dots, 5\\}$, there exists a set containing $x$ and another set omitting $x$. Kernel evaluation via `decide +kernel` exhaustively verifies the existence of these witnesses across all coordinates and both families.
lemma op1370_twoblock_eq_f_vary : ∀ i : Fin 2, ∀ x : Fin 6, (∃ S ∈ op1370_twoblock_eq_f i, x ∈ S) ∧ (∃ T ∈ op1370_twoblock_eq_f i, x ∉ T) := by decide +kernel
The total size of the two families is 32.
The sum of the sizes of the two families, $16 + 16 = 32 = 2^5$, is verified directly by kernel computation via `decide +kernel`.
lemma op1370_twoblock_eq_f_card : ∑ i, (op1370_twoblock_eq_f i).card = 2^5 := by decide +kernel
There exists a pair of strongly incomparable uncomplemented families of subsets of a six-element set, each varying at every coordinate, with total size 32.
The existential goal is witnessed directly by the pair of families `op1370_twoblock_eq_f`, assembling the four established properties (`op1370_twoblock_eq_f_uncomp`, `op1370_twoblock_eq_f_incomp`, `op1370_twoblock_eq_f_vary`, and `op1370_twoblock_eq_f_card`) into the required conjunction.
uses
op1370_twoblock_eq_f_uncomp,op1370_twoblock_eq_f_incomp,op1370_twoblock_eq_f_vary,op1370_twoblock_eq_f_cardtheorem op_1370_twoblock_nonprivate_equality_counterexample : ∃ 𝒜 : Fin 2 → Finset (Finset (Fin 6)), (∀ i, is_uncomplemented (𝒜 i)) ∧ strongly_incomparable 𝒜 ∧ (∀ i, ∀ x, (∃ S ∈ 𝒜 i, x ∈ S) ∧ (∃ T ∈ 𝒜 i, x ∉ T)) ∧ (∑ i, (𝒜 i).card = 2^5) := by exact ⟨op1370_twoblock_eq_f, op1370_twoblock_eq_f_uncomp, op1370_twoblock_eq_f_incomp, op1370_twoblock_eq_f_vary, op1370_twoblock_eq_f_card⟩
op1370_twoblock_eq_a_uncomp- The family `op1370_twoblock_eq_a` is uncomplemented: no subset in the family has its complement also in the family.
op1370_twoblock_eq_b_uncomp- The family `op1370_twoblock_eq_b` is uncomplemented: no subset in the family has its complement also in the family.
op1370_twoblock_eq_f_uncomp- For both indices $i \\in \\{0, 1\\}$, the family `op1370_twoblock_eq_f i` is uncomplemented.
op1370_twoblock_eq_f_incomp- The two families in `op1370_twoblock_eq_f` are strongly incomparable: no set in one family is a subset of any set in the other.
op1370_twoblock_eq_f_vary- For each family $i \\in \\{0, 1\\}$ and every coordinate $x \\in \\{0, \\dots, 5\\}$, there is a set in the family containing $x$ and a set omitting $x$.
op1370_twoblock_eq_f_card- The sum of the cardinalities of the two families in `op1370_twoblock_eq_f` is $2^5 = 32$.
- The core properties of the two families—uncomplementedness, strong incomparability, coordinate variation, and cardinality sum—are established by exhaustive boolean computation in the Lean kernel (`decide +kernel`) rather than by manual deductive 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 4000000set_option maxRecDepth 8192def op1370_twoblock_eq_a : Finset (Finset (Fin 6)) := {{0, 1}, {0, 1, 2}, {0, 1, 3}, {0, 4}, {1, 4}, {0, 1, 4}, {0, 2, 4}, {1, 2, 4}, {0, 1, 2, 4}, {0, 3, 4}, {1, 3, 4}, {0, 1, 3, 4}, {0, 1, 5}, {0, 4, 5}, {1, 4, 5}, {0, 1, 4, 5}}def op1370_twoblock_eq_b : Finset (Finset (Fin 6)) := {{2, 3}, {0, 2, 3}, {1, 2, 3}, {2, 3, 4}, {2, 5}, {0, 2, 5}, {1, 2, 5}, {3, 5}, {0, 3, 5}, {1, 3, 5}, {2, 3, 5}, {0, 2, 3, 5}, {1, 2, 3, 5}, {2, 4, 5}, {3, 4, 5}, {2, 3, 4, 5}}def op1370_twoblock_eq_f : Fin 2 → Finset (Finset (Fin 6)) := ![op1370_twoblock_eq_a, op1370_twoblock_eq_b]lemma op1370_twoblock_eq_a_uncomp : is_uncomplemented op1370_twoblock_eq_a := by unfold is_uncomplemented; decide +kernellemma op1370_twoblock_eq_b_uncomp : is_uncomplemented op1370_twoblock_eq_b := by unfold is_uncomplemented; decide +kernellemma op1370_twoblock_eq_f_uncomp : ∀ i, is_uncomplemented (op1370_twoblock_eq_f i) := by intro i; fin_cases i <;> simp [op1370_twoblock_eq_f, op1370_twoblock_eq_a_uncomp, op1370_twoblock_eq_b_uncomp]lemma op1370_twoblock_eq_f_incomp : strongly_incomparable op1370_twoblock_eq_f := by unfold strongly_incomparable decide +kernellemma op1370_twoblock_eq_f_vary : ∀ i : Fin 2, ∀ x : Fin 6, (∃ S ∈ op1370_twoblock_eq_f i, x ∈ S) ∧ (∃ T ∈ op1370_twoblock_eq_f i, x ∉ T) := by decide +kernellemma op1370_twoblock_eq_f_card : ∑ i, (op1370_twoblock_eq_f i).card = 2^5 := by decide +kerneltheorem op_1370_twoblock_nonprivate_equality_counterexample : ∃ 𝒜 : Fin 2 → Finset (Finset (Fin 6)), (∀ i, is_uncomplemented (𝒜 i)) ∧ strongly_incomparable 𝒜 ∧ (∀ i, ∀ x, (∃ S ∈ 𝒜 i, x ∈ S) ∧ (∃ T ∈ 𝒜 i, x ∉ T)) ∧ (∑ i, (𝒜 i).card = 2^5) := by exact ⟨op1370_twoblock_eq_f, op1370_twoblock_eq_f_uncomp, op1370_twoblock_eq_f_incomp, op1370_twoblock_eq_f_vary, op1370_twoblock_eq_f_card⟩