AFTD Auto-Formalizing Theoretical Domains

exists_pair_diff_coords_of_card_gt

theoremverified

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.

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

    lines 1–5

    uses Finset.card_le_card_of_injOn

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

    lines 7–11

    uses Finset.card_le_card_of_injOn

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

    lines 14–17

    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
  4. If all elements share the same first coordinate, we get a contradiction

    The second projection is injective, so |S| ≤ m, contradicting |S| > m

    lines 18–23

    uses Prod.ext, exists_pair_diff_coords_of_card_gt_card_le_of_snd_inj

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

    lines 24–26

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

    lines 27–35

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

    lines 36–40

    uses Prod.ext, exists_pair_diff_coords_of_card_gt_card_le_of_fst_inj

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

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