AFTD Auto-Formalizing Theoretical Domains

good_slopes_injective_product_fiber_card

theoremverified

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|$.

  1. 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`).

    lines 2–5

    uses Finset.eq_univ_of_card, Finset.card_image_of_injOn, Fintype.card_prod

      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]
  2. 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.

    lines 6–17

    uses Finset.mem_image, Finset.mem_filter, Finset.mem_product, Finset.mem_singleton, Finset.mem_univ, and_true, Finset.mem_image.mp

      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
  3. $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`).

    lines 18–20

    uses Finset.mem_filter.mp

      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
  4. 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.

    lines 21–22

    uses Finset.card_image_of_injOn

      rw [← 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.

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 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
See it in the graphDiscuss this resultChallenge it