not_card_fiber_one_eq_one
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.
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).
intro hConstruct 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.
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⟩
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.
have hf : ∀ x ∈ A, f x = c0 ∨ f x ∈ P := by intro x _ right dsimp [f, P] split_ifs <;> decide
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.
uses
Finset.card_pos.mprhave 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⟩
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.
have h_res := @h α β _ _ A P c0 hc0 hA f hf hPThe 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.
uses
Finset.filter_eq_empty_iffhave h_empty : A.filter (fun x => f x = c0) = ∅ := by rw [Finset.filter_eq_empty_iff] intro ⟨x⟩ _ dsimp [f, c0] revert x decide
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.
uses
Finset.card_emptyrw [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.
- The types α and β are defined using `ULift (Fin 3)` to lift the standard 3-element type `Fin 3` from universe 0 into the arbitrary universe levels `u_1` and `u_2` required by the theorem statement; mathematically, these are simply three-element sets.
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.
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