AFTD Auto-Formalizing Theoretical Domains

op1370_repaired_coordinate_witness_counterexample

theoremverifiedoriginal

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 all i j : ι with i ≠ 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
See it in the graphDiscuss this resultChallenge it