AFTD Auto-Formalizing Theoretical Domains

not_card_fiber_one_eq_one

theoremverifiedoriginal

The statement card_fiber_one_eq_one is false: The statement is false. The hypotheses require |A| = |P| + 1, f(A) ⊆ {c0} ∪ P, and that every c ∈ P has at least one preimage in A. However, there is no hypothesis requiring c0 to have any preimage in A. Counterexample: Take A = {0, 1, 2}, P = {0, 1}, c0 = 2 ∉ P. Then |A| = 3 = |P| + 1. Define f : A → P by f(0) = 0, f(1) = 0, f(2) = 1. Then: - For every x ∈ A, f(x) ∈ P ⊆ {c0} ∪ P. - For each c ∈ P, |A ∩ f⁻¹(c)| ≥ 1 (fiber of 0 has cardinality 2, fiber of 1 has cardinality 1). Yet A ∩ f⁻¹(c0) = ∅, so (A.filter (fun x => f x = c0)).card = 0 ≠ 1.

Statement

theorem not_card_fiber_one_eq_one : ¬ (∀ {α β : Type*} [DecidableEq α] [DecidableEq β]
    (A : Finset α) (P : Finset β) (c0 : β) (hc0 : c0 ∉ P)
    (hA : A.card = P.card + 1)
    (f : α → β) (hf : ∀ x ∈ A, f x = c0 ∨ f x ∈ P)
    (hP : ∀ c ∈ P, 1 ≤ (A.filter (fun x => f x = c)).card), (A.filter (fun x => f x = c0)).card = 1)
Related work
refutes `card_fiber_one_eq_one`
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The proof disproves the universal statement by exhibiting an explicit finite counterexample. We choose A = {0, 1, 2}, P = {0, 1}, and c₀ = 2 ∉ P, so that |A| = 3 = |P| + 1. We define f by sending 2 to 1 and all other elements of A to 0, ensuring that every element of P has at least one preimage and the image of f lies in P. However, no element maps to c₀, so the fiber of c₀ is empty and has cardinality 0 rather than 1, contradicting the statement.

  1. Assume, for contradiction, that the claimed statement holds universally.

    We introduce the hypothesis h asserting that for any types α and β, finite sets A and P, element c₀ ∉ P with |A| = |P| + 1, and function f whose image is in {c₀} ∪ P such that every fiber over P is nonempty, the fiber of c₀ must have cardinality 1. The goal is to derive a contradiction (False).

    line 6

      intro h
  2. Construct a counterexample with |A| = 3, P = {0, 1}, c₀ = 2, and a function f.

    We choose α and β to be three-element sets (Fin 3), with A = {0, 1, 2}, P = {0, 1}, and c₀ = 2. By direct computation, c₀ ∉ P and |A| = 3 = |P| + 1. We define f : A → β by f(2) = 1 and f(x) = 0 for x ≠ 2.

    lines 7–14

      let α := ULift.{u_1} (Fin 3)
      let β := ULift.{u_2} (Fin 3)
      let A : Finset α := Finset.univ
      let P : Finset β := {⟨0⟩, ⟨1⟩}
      let c0 : β := ⟨2⟩
      have hc0 : c0 ∉ P := by decide
      have hA : A.card = P.card + 1 := by decide
      let f : α → β := fun x => if x.down = 2 then ⟨1⟩ else ⟨0⟩
  3. The image of f is contained in {c₀} ∪ P.

    For every x ∈ A, f(x) is either 1 (when x = 2) or 0 (when x ≠ 2). Since both 0 and 1 belong to P, f(x) ∈ P holds in both cases, which implies f(x) = c₀ ∨ f(x) ∈ P.

    lines 15–19

      have hf : ∀ x ∈ A, f x = c0 ∨ f x ∈ P := by
        intro x _
        right
        dsimp [f, P]
        split_ifs <;> decide
  4. Every element of P has at least one preimage in A under f.

    For c = 0 ∈ P, we have f(0) = 0, so 0 is in the fiber of 0. For c = 1 ∈ P, we have f(2) = 1, so 2 is in the fiber of 1. In both cases, the fiber contains a witness and is therefore nonempty, so by Finset.card_pos.mpr its cardinality is at least 1.

    lines 20–28

    uses Finset.card_pos.mpr

      have hP : ∀ c ∈ P, 1 ≤ (A.filter (fun x => f x = c)).card := by
        intro c hc
        fin_cases hc
        · have h0 : (⟨0⟩ : α) ∈ A.filter (fun x => f x = ⟨0⟩) := by
            simp [A, f]
          exact Finset.card_pos.mpr ⟨_, h0⟩
        · have h1 : (⟨2⟩ : α) ∈ A.filter (fun x => f x = ⟨1⟩) := by
            simp [A, f]
          exact Finset.card_pos.mpr ⟨_, h1⟩
  5. Instantiating the assumed statement with this counterexample yields that the fiber of c₀ has cardinality 1.

    Applying the universal hypothesis h to the concrete choices α, β, A, P, c₀, and f, along with the verified hypotheses, produces h_res: |{x ∈ A | f(x) = c₀}| = 1.

    line 29

      have h_res := @h α β _ _ A P c0 hc0 hA f hf hP
  6. The fiber of c₀ in A is empty.

    By Finset.filter_eq_empty_iff, the fiber is empty if and only if no element of A maps to c₀ = 2. Since f only takes values 0 and 1, exhaustive evaluation over all elements of Fin 3 confirms that f(x) ≠ 2 for every x ∈ A.

    lines 30–35

    uses Finset.filter_eq_empty_iff

      have h_empty : A.filter (fun x => f x = c0) = ∅ := by
        rw [Finset.filter_eq_empty_iff]
        intro ⟨x⟩ _
        dsimp [f, c0]
        revert x
        decide
  7. A contradiction is obtained from 0 = 1.

    Since the fiber of c₀ is empty, its cardinality is 0 by Finset.card_empty. Rewriting this into h_res gives 0 = 1, which is evaluated to False by computation.

    lines 36–38

    uses Finset.card_empty

      rw [h_empty, Finset.card_empty] at h_res
      revert h_res
      decide
Finset.card_pos.mpr
A finite set has cardinality at least 1 (strictly positive) if it is nonempty.
Finset.filter_eq_empty_iff
The sub-finset of elements satisfying a predicate is empty if and only if no element in the set satisfies the predicate.
Finset.card_empty
The cardinality of the empty finite set is 0.

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_card_fiber_one_eq_one : ¬ (∀ {α β : Type*} [DecidableEq α] [DecidableEq β]    (A : Finset α) (P : Finset β) (c0 : β) (hc0 : c0 ∉ P)    (hA : A.card = P.card + 1)    (f : α → β) (hf : ∀ x ∈ A, f x = c0 ∨ f x ∈ P)    (hP : ∀ c ∈ P, 1 ≤ (A.filter (fun x => f x = c)).card), (A.filter (fun x => f x = c0)).card = 1) := by  intro h  let α := ULift.{u_1} (Fin 3)  let β := ULift.{u_2} (Fin 3)  let A : Finset α := Finset.univ  let P : Finset β := {⟨0⟩, ⟨1⟩}  let c0 : β := ⟨2⟩  have hc0 : c0 ∉ P := by decide  have hA : A.card = P.card + 1 := by decide  let f : α → β := fun x => if x.down = 2 then ⟨1⟩ else ⟨0⟩  have hf : ∀ x ∈ A, f x = c0 ∨ f x ∈ P := by    intro x _    right    dsimp [f, P]    split_ifs <;> decide  have hP : ∀ c ∈ P, 1 ≤ (A.filter (fun x => f x = c)).card := by    intro c hc    fin_cases hc    · have h0 : (⟨0⟩ : α) ∈ A.filter (fun x => f x = ⟨0⟩) := by        simp [A, f]      exact Finset.card_pos.mpr ⟨_, h0⟩    · have h1 : (⟨2⟩ : α) ∈ A.filter (fun x => f x = ⟨1⟩) := by        simp [A, f]      exact Finset.card_pos.mpr ⟨_, h1⟩  have h_res := @h α β _ _ A P c0 hc0 hA f hf hP  have h_empty : A.filter (fun x => f x = c0) = ∅ := by    rw [Finset.filter_eq_empty_iff]    intro ⟨x⟩ _    dsimp [f, c0]    revert x    decide  rw [h_empty, Finset.card_empty] at h_res  revert h_res  decide
See it in the graphDiscuss this resultChallenge it