AFTD Auto-Formalizing Theoretical Domains

op_1370_local_two_projection_holes_counterexample

theoremverified

There are three nonempty uncomplemented mutually strongly incomparable families on Fin 5 for which element 0 occurs in at least two families and is absent in at least two families, yet erasing 0 from their union gives 14 distinct subsets of the other four elements. Thus the local incidence assumptions alone do not force more than two missing projected fibers.

Statement

theorem op_1370_local_two_projection_holes_counterexample : ∃ 𝒜 : Fin 3 → Finset (Finset (Fin 5)), (∀ i, (𝒜 i).Nonempty) ∧ (∀ i, is_uncomplemented (𝒜 i)) ∧ strongly_incomparable 𝒜 ∧ (∃ i j : Fin 3, i ≠ j ∧ (∃ S ∈ 𝒜 i, (0 : Fin 5) ∈ S) ∧ (∃ T ∈ 𝒜 j, (0 : Fin 5) ∈ T)) ∧ (∃ i j : Fin 3, i ≠ j ∧ (∃ S ∈ 𝒜 i, (0 : Fin 5) ∉ S) ∧ (∃ T ∈ 𝒜 j, (0 : Fin 5) ∉ T)) ∧ ((Finset.univ.biUnion 𝒜).image (fun S => S.erase (0 : Fin 5))).card = 14
Source
Counterexample to a proposed strengthening of op_1370_no_private_fiber_count, 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

The proof exhibits an explicit counterexample: a collection of three families of subsets of Fin 5. Six auxiliary lemmas establish that each family is nonempty, each is uncomplemented, they are mutually strongly incomparable, element 0 appears in sets of at least two families, 0 is absent from sets of at least two families, and erasing 0 from their union leaves exactly 14 distinct subsets. Each property is checked by exhaustive finite computation via decide +kernel, and the main theorem packages this witness and the six lemmas into the final existential statement.

  1. Each of the three families is nonempty. automation

    By definition, the three families have cardinalities 1, 7, and 6 respectively. Lean's kernel decision procedure evaluates the nonemptiness predicate for each index in Fin 3.

    line 8

    lemma op1370_twoholes_nonempty : ∀ i, (op1370_twoholes_families i).Nonempty := by decide +kernel
  2. Each of the three families is uncomplemented. automation

    After unfolding the definition of is_uncomplemented (no set and its complement both belong to the family), the kernel decision procedure exhaustively checks that no member's complement in Fin 5 belongs to the same family. In F₀ = {{1, 3, 4}}, the complement {0, 2} is absent; in F₁, every set contains 2, so no complement can contain 2; and in F₂, every set contains 0, so no complement can contain 0.

    lines 10–11

      unfold is_uncomplemented
      decide +kernel
  3. The three families are mutually strongly incomparable. automation

    After unfolding strongly_incomparable, the kernel decision procedure verifies that for any distinct pair of families, no set in the first family is a subset of any set in the second family.

    lines 13–14

      unfold strongly_incomparable
      decide +kernel
  4. Element 0 belongs to sets in at least two distinct families. automation

    The kernel decision procedure finds that {0, 2} belongs to family 1 and {0, 1} belongs to family 2, both containing 0.

    line 15

    lemma op1370_twoholes_pos : ∃ i j : Fin 3, i ≠ j ∧ (∃ S ∈ op1370_twoholes_families i, (0 : Fin 5) ∈ S) ∧ (∃ T ∈ op1370_twoholes_families j, (0 : Fin 5) ∈ T) := by decide +kernel
  5. Element 0 is absent from sets in at least two distinct families. automation

    The kernel decision procedure finds that {1, 3, 4} belongs to family 0 and {1, 2} belongs to family 1, neither containing 0.

    line 16

    lemma op1370_twoholes_neg : ∃ i j : Fin 3, i ≠ j ∧ (∃ S ∈ op1370_twoholes_families i, (0 : Fin 5) ∉ S) ∧ (∃ T ∈ op1370_twoholes_families j, (0 : Fin 5) ∉ T) := by decide +kernel
  6. Erasing element 0 from the union of the three families yields exactly 14 distinct subsets. automation

    The projection map S ↦ S \ {0} applied to the union of the three families yields 7 subsets containing 2 (from family 1), 6 subsets not containing 2 (from family 2), and the single subset {1, 3, 4} (from family 0), totalling 14 distinct subsets of the remaining 4 elements. The kernel decision procedure computes this image and its cardinality.

    line 17

    lemma op1370_twoholes_card : ((Finset.univ.biUnion op1370_twoholes_families).image (fun S => S.erase (0 : Fin 5))).card = 14 := by decide +kernel
  7. There exists a triple of families satisfying all the counterexample conditions.

    We instantiate the existential quantifier with op1370_twoholes_families, providing the six previously proven lemmas to satisfy each required conjunct.

    line 20

    uses op1370_twoholes_nonempty, op1370_twoholes_unc, op1370_twoholes_inc, op1370_twoholes_pos, op1370_twoholes_neg, op1370_twoholes_card

      exact ⟨op1370_twoholes_families, op1370_twoholes_nonempty, op1370_twoholes_unc, op1370_twoholes_inc, op1370_twoholes_pos, op1370_twoholes_neg, op1370_twoholes_card⟩
op1370_twoholes_nonempty
Each of the three families in op1370_twoholes_families is nonempty.
op1370_twoholes_unc
Each of the three families is uncomplemented: no family contains both a subset and its complement.
op1370_twoholes_inc
The three families are mutually strongly incomparable: no subset in any family is a subset of a subset in a different family.
op1370_twoholes_pos
Element 0 belongs to at least one subset in each of two distinct families among the three.
op1370_twoholes_neg
Element 0 is absent from at least one subset in each of two distinct families among the three.
op1370_twoholes_card
Erasing element 0 from each subset in the union of the three families yields a family of cardinality exactly 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_twoholes_f0 : Finset (Finset (Fin 5)) := {{1,3,4}}def op1370_twoholes_f1 : Finset (Finset (Fin 5)) := {{0,2}, {1,2}, {2,3}, {1,2,3}, {2,4}, {1,2,4}, {2,3,4}}def op1370_twoholes_f2 : Finset (Finset (Fin 5)) := {{0,1}, {0,3}, {0,1,3}, {0,4}, {0,1,4}, {0,3,4}}def op1370_twoholes_families : Fin 3 → Finset (Finset (Fin 5)) := ![op1370_twoholes_f0, op1370_twoholes_f1, op1370_twoholes_f2]lemma op1370_twoholes_nonempty : ∀ i, (op1370_twoholes_families i).Nonempty := by decide +kernellemma op1370_twoholes_unc : ∀ i, is_uncomplemented (op1370_twoholes_families i) := by  unfold is_uncomplemented  decide +kernellemma op1370_twoholes_inc : strongly_incomparable op1370_twoholes_families := by  unfold strongly_incomparable  decide +kernellemma op1370_twoholes_pos : ∃ i j : Fin 3, i ≠ j ∧ (∃ S ∈ op1370_twoholes_families i, (0 : Fin 5) ∈ S) ∧ (∃ T ∈ op1370_twoholes_families j, (0 : Fin 5) ∈ T) := by decide +kernellemma op1370_twoholes_neg : ∃ i j : Fin 3, i ≠ j ∧ (∃ S ∈ op1370_twoholes_families i, (0 : Fin 5) ∉ S) ∧ (∃ T ∈ op1370_twoholes_families j, (0 : Fin 5) ∉ T) := by decide +kernellemma op1370_twoholes_card : ((Finset.univ.biUnion op1370_twoholes_families).image (fun S => S.erase (0 : Fin 5))).card = 14 := by decide +kerneltheorem op_1370_local_two_projection_holes_counterexample : ∃ 𝒜 : Fin 3 → Finset (Finset (Fin 5)), (∀ i, (𝒜 i).Nonempty) ∧ (∀ i, is_uncomplemented (𝒜 i)) ∧ strongly_incomparable 𝒜 ∧ (∃ i j : Fin 3, i ≠ j ∧ (∃ S ∈ 𝒜 i, (0 : Fin 5) ∈ S) ∧ (∃ T ∈ 𝒜 j, (0 : Fin 5) ∈ T)) ∧ (∃ i j : Fin 3, i ≠ j ∧ (∃ S ∈ 𝒜 i, (0 : Fin 5) ∉ S) ∧ (∃ T ∈ 𝒜 j, (0 : Fin 5) ∉ T)) ∧ ((Finset.univ.biUnion 𝒜).image (fun S => S.erase (0 : Fin 5))).card = 14 := by  exact ⟨op1370_twoholes_families, op1370_twoholes_nonempty, op1370_twoholes_unc, op1370_twoholes_inc, op1370_twoholes_pos, op1370_twoholes_neg, op1370_twoholes_card⟩
See it in the graphDiscuss this resultChallenge it