op1370_split_biintersecting_shatterer_shadow_counterexample
There are nonempty strongly cross-incomparable families F and G of subsets of Fin 6 whose union is both intersecting and co-intersecting and is nonconstant in every coordinate, together with a set R shattered by F∪G, such that R is not simultaneously contained in a member of F∪G and disjoint from a member of G, and R is not simultaneously disjoint from a member of F∪G and contained in a member of F.
Statement
theorem op1370_split_biintersecting_shatterer_shadow_counterexample : ∃ F G : Finset (Finset (Fin 6)), ∃ R : Finset (Fin 6), F.Nonempty ∧ G.Nonempty ∧ (∀ A ∈ F, ∀ B ∈ G, ¬ A ⊆ B ∧ ¬ B ⊆ A) ∧ (∀ A ∈ F ∪ G, ∀ B ∈ F ∪ G, (A ∩ B).Nonempty ∧ A ∪ B ≠ Finset.univ) ∧ (∀ x : Fin 6, (∃ A ∈ F ∪ G, x ∈ A) ∧ (∃ B ∈ F ∪ G, x ∉ B)) ∧ R ∈ (F ∪ G).shatterer ∧ ¬ ((∃ A ∈ F ∪ G, R ⊆ A) ∧ (∃ B ∈ G, Disjoint R B)) ∧ ¬ ((∃ A ∈ F ∪ G, Disjoint R A) ∧ (∃ B ∈ F, R ⊆ B))- Source
- A counterexample to a witness-shadow coverage shortcut toward OP-1370, arXiv:2611.12199 Conjecture 4.3.
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The theorem is established by providing explicit finite witnesses on the 6-element universe: $F = \{\{0, 1, 3\}\}$, $G = \{\{0, 2, 4\}, \{1, 2, 5\}\}$, and $R = \{2\}$. All eight required properties—nonemptiness, cross-incomparability, intersecting and co-intersecting union, coordinate nonconstancy, shattering of $R$, and the two negation conditions—are finite and decidable, so they are verified by computational reflection using `decide +kernel`.
The explicit families $F = \{\{0, 1, 3\}\}$, $G = \{\{0, 2, 4\}, \{1, 2, 5\}\}$, and the subset $R = \{2\}$ of $\mathrm{Fin}\ 6$ satisfy all eight conditions of the theorem. automation
We instantiate the existential quantifiers with the families $F = \{\{0, 1, 3\}\}$, $G = \{\{0, 2, 4\}, \{1, 2, 5\}\}$, and the candidate set $R = \{2\}$ over the universe $\mathrm{Fin}\ 6 = \{0, 1, 2, 3, 4, 5\}$. This leaves eight finite subgoals: 1. $F$ is nonempty (it contains $\{0, 1, 3\}$). 2. $G$ is nonempty (it contains two sets). 3. $F$ and $G$ are strongly cross-incomparable: $\{0, 1, 3\}$ is incomparable with $\{0, 2, 4\}$ (since $1 \notin \{0, 2, 4\}$ and $2 \notin \{0, 1, 3\}$) and with $\{1, 2, 5\}$ (since $0 \notin \{1, 2, 5\}$ and $2 \notin \{0, 1, 3\}$). 4. $F \cup G$ is intersecting and co-intersecting: any two of the three sets intersect (at 0, 1, or 2), and no union of two sets equals the entire 6-element universe. 5. Every element of $\mathrm{Fin}\ 6$ is covered by some set and omitted by some set in $F \cup G$. 6. $R = \{2\}$ is shattered by $F \cup G$, as its two subsets $\emptyset$ and $\{2\}$ are realized as $\{0, 1, 3\} \cap \{2\}$ and $\{0, 2, 4\} \cap \{2\}$. 7. The first conjunction fails because no member of $G$ is disjoint from $R$ (both contain 2). 8. The second conjunction fails because no member of $F$ contains $R$ ($2 \notin \{0, 1, 3\}$). Each of these finite decidable statements is verified by kernel evaluation.
refine ⟨{{0, 1, 3}}, {{0, 2, 4}, {1, 2, 5}}, {2}, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> decide +kernel
- All eight verification subgoals are discharged by finite exhaustive evaluation (`decide +kernel`), so the formal proof contains no manual deduction 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.
set_option maxHeartbeats 2000000set_option maxRecDepth 8192theorem op1370_split_biintersecting_shatterer_shadow_counterexample : ∃ F G : Finset (Finset (Fin 6)), ∃ R : Finset (Fin 6), F.Nonempty ∧ G.Nonempty ∧ (∀ A ∈ F, ∀ B ∈ G, ¬ A ⊆ B ∧ ¬ B ⊆ A) ∧ (∀ A ∈ F ∪ G, ∀ B ∈ F ∪ G, (A ∩ B).Nonempty ∧ A ∪ B ≠ Finset.univ) ∧ (∀ x : Fin 6, (∃ A ∈ F ∪ G, x ∈ A) ∧ (∃ B ∈ F ∪ G, x ∉ B)) ∧ R ∈ (F ∪ G).shatterer ∧ ¬ ((∃ A ∈ F ∪ G, R ⊆ A) ∧ (∃ B ∈ G, Disjoint R B)) ∧ ¬ ((∃ A ∈ F ∪ G, Disjoint R A) ∧ (∃ B ∈ F, R ⊆ B)) := by refine ⟨{{0, 1, 3}}, {{0, 2, 4}, {1, 2, 5}}, {2}, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> decide +kernel