AFTD Auto-Formalizing Theoretical Domains

exists_pair_same_snd_of_card_gt

theoremverified

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

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

    line 4

      by_contra! h
  2. 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.

    lines 5–8

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

    lines 9–11

    uses Finset.mem_univ

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

    lines 12–13

    uses Finset.card_le_card_of_injOn, Finset.card_univ, Fintype.card_fin

      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
  5. A contradiction is reached, completing the proof.

    The bound |S| ≤ k contradicts the hypothesis k < |S| by Nat.not_le_of_lt.

    line 14

    uses Nat.not_le_of_lt

      exact 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

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