AFTD Auto-Formalizing Theoretical Domains

not_strong_elimination_iff_compatible_and_union_min

theoremverifiedoriginal

The statement strong_elimination_iff_compatible_and_union_min is false: The statement is false as stated because of the empty set: If ∅ ∈ C, then is_compatible_collection C is trivially satisfied by picking C3 = ∅ for any distinct C1, C2 ∈ C and x ∈ C1 ∩ C2, because ∅ ⊆ (C1 ∪ C2) \ {x}. Furthermore, the condition ∀ F ∈ C, F.Nonempty → ∃ U ⊆ collection_min_nonempty C, F = U.biUnion id only constrains nonempty sets and ignores ∅. However, has_strong_elimination C requires finding C3 ∈ C containing y ∈ C1 \ C2, so C3 can never be ∅. A minimal concrete counterexample is on V = Fin 3 with C = {∅, {0, 1}, {0, 2}}: - is_compatible_collection C holds: the only pair with nonempty intersection is {0, 1} and {0, 2} (meeting at 0), and C3 = ∅ ∈ C is a subset of ({0, 1} ∪ {0, 2}) \ {0} = {1, 2}. - The nonempty sets of C are {0, 1} and {0, 2}; neither properly contains any other nonempty set in C, so both belong to collection_min_nonempty C. Each is thus a union of a subcollection of minimal nonempty sets (namely, the singleton subcollection). - However, has_strong_elimination C fails: taking C1 = {0, 1}, C2 = {0, 2}, x = 0, and y = 1, any C3 ∈ C containing 1 must be {0, 1}, but {0, 1} is not a subset of {1, 2} since 0 ∉ {1, 2}.

Statement

theorem not_strong_elimination_iff_compatible_and_union_min : ¬ (∀ {V : Type*} [DecidableEq V] (C : Finset (Finset V)), has_strong_elimination C ↔ is_compatible_collection C ∧ ∀ F ∈ C, F.Nonempty → ∃ U ⊆ collection_min_nonempty C, F = U.biUnion id)
Related work
refutes `strong_elimination_iff_compatible_and_union_min`
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • has_strong_eliminationGiven a type α with decidable equality, a finite collection C of finite subsets of α has the strong elimination property if for all C₁, C₂…
  • is_compatible_collectionFor an arbitrary type V with decidable equality, a finite collection C of finite subsets of V (C : Finset (Finset V)) is compatible if for…
  • collection_min_nonemptyGiven a type α with decidable equality and a finite collection C of finite subsets of α, collection_min_nonempty C is the subcollection of…

The proof, explained

The proposed equivalence between strong elimination and the conjunction of compatibility and decomposition into minimal nonempty sets is disproved by constructing an explicit counterexample. Assuming for contradiction that the equivalence holds universally, we take the collection C = {∅, {0, 1}, {0, 2}} over a three-element ground set. Because ∅ is in C, compatibility is trivially satisfied by picking C3 = ∅ whenever two sets intersect, and both nonempty sets are minimal, satisfying the decomposition condition. However, strong elimination requires finding a set containing a distinguished element y, which ∅ cannot do; an exhaustive check reveals that strong elimination fails for C, yielding a contradiction.

  1. Assume the general equivalence for contradiction and construct the counterexample collection C = {∅, {u0, u1}, {u0, u2}} over a three-element set.

    We begin a proof by contradiction by introducing the assumed equivalence H. To refute it, we take three points u0, u1, u2 representing 0, 1, 2 in Fin 3 (lifted to the appropriate universe level), prove they are pairwise distinct by computational evaluation (`decide`), and define the candidate counterexample collection exC = {∅, {u0, u1}, {u0, u2}}.

    lines 2–9

      intro H
      let u0 : ULift (Fin 3) := ⟨0⟩
      let u1 : ULift (Fin 3) := ⟨1⟩
      let u2 : ULift (Fin 3) := ⟨2⟩
      have u0_ne_u1 : u0 ≠ u1 := by intro h; injection h with h; revert h; decide
      have u0_ne_u2 : u0 ≠ u2 := by intro h; injection h with h; revert h; decide
      have u1_ne_u2 : u1 ≠ u2 := by intro h; injection h with h; revert h; decide
      let exC : Finset (Finset (ULift (Fin 3))) := {∅, {u0, u1}, {u0, u2}}
  2. The collection C does not have the strong elimination property.

    Suppose for contradiction that strong elimination holds for exC. Consider the sets C1 = {u0, u1} and C2 = {u0, u2} in exC. Their intersection contains u0, and u1 belongs to C1 \ C2. Strong elimination would guarantee the existence of some C3 ∈ exC containing u1 with C3 ⊆ (C1 ∪ C2) \ {u0} = {u1, u2}. We test all three members of exC: C3 cannot be ∅ because u1 ∈ C3; C3 cannot be {u0, u1} because it contains u0, which is not in {u1, u2}; and C3 cannot be {u0, u2} because it does not contain u1 (since u1 ≠ u0 and u1 ≠ u2). All three possibilities lead to contradiction.

    lines 10–25

    uses Finset.mem_insert, Finset.mem_singleton

      have not_se : ¬ has_strong_elimination exC := by
        intro h
        have h1 : ({u0, u1} : Finset (ULift (Fin 3))) ∈ exC := by simp [exC]
        have h2 : ({u0, u2} : Finset (ULift (Fin 3))) ∈ exC := by simp [exC]
        have hx : u0 ∈ ({u0, u1} : Finset (ULift (Fin 3))) ∩ {u0, u2} := by simp
        have hy : u1 ∈ ({u0, u1} : Finset (ULift (Fin 3))) \ {u0, u2} := by
          simp [u1_ne_u2, (u0_ne_u1).symm]
        rcases h _ h1 _ h2 u0 hx u1 hy with ⟨C3, hC3_mem, hy_in, hC3_sub⟩
        simp only [exC, Finset.mem_insert, Finset.mem_singleton] at hC3_mem
        rcases hC3_mem with rfl | rfl | rfl
        · simp at hy_in
        · have h_in : u0 ∈ ({u0, u1} : Finset (ULift (Fin 3))) := by simp
          have := hC3_sub h_in
          simp [u0_ne_u1, u0_ne_u2] at this
        · have : u1 ∈ ({u0, u2} : Finset (ULift (Fin 3))) := hy_in
          simp [u1_ne_u2, (u0_ne_u1).symm] at this
  3. The collection C is a compatible collection.

    Compatibility requires that for any distinct C1, C2 ∈ exC and any x ∈ C1 ∩ C2, there exists C3 ∈ exC with C3 ⊆ (C1 ∪ C2) \ {x}. We examine all pairs from exC: if C1 = C2, the distinctness hypothesis is violated; if either set is ∅, their intersection is empty so no such x exists. In the only remaining cases, where {C1, C2} = {{u0, u1}, {u0, u2}}, we choose C3 = ∅ ∈ exC. Since the empty set is a subset of every set, C3 ⊆ (C1 ∪ C2) \ {x} is trivially satisfied.

    lines 26–38

    uses Finset.mem_insert, Finset.mem_singleton, Finset.empty_subset

      have is_compat : is_compatible_collection exC := by
        intro C1 h1 C2 h2 hne x hx
        simp only [exC, Finset.mem_insert, Finset.mem_singleton] at h1 h2
        rcases h1 with rfl | rfl | rfl <;> rcases h2 with rfl | rfl | rfl
        · contradiction
        · simp at hx
        · simp at hx
        · simp at hx
        · contradiction
        · refine ⟨∅, by simp [exC], Finset.empty_subset _⟩
        · simp at hx
        · refine ⟨∅, by simp [exC], Finset.empty_subset _⟩
        · contradiction
  4. The set {u0, u1} is a minimal nonempty set in C.

    A set belongs to collection_min_nonempty if it is nonempty and contains no strictly smaller nonempty member of exC. The set {u0, u1} contains u0, hence is nonempty. Any nonempty subset T ∈ exC cannot be ∅; if T were {u0, u2}, then T ⊆ {u0, u1} would imply u2 ∈ {u0, u1}, which is false since u2 ≠ u0 and u2 ≠ u1. Thus no other nonempty set in exC is contained in {u0, u1}, confirming its minimality.

    lines 39–49

    uses Finset.mem_filter, Finset.mem_insert, Finset.mem_singleton, False.elim, Finset.not_nonempty_empty

      have min_01 : ({u0, u1} : Finset (ULift (Fin 3))) ∈ collection_min_nonempty exC := by
        simp only [collection_min_nonempty, Finset.mem_filter, exC, Finset.mem_insert,
                   Finset.mem_singleton]
        refine ⟨by simp, ⟨⟨u0, by simp⟩, ?_⟩⟩
        intro T hT hTne hTsub
        rcases hT with rfl | rfl | rfl
        · exact False.elim (Finset.not_nonempty_empty hTne)
        · rfl
        · exfalso
          have : u2 ∈ ({u0, u1} : Finset (ULift (Fin 3))) := hTsub (by simp)
          simp [u0_ne_u2.symm, u1_ne_u2.symm] at this
  5. The set {u0, u2} is a minimal nonempty set in C.

    Symmetrically to the previous step, {u0, u2} is nonempty because it contains u0. The only other nonempty candidate subset in exC is {u0, u1}, which cannot be a subset since u1 ∉ {u0, u2}. Therefore, {u0, u2} is also minimal among nonempty sets in exC.

    lines 50–60

    uses Finset.mem_filter, Finset.mem_insert, Finset.mem_singleton, False.elim, Finset.not_nonempty_empty

      have min_02 : ({u0, u2} : Finset (ULift (Fin 3))) ∈ collection_min_nonempty exC := by
        simp only [collection_min_nonempty, Finset.mem_filter, exC, Finset.mem_insert,
                   Finset.mem_singleton]
        refine ⟨by simp, ⟨⟨u0, by simp⟩, ?_⟩⟩
        intro T hT hTne hTsub
        rcases hT with rfl | rfl | rfl
        · exact False.elim (Finset.not_nonempty_empty hTne)
        · exfalso
          have : u1 ∈ ({u0, u2} : Finset (ULift (Fin 3))) := hTsub (by simp)
          simp [u0_ne_u1.symm, u1_ne_u2] at this
        · rfl
  6. Every nonempty set in C is a union of minimal nonempty sets.

    Given any F ∈ exC that is nonempty, F cannot be ∅. If F = {u0, u1}, we choose the singleton family U = {{u0, u1}}, which is a subcollection of collection_min_nonempty exC and whose union is F. If F = {u0, u2}, we similarly choose U = {{u0, u2}}.

    lines 61–71

    uses Finset.mem_insert, Finset.mem_singleton, False.elim, Finset.not_nonempty_empty

      have union_min : ∀ F ∈ exC, F.Nonempty → ∃ U ⊆ collection_min_nonempty exC, F = U.biUnion id := by
        intro F hF hFne
        simp only [exC, Finset.mem_insert, Finset.mem_singleton] at hF
        rcases hF with rfl | rfl | rfl
        · exact False.elim (Finset.not_nonempty_empty hFne)
        · refine ⟨{ {u0, u1} }, ?_, ?_⟩
          · simp [min_01]
          · simp
        · refine ⟨{ {u0, u2} }, ?_, ?_⟩
          · simp [min_02]
          · simp
  7. The collection C contradicts the assumed equivalence, establishing the theorem.

    We instantiate the universal equivalence H with V = ULift (Fin 3) and C = exC. Because exC is compatible and every nonempty set in exC is a union of minimal nonempty sets, the right-hand side of the equivalence holds. By the equivalence, exC must have strong elimination, contradicting our proof that it does not.

    lines 72–75

      have h := @H (ULift (Fin 3)) _ exC
      have h_rhs : is_compatible_collection exC ∧ ∀ F ∈ exC, F.Nonempty → ∃ U ⊆ collection_min_nonempty exC, F = U.biUnion id :=
        ⟨is_compat, union_min⟩
      exact not_se (h.mpr h_rhs)
False.elim
From False (a contradiction), any proposition follows (principle of explosion).
Finset.empty_subset
The empty set is a subset of every finite set.
Finset.mem_filter
An element belongs to the filtered subset {x ∈ s | p(x)} if and only if it belongs to s and satisfies p.
Finset.mem_insert
An element belongs to the insertion of an element b into a finite set s if and only if it equals b or already belongs to s.
Finset.mem_singleton
An element belongs to the singleton {a} if and only if it equals a.
Finset.not_nonempty_empty
The empty set is not nonempty.

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

theorem not_strong_elimination_iff_compatible_and_union_min : ¬ (∀ {V : Type*} [DecidableEq V] (C : Finset (Finset V)), has_strong_elimination C ↔ is_compatible_collection C ∧ ∀ F ∈ C, F.Nonempty → ∃ U ⊆ collection_min_nonempty C, F = U.biUnion id) := by  intro H  let u0 : ULift (Fin 3) := ⟨0⟩  let u1 : ULift (Fin 3) := ⟨1⟩  let u2 : ULift (Fin 3) := ⟨2⟩  have u0_ne_u1 : u0 ≠ u1 := by intro h; injection h with h; revert h; decide  have u0_ne_u2 : u0 ≠ u2 := by intro h; injection h with h; revert h; decide  have u1_ne_u2 : u1 ≠ u2 := by intro h; injection h with h; revert h; decide  let exC : Finset (Finset (ULift (Fin 3))) := {∅, {u0, u1}, {u0, u2}}  have not_se : ¬ has_strong_elimination exC := by    intro h    have h1 : ({u0, u1} : Finset (ULift (Fin 3))) ∈ exC := by simp [exC]    have h2 : ({u0, u2} : Finset (ULift (Fin 3))) ∈ exC := by simp [exC]    have hx : u0 ∈ ({u0, u1} : Finset (ULift (Fin 3))) ∩ {u0, u2} := by simp    have hy : u1 ∈ ({u0, u1} : Finset (ULift (Fin 3))) \ {u0, u2} := by      simp [u1_ne_u2, (u0_ne_u1).symm]    rcases h _ h1 _ h2 u0 hx u1 hy with ⟨C3, hC3_mem, hy_in, hC3_sub⟩    simp only [exC, Finset.mem_insert, Finset.mem_singleton] at hC3_mem    rcases hC3_mem with rfl | rfl | rfl    · simp at hy_in    · have h_in : u0 ∈ ({u0, u1} : Finset (ULift (Fin 3))) := by simp      have := hC3_sub h_in      simp [u0_ne_u1, u0_ne_u2] at this    · have : u1 ∈ ({u0, u2} : Finset (ULift (Fin 3))) := hy_in      simp [u1_ne_u2, (u0_ne_u1).symm] at this  have is_compat : is_compatible_collection exC := by    intro C1 h1 C2 h2 hne x hx    simp only [exC, Finset.mem_insert, Finset.mem_singleton] at h1 h2    rcases h1 with rfl | rfl | rfl <;> rcases h2 with rfl | rfl | rfl    · contradiction    · simp at hx    · simp at hx    · simp at hx    · contradiction    · refine ⟨∅, by simp [exC], Finset.empty_subset _⟩    · simp at hx    · refine ⟨∅, by simp [exC], Finset.empty_subset _⟩    · contradiction  have min_01 : ({u0, u1} : Finset (ULift (Fin 3))) ∈ collection_min_nonempty exC := by    simp only [collection_min_nonempty, Finset.mem_filter, exC, Finset.mem_insert,               Finset.mem_singleton]    refine ⟨by simp, ⟨⟨u0, by simp⟩, ?_⟩⟩    intro T hT hTne hTsub    rcases hT with rfl | rfl | rfl    · exact False.elim (Finset.not_nonempty_empty hTne)    · rfl    · exfalso      have : u2 ∈ ({u0, u1} : Finset (ULift (Fin 3))) := hTsub (by simp)      simp [u0_ne_u2.symm, u1_ne_u2.symm] at this  have min_02 : ({u0, u2} : Finset (ULift (Fin 3))) ∈ collection_min_nonempty exC := by    simp only [collection_min_nonempty, Finset.mem_filter, exC, Finset.mem_insert,               Finset.mem_singleton]    refine ⟨by simp, ⟨⟨u0, by simp⟩, ?_⟩⟩    intro T hT hTne hTsub    rcases hT with rfl | rfl | rfl    · exact False.elim (Finset.not_nonempty_empty hTne)    · exfalso      have : u1 ∈ ({u0, u2} : Finset (ULift (Fin 3))) := hTsub (by simp)      simp [u0_ne_u1.symm, u1_ne_u2] at this    · rfl  have union_min : ∀ F ∈ exC, F.Nonempty → ∃ U ⊆ collection_min_nonempty exC, F = U.biUnion id := by    intro F hF hFne    simp only [exC, Finset.mem_insert, Finset.mem_singleton] at hF    rcases hF with rfl | rfl | rfl    · exact False.elim (Finset.not_nonempty_empty hFne)    · refine ⟨{ {u0, u1} }, ?_, ?_⟩      · simp [min_01]      · simp    · refine ⟨{ {u0, u2} }, ?_, ?_⟩      · simp [min_02]      · simp  have h := @H (ULift (Fin 3)) _ exC  have h_rhs : is_compatible_collection exC ∧ ∀ F ∈ exC, F.Nonempty → ∃ U ⊆ collection_min_nonempty exC, F = U.biUnion id :=    ⟨is_compat, union_min⟩  exact not_se (h.mpr h_rhs)
See it in the graphDiscuss this resultChallenge it