exists_pair_same_fst_of_card_gt
Every finite subset S of Fin m × Fin k with cardinality strictly greater than m contains two distinct elements sharing the same first coordinate.
Statement
theorem exists_pair_same_fst_of_card_gt {m k : ℕ} {S : Finset (Fin m × Fin k)} (hS : m < S.card) :
∃ u ∈ S, ∃ v ∈ S, u ≠ v ∧ u.1 = v.1- Source
- arXiv:2611.03878 Theorem 3.1
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
For any natural numbers $m$ and $k$, and any finite subset $S \subseteq \mathrm{Fin}(m) \times \mathrm{Fin}(k)$, if the cardinality of $S$ is strictly greater than $m$, then there exist elements $u, v \in S$ such that $u \neq v$ and the first component of $u$ equals the first component of $v$ ($u.1 = v.1$).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof applies the pigeonhole principle to the projection map onto the first coordinate. Because the first component lies in Fin m, the image of S under the projection has cardinality at most m. Since |S| > m by assumption, the image is strictly smaller than S, which implies that two distinct pairs in S must map to the same first coordinate.
The image of S under the first projection has cardinality at most m: |Prod.fst '' S| ≤ m.
The first coordinate belongs to the finite type Fin m. By Finset.card_le_univ, the cardinality of any subset of Fin m is at most the cardinality of Fin m itself, which equals m by Fintype.card_fin.
uses
Finset.card_le_univ,Fintype.card_finhave h_le : (S.image Prod.fst).card ≤ m := by calc (S.image Prod.fst).card ≤ Fintype.card (Fin m) := Finset.card_le_univ _ _ = m := Fintype.card_fin m
The image of S under the first projection has strictly smaller cardinality than S: |Prod.fst '' S| < |S|.
Combining |Prod.fst '' S| ≤ m with the hypothesis m < |S| using lt_of_le_of_lt gives the strict inequality.
uses
lt_of_le_of_lthave h_lt : (S.image Prod.fst).card < S.card := lt_of_le_of_lt h_le hSThere exist two distinct elements of S sharing the same first coordinate.
By the pigeonhole principle (Finset.exists_ne_map_eq_of_card_image_lt), since the projection Prod.fst maps S into a set of strictly smaller cardinality, it cannot be injective on S, producing two distinct elements u, v ∈ S with u.1 = v.1.
uses
Finset.exists_ne_map_eq_of_card_image_ltexact Finset.exists_ne_map_eq_of_card_image_lt h_lt
Finset.card_le_univ- The cardinality of any finite subset of a finite type is at most the cardinality of the entire type.
Fintype.card_fin- The standard finite set Fin n has cardinality n.
lt_of_le_of_lt- Transitivity of ordering: if a ≤ b and b < c, then a < c.
Finset.exists_ne_map_eq_of_card_image_lt- If the image of a finite set under a map has strictly smaller cardinality than the set itself, then some two distinct elements map to the same value (the pigeonhole principle).
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.
/-- By pigeonhole on the first coordinate, any subset of Fin m × Fin k of size > m has two distinct elements with equal first coordinate. -/theorem exists_pair_same_fst_of_card_gt {m k : ℕ} {S : Finset (Fin m × Fin k)} (hS : m < S.card) : ∃ u ∈ S, ∃ v ∈ S, u ≠ v ∧ u.1 = v.1 := by have h_le : (S.image Prod.fst).card ≤ m := by calc (S.image Prod.fst).card ≤ Fintype.card (Fin m) := Finset.card_le_univ _ _ = m := Fintype.card_fin m have h_lt : (S.image Prod.fst).card < S.card := lt_of_le_of_lt h_le hS exact Finset.exists_ne_map_eq_of_card_image_lt h_lt