exists_pair_same_snd_of_card_gt
Every finite subset S of Fin m × Fin k with cardinality strictly greater than k contains two distinct elements sharing the same second coordinate.
Statement
theorem exists_pair_same_snd_of_card_gt {m k : ℕ} {S : Finset (Fin m × Fin k)} (hS : k < S.card) :
∃ u ∈ S, ∃ v ∈ S, u ≠ v ∧ u.2 = v.2- Source
- arXiv:2611.03878 Theorem 3.1
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
For all natural numbers $m$ and $k$, and any finite subset $S$ of $\mathrm{Fin}(m) \times \mathrm{Fin}(k)$, if the cardinality of $S$ is strictly greater than $k$, then there exist distinct elements $u, v \in S$ ($u \neq v$) such that their second coordinates are equal ($u.2 = v.2$).
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 proceeds by contradiction using the pigeonhole principle. If no two distinct elements in S shared their second coordinate, projection onto the second coordinate would be an injection from S into Fin k. That injection would force |S| ≤ k, contradicting the assumption that k < |S|.
Assume for contradiction that no two distinct elements of S share their second coordinate.
We assume the negation of the conclusion: for all pairs u, v ∈ S, if u ≠ v then their second coordinates differ (u.2 ≠ v.2).
by_contra! h
The projection onto the second coordinate is injective on S.
Suppose u, v ∈ S have the same second coordinate (u.2 = v.2). If u ≠ v, this would contradict our assumption that distinct elements have distinct second coordinates. Hence u = v.
have h_inj : Set.InjOn Prod.snd (S : Set (Fin m × Fin k)) := by intro u hu v hv heq by_contra hne exact h u hu v hv hne heq
The projection onto the second coordinate maps S into the universal finset of Fin k.
For any x ∈ S, its second component x.2 belongs to the universe of Fin k by Finset.mem_univ.
uses
Finset.mem_univhave h_maps : Set.MapsTo Prod.snd (S : Set (Fin m × Fin k)) (Finset.univ : Finset (Fin k)) := by intro x _ exact Finset.mem_univ _
The cardinality of S is at most k (|S| ≤ k).
Since the projection to the second coordinate is injective on S and maps into Finset.univ for Fin k, Finset.card_le_card_of_injOn implies |S| ≤ |Finset.univ|. Rewriting the cardinality of Finset.univ using Finset.card_univ and Fintype.card_fin gives |S| ≤ k.
uses
Finset.card_le_card_of_injOn,Finset.card_univ,Fintype.card_finhave h_le := Finset.card_le_card_of_injOn Prod.snd h_maps h_inj simp only [Finset.card_univ, Fintype.card_fin] at h_le
A contradiction is reached, completing the proof.
The bound |S| ≤ k contradicts the hypothesis k < |S| by Nat.not_le_of_lt.
uses
Nat.not_le_of_ltexact Nat.not_le_of_lt hS h_le
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
Finset.card_le_card_of_injOn- If a function maps a finite set s into a finite set t and is injective on s, then |s| ≤ |t|.
Finset.card_univ- The cardinality of the universal finset of a finite type α equals the cardinality of α.
Fintype.card_fin- The standard finite set Fin n has cardinality n.
Nat.not_le_of_lt- If a < b for natural numbers, then b ≤ a cannot hold.
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 second coordinate, any subset of Fin m × Fin k of size > k has two distinct elements with equal second coordinate. -/theorem exists_pair_same_snd_of_card_gt {m k : ℕ} {S : Finset (Fin m × Fin k)} (hS : k < S.card) : ∃ u ∈ S, ∃ v ∈ S, u ≠ v ∧ u.2 = v.2 := by by_contra! h have h_inj : Set.InjOn Prod.snd (S : Set (Fin m × Fin k)) := by intro u hu v hv heq by_contra hne exact h u hu v hv hne heq have h_maps : Set.MapsTo Prod.snd (S : Set (Fin m × Fin k)) (Finset.univ : Finset (Fin k)) := by intro x _ exact Finset.mem_univ _ have h_le := Finset.card_le_card_of_injOn Prod.snd h_maps h_inj simp only [Finset.card_univ, Fintype.card_fin] at h_le exact Nat.not_le_of_lt hS h_le