op_1370_global_two_projection_holes_counterexample
There are four nonempty uncomplemented mutually strongly incomparable families on Fin 5 with both no-private incidence conditions at every element, but only two subsets of the other four elements are missing after erasing element 0 from their union.
Statement
theorem op_1370_global_two_projection_holes_counterexample : ∃ 𝒜 : Fin 4 → Finset (Finset (Fin 5)), (∀ i, (𝒜 i).Nonempty) ∧ (∀ i, is_uncomplemented (𝒜 i)) ∧ strongly_incomparable 𝒜 ∧ (∀ x, ∃ i j : Fin 4, i ≠ j ∧ (∃ S ∈ 𝒜 i, x ∈ S) ∧ (∃ T ∈ 𝒜 j, x ∈ T)) ∧ (∀ x, ∃ i j : Fin 4, i ≠ j ∧ (∃ S ∈ 𝒜 i, x ∉ S) ∧ (∃ T ∈ 𝒜 j, x ∉ T)) ∧ ((Finset.univ.biUnion 𝒜).image (fun S => S.erase (0 : Fin 5))).card = 14
- Source
- Counterexample to a proposed four-missing-projection-fibers strengthening 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
We construct an explicit counterexample of four families of subsets of $\{0, 1, 2, 3, 4\}$. Family $\mathcal{A}_0 = \{\{0, 1\}\}$ and family $\mathcal{A}_1 = \{\{2, 3, 4\}\}$ each contain a single set, while $\mathcal{A}_2$ contains the six sets formed by adding $1$ to any nonempty proper subset of $\{2, 3, 4\}$, and $\mathcal{A}_3$ symmetrically adds $0$. Each family is nonempty and uncomplemented, the four families are pairwise strongly incomparable, and every element of the ground set both belongs to and is omitted by sets in at least two distinct families. Projecting the union $\bigcup_{i=0}^3 \mathcal{A}_i$ by erasing element $0$ yields 14 distinct subsets of $\{1, 2, 3, 4\}$, leaving only two missing subsets. Lean's kernel verifies each condition by exhaustive finite evaluation, and the witness tuple completes the existential proof.
Each of the four families is nonempty. automation
The families $\mathcal{A}_0, \mathcal{A}_1, \mathcal{A}_2, \mathcal{A}_3$ have sizes 1, 1, 6, and 6 respectively. The kernel verifies that each family contains at least one set by direct finite evaluation.
lemma op1370_globalholes_ne : ∀ i, (op1370_globalholes_families i).Nonempty := by decide +kernel
Each of the four families is uncomplemented. automation
A family is uncomplemented if no member set has its complement in the same family. Unfolding `is_uncomplemented` reduces the goal to checking that for every $i \in \{0, 1, 2, 3\}$ and every set $A \in \mathcal{A}_i$, the complement $A^c = \{0, 1, 2, 3, 4\} \setminus A$ is not in $\mathcal{A}_i$. The kernel verifies this by exhaustive check.
unfold is_uncomplemented decide +kernel
The four families are pairwise strongly incomparable. automation
Strong incomparability requires that for any distinct $i \neq j$, no set $A \in \mathcal{A}_i$ is a subset of any set $B \in \mathcal{A}_j$. Unfolding `strongly_incomparable` reduces the goal to this condition over all pairs of sets, which the kernel checks exhaustively.
unfold strongly_incomparable decide +kernel
Every element of the ground set belongs to sets from at least two distinct families. automation
For each of the five ground set elements $x \in \{0, 1, 2, 3, 4\}$, there must exist two distinct families containing sets that contain $x$. The kernel establishes this by evaluating the existential statement over all five points.
lemma op1370_globalholes_pos : ∀ x : Fin 5, ∃ i j : Fin 4, i ≠ j ∧ (∃ S ∈ op1370_globalholes_families i, x ∈ S) ∧ (∃ T ∈ op1370_globalholes_families j, x ∈ T) := by decide +kernel
Every element of the ground set is absent from sets in at least two distinct families. automation
For each ground set element $x \in \{0, 1, 2, 3, 4\}$, there must exist two distinct families containing sets that omit $x$. The kernel verifies this existential property for all five elements by exhaustive check.
lemma op1370_globalholes_neg : ∀ x : Fin 5, ∃ i j : Fin 4, i ≠ j ∧ (∃ S ∈ op1370_globalholes_families i, x ∉ S) ∧ (∃ T ∈ op1370_globalholes_families j, x ∉ T) := by decide +kernel
Erasing element 0 from each set in the union of the four families yields exactly 14 distinct subsets. automation
Projecting each set in $\bigcup_{i=0}^3 \mathcal{A}_i$ by deleting element $0$ produces subsets of $\{1, 2, 3, 4\}$. Out of the $2^4 = 16$ possible subsets, exactly 14 appear (only $\emptyset$ and $\{1, 2, 3, 4\}$ are omitted), leaving just two projection holes. The kernel computes the union, applies the erasure map, and counts the cardinality of the resulting set.
lemma op1370_globalholes_card : ((Finset.univ.biUnion op1370_globalholes_families).image (fun S => S.erase (0 : Fin 5))).card = 14 := by decide +kernel
There exists a collection of four families satisfying all required conditions.
We provide `op1370_globalholes_families` as the existential witness, accompanied by the proofs of nonemptiness (`op1370_globalholes_ne`), uncomplementedness (`op1370_globalholes_unc`), strong incomparability (`op1370_globalholes_inc`), positive incidence (`op1370_globalholes_pos`), negative incidence (`op1370_globalholes_neg`), and projection cardinality (`op1370_globalholes_card`).
uses
op1370_globalholes_ne,op1370_globalholes_unc,op1370_globalholes_inc,op1370_globalholes_pos,op1370_globalholes_neg,op1370_globalholes_cardexact ⟨op1370_globalholes_families, op1370_globalholes_ne, op1370_globalholes_unc, op1370_globalholes_inc, op1370_globalholes_pos, op1370_globalholes_neg, op1370_globalholes_card⟩
op1370_globalholes_ne- Every family $\mathcal{A}_i$ (for $i \in \{0, 1, 2, 3\}$) is nonempty.
op1370_globalholes_unc- Every family $\mathcal{A}_i$ is uncomplemented: no member set has its complement in the same family.
op1370_globalholes_inc- The four families are pairwise strongly incomparable: no set in one family is a subset of any set in a different family.
op1370_globalholes_pos- For every element $x \in \{0, 1, 2, 3, 4\}$, there exist two distinct families containing sets that include $x$ (no private positive incidence).
op1370_globalholes_neg- For every element $x \in \{0, 1, 2, 3, 4\}$, there exist two distinct families containing sets that exclude $x$ (no private negative incidence).
op1370_globalholes_card- The set of subsets obtained by erasing element $0$ from each set in the union $\bigcup_{i=0}^3 \mathcal{A}_i$ has cardinality 14.
- The six auxiliary lemmas are verified entirely by Lean's kernel via `decide +kernel`, which evaluates the decidable finite set predicates by exhaustive computation rather than symbolic deduction.
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 1800000set_option maxRecDepth 8192def op1370_globalholes_f0 : Finset (Finset (Fin 5)) := {{0, 1}}def op1370_globalholes_f1 : Finset (Finset (Fin 5)) := {{2, 3, 4}}def op1370_globalholes_f2 : Finset (Finset (Fin 5)) := {{1, 2}, {1, 3}, {1, 2, 3}, {1, 4}, {1, 2, 4}, {1, 3, 4}}def op1370_globalholes_f3 : Finset (Finset (Fin 5)) := {{0, 2}, {0, 3}, {0, 2, 3}, {0, 4}, {0, 2, 4}, {0, 3, 4}}def op1370_globalholes_families : Fin 4 → Finset (Finset (Fin 5)) := ![op1370_globalholes_f0, op1370_globalholes_f1, op1370_globalholes_f2, op1370_globalholes_f3]lemma op1370_globalholes_ne : ∀ i, (op1370_globalholes_families i).Nonempty := by decide +kernellemma op1370_globalholes_unc : ∀ i, is_uncomplemented (op1370_globalholes_families i) := by unfold is_uncomplemented decide +kernellemma op1370_globalholes_inc : strongly_incomparable op1370_globalholes_families := by unfold strongly_incomparable decide +kernellemma op1370_globalholes_pos : ∀ x : Fin 5, ∃ i j : Fin 4, i ≠ j ∧ (∃ S ∈ op1370_globalholes_families i, x ∈ S) ∧ (∃ T ∈ op1370_globalholes_families j, x ∈ T) := by decide +kernellemma op1370_globalholes_neg : ∀ x : Fin 5, ∃ i j : Fin 4, i ≠ j ∧ (∃ S ∈ op1370_globalholes_families i, x ∉ S) ∧ (∃ T ∈ op1370_globalholes_families j, x ∉ T) := by decide +kernellemma op1370_globalholes_card : ((Finset.univ.biUnion op1370_globalholes_families).image (fun S => S.erase (0 : Fin 5))).card = 14 := by decide +kerneltheorem op_1370_global_two_projection_holes_counterexample : ∃ 𝒜 : Fin 4 → Finset (Finset (Fin 5)), (∀ i, (𝒜 i).Nonempty) ∧ (∀ i, is_uncomplemented (𝒜 i)) ∧ strongly_incomparable 𝒜 ∧ (∀ x, ∃ i j : Fin 4, i ≠ j ∧ (∃ S ∈ 𝒜 i, x ∈ S) ∧ (∃ T ∈ 𝒜 j, x ∈ T)) ∧ (∀ x, ∃ i j : Fin 4, i ≠ j ∧ (∃ S ∈ 𝒜 i, x ∉ S) ∧ (∃ T ∈ 𝒜 j, x ∉ T)) ∧ ((Finset.univ.biUnion 𝒜).image (fun S => S.erase (0 : Fin 5))).card = 14 := by exact ⟨op1370_globalholes_families, op1370_globalholes_ne, op1370_globalholes_unc, op1370_globalholes_inc, op1370_globalholes_pos, op1370_globalholes_neg, op1370_globalholes_card⟩