good_slopes_injective_product_fiber_card
If an injective map on a finite set of size |Y| times |Z| takes values in Y times Z, then each fiber of its first coordinate has |Z| elements.
Statement
theorem good_slopes_injective_product_fiber_card {X Y Z : Type*} [DecidableEq X] [Fintype Y] [Fintype Z] [DecidableEq Y] [DecidableEq Z] (S : Finset X) (f : X → Y × Z) (hinj : Set.InjOn f S) (hcard : S.card = Fintype.card Y * Fintype.card Z) (y : Y) : (S.filter fun x => (f x).1 = y).card = Fintype.card Z
- Source
- Finite-fiber counting for the CRT reduction in the 35-point fiber route to OP-1027.
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- good_slopes_fiber35_unit_gapFor any 35 points over the residues modulo 35, if at least one unit direction fails to be injective, then at most 20 of the 24 unit…
- good_slopes_product_fiber_transferFor a bijective anchor direction on a product, each projected fiber has the size of the second factor. Good directions with the same first…
The proof, explained
Since $f$ is injective on $S$ and $|S| = |Y| \cdot |Z| = |Y \times Z|$, a cardinality argument implies that $f(S)$ covers all of $Y \times Z$. Consequently, the image of the fiber of elements mapping to first coordinate $y$ is precisely the full slice $\{y\} \times Z$. Injectivity of $f$ on the fiber then ensures that the fiber and this slice have the same cardinality, namely $|Z|$.
The image of $S$ under $f$ is the entire product $Y \times Z$.
Because $f$ is injective on $S$, the size of its image $|f(S)|$ equals $|S|$ (`Finset.card_image_of_injOn`). By hypothesis, $|S| = |Y| \cdot |Z|$, which equals the cardinality of the product type $Y \times Z$ (`Fintype.card_prod`). A subset of a finite type having the same cardinality as the whole type must be the entire universe (`Finset.eq_univ_of_card`).
uses
Finset.eq_univ_of_card,Finset.card_image_of_injOn,Fintype.card_prodclassical have hfull : S.image f = Finset.univ := by apply Finset.eq_univ_of_card rw [Finset.card_image_of_injOn hinj, hcard, Fintype.card_prod]
The image of the fiber $\{x \in S \mid (f(x))_1 = y\}$ under $f$ is the set $\{y\} \times Z$.
By extensionality, an element $z \in Y \times Z$ belongs to the image of the fiber if and only if $z.1 = y$, after simplifying membership in images, filters, products, and singletons (`Finset.mem_image`, `Finset.mem_filter`, `Finset.mem_product`, `Finset.mem_singleton`, `Finset.mem_univ`, `and_true`). Forward: if $z = f(x)$ for some $x \in S$ with $(f(x))_1 = y$, then $z.1 = y$. Backward: if $z.1 = y$, since $f(S)$ is the entire universe (`hfull`), $z$ is in $f(S)$, so there exists $x \in S$ such that $f(x) = z$ (`Finset.mem_image.mp`). This $x$ also satisfies $(f(x))_1 = z.1 = y$, placing $z$ in the image of the fiber.
uses
Finset.mem_image,Finset.mem_filter,Finset.mem_product,Finset.mem_singleton,Finset.mem_univ,and_true,Finset.mem_image.mphave htarget : (S.filter fun x => (f x).1 = y).image f = {y} ×ˢ Finset.univ := by ext z simp only [Finset.mem_image, Finset.mem_filter, Finset.mem_product, Finset.mem_singleton, Finset.mem_univ, and_true] constructor · rintro ⟨x, ⟨hx,hxy⟩, rfl⟩ exact hxy · intro hz have hzfull : z ∈ S.image f := by rw [hfull]; exact Finset.mem_univ z obtain ⟨x,hx,hxz⟩ := Finset.mem_image.mp hzfull refine ⟨x, ⟨hx, ?_⟩, hxz⟩ rw [hxz] exact hz
$f$ is injective on the fiber $\{x \in S \mid (f(x))_1 = y\}$.
Every element in the filtered subset belongs to $S$ (`Finset.mem_filter.mp`), and $f$ is assumed to be injective on $S$ (`hinj`).
uses
Finset.mem_filter.mphave hfi : Set.InjOn f (S.filter fun x => (f x).1 = y) := by intro a ha b hb hab exact hinj (Finset.mem_filter.mp ha).1 (Finset.mem_filter.mp hb).1 hab
The cardinality of the fiber $\{x \in S \mid (f(x))_1 = y\}$ is $|Z|$.
Since $f$ is injective on the fiber, the fiber has the same size as its image (`Finset.card_image_of_injOn`), which is $\{y\} \times Z$. The cardinality of $\{y\} \times Z$ is $1 \cdot |Z| = |Z|$, which simplifies directly.
uses
Finset.card_image_of_injOnrw [← Finset.card_image_of_injOn hfi, htarget] simp
Finset.eq_univ_of_card- A finite subset of a finite type whose cardinality equals the type's cardinality is the entire type (`Finset.univ`).
Finset.card_image_of_injOn- If a function is injective on a finite set, the cardinality of the image finset equals the cardinality of the domain finset.
Fintype.card_prod- The cardinality of the product of two finite types is the product of their respective cardinalities.
Finset.mem_image- An element $b$ belongs to the image of a finset $s$ under $f$ if and only if there is some $a \in s$ with $f(a) = b$.
Finset.mem_filter- An element $a$ belongs to the filtered finset $\{x \in s \mid p(x)\}$ if and only if $a \in s$ and $p(a)$ holds.
Finset.mem_product- A pair $p$ belongs to the Cartesian product $s \times t$ if and only if $p.1 \in s$ and $p.2 \in t$.
Finset.mem_singleton- An element belongs to the singleton set $\{a\}$ if and only if it is equal to $a$.
Finset.mem_univ- Every element of a finite type belongs to the universal finset `Finset.univ`.
and_true- The conjunction $p \wedge \text{True}$ is logically equivalent to $p$.
Finset.mem_image.mp- If an element is in the image of a finset under $f$, then it is the image of some element in that finset.
Finset.mem_filter.mp- If an element is in a filtered finset, then it belongs to the underlying finset and satisfies the predicate.
- Line 2 activates classical logic (`classical`), allowing decidability of all propositions without explicit constructive instances.
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 good_slopes_injective_product_fiber_card {X Y Z : Type*} [DecidableEq X] [Fintype Y] [Fintype Z] [DecidableEq Y] [DecidableEq Z] (S : Finset X) (f : X → Y × Z) (hinj : Set.InjOn f S) (hcard : S.card = Fintype.card Y * Fintype.card Z) (y : Y) : (S.filter fun x => (f x).1 = y).card = Fintype.card Z := by classical have hfull : S.image f = Finset.univ := by apply Finset.eq_univ_of_card rw [Finset.card_image_of_injOn hinj, hcard, Fintype.card_prod] have htarget : (S.filter fun x => (f x).1 = y).image f = {y} ×ˢ Finset.univ := by ext z simp only [Finset.mem_image, Finset.mem_filter, Finset.mem_product, Finset.mem_singleton, Finset.mem_univ, and_true] constructor · rintro ⟨x, ⟨hx,hxy⟩, rfl⟩ exact hxy · intro hz have hzfull : z ∈ S.image f := by rw [hfull]; exact Finset.mem_univ z obtain ⟨x,hx,hxz⟩ := Finset.mem_image.mp hzfull refine ⟨x, ⟨hx, ?_⟩, hxz⟩ rw [hxz] exact hz have hfi : Set.InjOn f (S.filter fun x => (f x).1 = y) := by intro a ha b hb hab exact hinj (Finset.mem_filter.mp ha).1 (Finset.mem_filter.mp hb).1 hab rw [← Finset.card_image_of_injOn hfi, htarget] simp