op1370_repaired_coordinate_witness_counterexample
There exist three nonempty uncomplemented mutually strongly incomparable families of subsets of Fin 6 such that, for every coordinate, some two distinct families contain sets including that coordinate and some two distinct families contain sets excluding it. Put x = 0 and V = Fin 6 with x removed. Every fiber below means an arbitrary subset R of V, whether or not R is present in a family. Call R a lower witness fiber if there are sets A and B in different families, both containing x, such that R is contained in (A intersect B) with x removed. Call R an upper witness fiber if there are sets C and D in different families, both excluding x, such that C union D is contained in R. There is exactly one lower witness fiber and exactly one upper witness fiber. Call R doubled if both R and R union {x} are present in the union of the families. Exactly two fibers are doubled. For each doubled fiber R, at least one of V minus R and (V minus R) union {x} belongs to the union of the families.
Statement
theorem op1370_repaired_coordinate_witness_counterexample : ∃ 𝒜 : 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)) ∧ let x : Fin 6 := 0 let V : Finset (Fin 6) := Finset.univ.erase x let U := Finset.univ.biUnion 𝒜 let P := U.filter (fun S => x ∉ S) let Q := (U.filter (fun S => x ∈ S)).image (fun S => S.erase x) let low : Fin 3 → Finset (Finset (Fin 6)) := fun i => ((𝒜 i).filter (fun A => x ∈ A)).biUnion (fun A => (A.erase x).powerset) let high : Fin 3 → Finset (Finset (Fin 6)) := fun i => ((𝒜 i).filter (fun A => x ∉ A)).biUnion (fun A => (V \ A).powerset.image (fun B => A ∪ B)) let L := (low 0 ∩ low 1) ∪ (low 0 ∩ low 2) ∪ (low 1 ∩ low 2) let H := (high 0 ∩ high 1) ∪ (high 0 ∩ high 2) ∪ (high 1 ∩ high 2) L.card = 1 ∧ H.card = 1 ∧ (P ∩ Q).card = 2 ∧ (∀ S ∈ P ∩ Q, V \ S ∈ P ∪ Q)
- Related work
- A counterexample to the repaired fixed-coordinate witness-shadow counting route toward Conjecture 4.3 of arXiv:2611.12199.
- 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 family of three collections of subsets of Fin 6, $\mathcal{A} : \text{Fin } 3 \to \text{Finset } (\text{Finset } (\text{Fin } 6))$, satisfying all of the following conditions:
1. **Non-emptiness**: For every $i \in \text{Fin } 3$, $\mathcal{A}(i)$ is non-empty.
2. **Uncomplementedness**: For every $i \in \text{Fin } 3$ and every $A \in \mathcal{A}(i)$, the complement $A^c$ (relative to $\text{Fin } 6$) is not in $\mathcal{A}(i)$.
3. **Strong incomparability**: For all distinct $i, j \in \text{Fin } 3$, no set $A \in \mathcal{A}(i)$ is a subset of any set $B \in \mathcal{A}(j)$.
4. **Point-incidence across families**: For every element $x \in \text{Fin } 6$, there exist distinct indices $i, j \in \text{Fin } 3$ such that $x$ belongs to some set $S \in \mathcal{A}(i)$ and some set $T \in \mathcal{A}(j)$.
5. **Non-incidence across families**: For every element $x \in \text{Fin } 6$, there exist distinct indices $i, j \in \text{Fin } 3$ such that $x$ does not belong to some set $S \in \mathcal{A}(i)$ and does not belong to some set $T \in \mathcal{A}(j)$.
6. With the fixed coordinate $x = 0 \in \text{Fin } 6$, the universe $V = \text{Finset.univ} \setminus \{0\}$, the total collection $U = \bigcup_{i \in \text{Fin } 3} \mathcal{A}(i)$, and the sliced collections:
- $P = \{S \in U \mid 0 \notin S\}$,
- $Q = \{S \setminus \{0\} \mid S \in U, 0 \in S\}$,
- $\text{low}(i) = \bigcup_{A \in \mathcal{A}(i),\, 0 \in A} \mathcal{P}(A \setminus \{0\})$,
- $\text{high}(i) = \bigcup_{A \in \mathcal{A}(i),\, 0 \notin A} \{A \cup B \mid B \subseteq V \setminus A\}$,
- $L = (\text{low}(0) \cap \text{low}(1)) \cup (\text{low}(0) \cap \text{low}(2)) \cup (\text{low}(1) \cap \text{low}(2))$,
- $H = (\text{high}(0) \cap \text{high}(1)) \cup (\text{high}(0) \cap \text{high}(2)) \cup (\text{high}(1) \cap \text{high}(2))$,
it holds that:
- $|L| = 1$,
- $|H| = 1$,
- $|P \cap Q| = 2$, and
- For all $S \in P \cap Q$, $(V \setminus S) \in P \cup Q$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
set_option maxHeartbeats 3000000 set_option maxRecDepth 8192 theorem op1370_repaired_coordinate_witness_counterexample : ∃ 𝒜 : 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)) ∧ let x : Fin 6 := 0 let V : Finset (Fin 6) := Finset.univ.erase x let U := Finset.univ.biUnion 𝒜 let P := U.filter (fun S => x ∉ S) let Q := (U.filter (fun S => x ∈ S)).image (fun S => S.erase x) let low : Fin 3 → Finset (Finset (Fin 6)) := fun i => ((𝒜 i).filter (fun A => x ∈ A)).biUnion (fun A => (A.erase x).powerset) let high : Fin 3 → Finset (Finset (Fin 6)) := fun i => ((𝒜 i).filter (fun A => x ∉ A)).biUnion (fun A => (V \ A).powerset.image (fun B => A ∪ B)) let L := (low 0 ∩ low 1) ∪ (low 0 ∩ low 2) ∪ (low 1 ∩ low 2) let H := (high 0 ∩ high 1) ∪ (high 0 ∩ high 2) ∪ (high 1 ∩ high 2) L.card = 1 ∧ H.card = 1 ∧ (P ∩ Q).card = 2 ∧ (∀ S ∈ P ∩ Q, V \ S ∈ P ∪ Q) := by refine ⟨![{{1,2,5}, {1,2,3,5}, {1,2,4,5}}, {{0,1}, {0,2}, {0,1,2}}, {{3,4}, {0,3,4}, {3,4,5}, {0,3,4,5}}], ?_, ?_, ?_, ?_, ?_, ?_⟩ · decide +kernel · unfold is_uncomplemented decide +kernel · unfold strongly_incomparable decide +kernel · decide +kernel · decide +kernel · decide +kernel