AFTD Auto-Formalizing Theoretical Domains

exists_pair_same_fst_of_card_gt

theoremverified

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.

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

    lines 4–6

    uses Finset.card_le_univ, Fintype.card_fin

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

    line 7

    uses lt_of_le_of_lt

      have h_lt : (S.image Prod.fst).card < S.card := lt_of_le_of_lt h_le hS
  3. There 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.

    line 8

    uses Finset.exists_ne_map_eq_of_card_image_lt

      exact 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

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