exists_pair_diff_coords_of_card_gt
Every finite subset S of Fin m × Fin m with cardinality strictly greater than m contains two elements that differ in both coordinates.
Statement
theorem exists_pair_diff_coords_of_card_gt {m : ℕ} {S : Finset (Fin m × Fin m)} (hS : m < S.card) :
∃ u ∈ S, ∃ v ∈ S, u.1 ≠ v.1 ∧ 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 any natural number $m$ and any finite subset $S \subseteq \mathrm{Fin}(m) \times \mathrm{Fin}(m)$, if the cardinality of $S$ is strictly greater than $m$, then there exist $u \in S$ and $v \in S$ such that $u.1 \neq v.1$ and $u.2 \neq v.2$ (that is, $u$ and $v$ differ in both coordinates).
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
We prove the claim by contradiction. If no two elements differ in both coordinates, then any two elements that differ in the first coordinate must agree in the second. If all elements of S share the first coordinate, the second coordinate is injective on S, so |S| ≤ m, a contradiction. Otherwise, there exist two elements differing in the first coordinate, which implies every element in S must share the same second coordinate, making the first coordinate injective on S and again forcing |S| ≤ m.
If the first coordinate projection is injective on S, then |S| ≤ m
Prod.fst maps S injectively into the universal set of Fin m, which has cardinality m
uses
Finset.card_le_card_of_injOnlemma exists_pair_diff_coords_of_card_gt_card_le_of_fst_inj {m : ℕ} {S : Finset (Fin m × Fin m)} (h : ∀ u ∈ S, ∀ v ∈ S, u.1 = v.1 → u = v) : S.card ≤ m := by have h_inj : Set.InjOn Prod.fst (↑S : Set (Fin m × Fin m)) := fun u hu v hv huv => h u hu v hv huv have h_maps : Set.MapsTo Prod.fst (↑S : Set (Fin m × Fin m)) (↑(Finset.univ : Finset (Fin m)) : Set (Fin m)) := fun _ _ => by simp simpa using Finset.card_le_card_of_injOn Prod.fst h_maps h_inj
If the second coordinate projection is injective on S, then |S| ≤ m
Prod.snd maps S injectively into the universal set of Fin m, which has cardinality m
uses
Finset.card_le_card_of_injOnlemma exists_pair_diff_coords_of_card_gt_card_le_of_snd_inj {m : ℕ} {S : Finset (Fin m × Fin m)} (h : ∀ u ∈ S, ∀ v ∈ S, u.2 = v.2 → u = v) : S.card ≤ m := by have h_inj : Set.InjOn Prod.snd (↑S : Set (Fin m × Fin m)) := fun u hu v hv huv => h u hu v hv huv have h_maps : Set.MapsTo Prod.snd (↑S : Set (Fin m × Fin m)) (↑(Finset.univ : Finset (Fin m)) : Set (Fin m)) := fun _ _ => by simp simpa using Finset.card_le_card_of_injOn Prod.snd h_maps h_inj
Assume for contradiction that no two elements in S differ in both coordinates
We proceed by contradiction and negate the existential goal: for any u, v in S, if they differ in the first coordinate, they must agree in the second
theorem exists_pair_diff_coords_of_card_gt {m : ℕ} {S : Finset (Fin m × Fin m)} (hS : m < S.card) : ∃ u ∈ S, ∃ v ∈ S, u.1 ≠ v.1 ∧ u.2 ≠ v.2 := by by_contra h push Not at h
If all elements share the same first coordinate, we get a contradiction
The second projection is injective, so |S| ≤ m, contradicting |S| > m
uses
Prod.ext,exists_pair_diff_coords_of_card_gt_card_le_of_snd_injby_cases h_fst : ∀ u ∈ S, ∀ v ∈ S, u.1 = v.1 · have h_inj : ∀ u ∈ S, ∀ v ∈ S, u.2 = v.2 → u = v := by intro u hu v hv huv exact Prod.ext (h_fst u hu v hv) huv have := exists_pair_diff_coords_of_card_gt_card_le_of_snd_inj h_inj omega
If not all elements share the first coordinate, pick two with different first coordinates; they share the second coordinate
Let a, b in S with different first coordinates; by the contradiction hypothesis, their second coordinates are equal
· push Not at h_fst rcases h_fst with ⟨a, ha, b, hb, hab⟩ have hab2 : a.2 = b.2 := h a ha b hb hab
Every element in S has the same second coordinate as a
For any w in S, either w shares the first coordinate with a, in which case it differs from b and hence matches b in the second coordinate, or it differs from a and matches a
have h_snd : ∀ w ∈ S, w.2 = a.2 := by intro w hw by_cases hwa : w.1 = a.1 · have hwb : w.1 ≠ b.1 := by intro hwb_eq exact hab (hwa.symm.trans hwb_eq) have := h w hw b hb hwb rw [this, ← hab2] · exact h w hw a ha hwa
The first projection is injective, giving |S| ≤ m and a contradiction
Since all elements have the same second coordinate, equality of the first coordinate implies equality of elements. Thus |S| ≤ m, contradicting |S| > m
uses
Prod.ext,exists_pair_diff_coords_of_card_gt_card_le_of_fst_injhave h_inj : ∀ u ∈ S, ∀ v ∈ S, u.1 = v.1 → u = v := by intro u hu v hv huv exact Prod.ext huv ((h_snd u hu).trans (h_snd v hv).symm) have := exists_pair_diff_coords_of_card_gt_card_le_of_fst_inj h_inj omega
Finset.card_le_card_of_injOn- If a function maps a finite set injectively into another, the domain cardinality is at most the codomain cardinality
exists_pair_diff_coords_of_card_gt_card_le_of_fst_inj- If the first projection is injective on S, then |S| ≤ m
exists_pair_diff_coords_of_card_gt_card_le_of_snd_inj- If the second projection is injective on S, then |S| ≤ m
Prod.ext- Two pairs are equal if their corresponding coordinates are equal
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.
lemma exists_pair_diff_coords_of_card_gt_card_le_of_fst_inj {m : ℕ} {S : Finset (Fin m × Fin m)} (h : ∀ u ∈ S, ∀ v ∈ S, u.1 = v.1 → u = v) : S.card ≤ m := by have h_inj : Set.InjOn Prod.fst (↑S : Set (Fin m × Fin m)) := fun u hu v hv huv => h u hu v hv huv have h_maps : Set.MapsTo Prod.fst (↑S : Set (Fin m × Fin m)) (↑(Finset.univ : Finset (Fin m)) : Set (Fin m)) := fun _ _ => by simp simpa using Finset.card_le_card_of_injOn Prod.fst h_maps h_injlemma exists_pair_diff_coords_of_card_gt_card_le_of_snd_inj {m : ℕ} {S : Finset (Fin m × Fin m)} (h : ∀ u ∈ S, ∀ v ∈ S, u.2 = v.2 → u = v) : S.card ≤ m := by have h_inj : Set.InjOn Prod.snd (↑S : Set (Fin m × Fin m)) := fun u hu v hv huv => h u hu v hv huv have h_maps : Set.MapsTo Prod.snd (↑S : Set (Fin m × Fin m)) (↑(Finset.univ : Finset (Fin m)) : Set (Fin m)) := fun _ _ => by simp simpa using Finset.card_le_card_of_injOn Prod.snd h_maps h_inj/-- Any subset of Fin m × Fin m of cardinality strictly greater than m contains two elements with both coordinates different. -/theorem exists_pair_diff_coords_of_card_gt {m : ℕ} {S : Finset (Fin m × Fin m)} (hS : m < S.card) : ∃ u ∈ S, ∃ v ∈ S, u.1 ≠ v.1 ∧ u.2 ≠ v.2 := by by_contra h push Not at h by_cases h_fst : ∀ u ∈ S, ∀ v ∈ S, u.1 = v.1 · have h_inj : ∀ u ∈ S, ∀ v ∈ S, u.2 = v.2 → u = v := by intro u hu v hv huv exact Prod.ext (h_fst u hu v hv) huv have := exists_pair_diff_coords_of_card_gt_card_le_of_snd_inj h_inj omega · push Not at h_fst rcases h_fst with ⟨a, ha, b, hb, hab⟩ have hab2 : a.2 = b.2 := h a ha b hb hab have h_snd : ∀ w ∈ S, w.2 = a.2 := by intro w hw by_cases hwa : w.1 = a.1 · have hwb : w.1 ≠ b.1 := by intro hwb_eq exact hab (hwa.symm.trans hwb_eq) have := h w hw b hb hwb rw [this, ← hab2] · exact h w hw a ha hwa have h_inj : ∀ u ∈ S, ∀ v ∈ S, u.1 = v.1 → u = v := by intro u hu v hv huv exact Prod.ext huv ((h_snd u hu).trans (h_snd v hv).symm) have := exists_pair_diff_coords_of_card_gt_card_le_of_fst_inj h_inj omega