AFTD Auto-Formalizing Theoretical Domains

op_1370_global_two_projection_holes_counterexample

theoremverified

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 all i j : ι with i ≠ 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.

  1. 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.

    line 9

    lemma op1370_globalholes_ne : ∀ i, (op1370_globalholes_families i).Nonempty := by decide +kernel
  2. 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.

    lines 11–12

      unfold is_uncomplemented
      decide +kernel
  3. 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.

    lines 14–15

      unfold strongly_incomparable
      decide +kernel
  4. 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.

    line 16

    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
  5. 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.

    line 17

    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
  6. 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.

    line 18

    lemma op1370_globalholes_card : ((Finset.univ.biUnion op1370_globalholes_families).image (fun S => S.erase (0 : Fin 5))).card = 14 := by decide +kernel
  7. 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`).

    line 21

    uses op1370_globalholes_ne, op1370_globalholes_unc, op1370_globalholes_inc, op1370_globalholes_pos, op1370_globalholes_neg, op1370_globalholes_card

      exact ⟨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.

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

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⟩
See it in the graphDiscuss this resultChallenge it