AFTD Auto-Formalizing Theoretical Domains

op_153_card_le_of_avoiding_diff

theoremverified

For every positive integer $k$, every subset $A \subseteq \{1, \dots, 2k\}$ such that no two distinct elements of $A$ have difference equal to $k$ satisfies $|A| \le k$.

Statement

theorem op_153_card_le_of_avoiding_diff (k : ℕ) (hk : 0 < k) (A : Finset ℕ)
    (hA : A ⊆ Finset.Icc 1 (2 * k))
    (hdiff : ∀ a ∈ A, ∀ b ∈ A, a ≠ b → (a : ℤ) - b ≠ (k : ℤ)) :
    A.card ≤ k
Source
folklore
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • op_153_card_le_of_poly_diff_freeLet $h \in \mathbb{Z}[X]$ be an integer polynomial such that $h(1) = k > 0$. Every subset $A \subseteq \{1, \dots, 2k\}$ whose distinct…

Read back from the Lean

For any natural number $k$ with $k > 0$, and any finite set of natural numbers $A \subseteq \{1, \dots, 2k\}$, if no two distinct elements $a, b \in A$ satisfy $a - b = k$ (as integers), then the cardinality of $A$ is at most $k$.

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 uses the pigeonhole principle via an explicit injection. We define a map $f$ from $\{1, \dots, 2k\}$ to $\{1, \dots, k\}$ by sending $x$ to $x$ when $x \le k$ and to $x - k$ when $x > k$, effectively pairing each $x$ with $x + k$. This map sends $A$ into $\{1, \dots, k\}$ and is injective on $A$, since two distinct elements with the same image under $f$ would differ by exactly $k$. It follows that $|A| \le |\{1, \dots, k\}| = k$.

  1. The map $f(x)$, defined as $x$ if $x \le k$ and $x - k$ if $x > k$, maps $A$ into $\{1, \dots, k\}$.

    We define $f : ℕ \to ℕ$ by splitting on whether $x \le k$. For any $x \in A$, the assumption $A \subseteq \{1, \dots, 2k\}$ gives $1 \le x \le 2k$ using Finset.mem_coe and Finset.mem_Icc. If $x \le k$, then $f(x) = x \in \{1, \dots, k\}$. If $x > k$, then $f(x) = x - k$, which satisfies $1 \le x - k \le k$ since $x \le 2k$. In both cases, linear arithmetic (omega) confirms that $f(x) \in \{1, \dots, k\}$.

    lines 6–13

    uses Finset.mem_coe, Finset.mem_Icc

      let f : ℕ → ℕ := fun x => if x ≤ k then x else x - k
      have hmaps : Set.MapsTo f (A : Set ℕ) (Finset.Icc 1 k : Set ℕ) := by
        intro x hx
        rw [Finset.mem_coe] at hx ⊢
        have hx' := hA hx
        rw [Finset.mem_Icc] at hx' ⊢
        dsimp [f]
        split_ifs <;> omega
  2. The map $f$ is injective on $A$.

    Let $a, b \in A$ satisfy $f(a) = f(b)$, and suppose for contradiction that $a \neq b$. By the hypothesis that no two distinct elements of $A$ have difference $k$, we have $(a : ℤ) - b \neq k$ and, by symmetry of inequality (Ne.symm), $(b : ℤ) - a \neq k$. Expanding the definition of $f$ gives four cases: if both $a, b \le k$ or both $a, b > k$, then $f(a) = f(b)$ directly forces $a = b$, contradicting $a \neq b$; if $a \le k$ and $b > k$, then $a = b - k$, so $b - a = k$, a contradiction; symmetrically, if $a > k$ and $b \le k$, then $a - k = b$, so $a - b = k$, also a contradiction. Linear arithmetic (omega) closes each branch.

    lines 14–21

    uses Finset.mem_coe, Ne.symm

      have hinj : (A : Set ℕ).InjOn f := by
        intro a ha b hb hfab
        rw [Finset.mem_coe] at ha hb
        dsimp [f] at hfab
        by_contra hne
        have hd1 := hdiff a ha b hb hne
        have hd2 := hdiff b hb a ha (Ne.symm hne)
        split_ifs at hfab <;> omega
  3. The cardinality of $A$ is bounded by $|\{1, \dots, k\}| = k$.

    Because $f$ maps $A$ injectively into $\{1, \dots, k\}$, the cardinality of $A$ is at most that of $\{1, \dots, k\}$ (Finset.card_le_card_of_injOn). The size of $\{1, \dots, k\}$ is $k + 1 - 1$ (Nat.card_Icc), which simplifies to $k$ by linear arithmetic (omega).

    lines 22–24

    uses Finset.card_le_card_of_injOn, Nat.card_Icc

      have hcard := Finset.card_le_card_of_injOn f hmaps hinj
      rw [Nat.card_Icc] at hcard
      omega
Finset.mem_coe
An element belongs to a finite set viewed as a set if and only if it belongs to the finite set.
Finset.mem_Icc
An element $x$ belongs to the closed interval $\{a, \dots, b\}$ if and only if $a \le x \le b$.
Ne.symm
Inequality is symmetric: if $a \neq b$, then $b \neq a$.
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| \le |t|$.
Nat.card_Icc
For natural numbers $a$ and $b$, the number of integers in $\{a, \dots, b\}$ is $b + 1 - a$.

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

/-- Any subset of {1, ..., 2k} avoiding difference k has cardinality at most k. -/theorem op_153_card_le_of_avoiding_diff (k : ℕ) (hk : 0 < k) (A : Finset ℕ)    (hA : A ⊆ Finset.Icc 1 (2 * k))    (hdiff : ∀ a ∈ A, ∀ b ∈ A, a ≠ b → (a : ℤ) - b ≠ (k : ℤ)) :    A.card ≤ k := by  let f : ℕ → ℕ := fun x => if x ≤ k then x else x - k  have hmaps : Set.MapsTo f (A : Set ℕ) (Finset.Icc 1 k : Set ℕ) := by    intro x hx    rw [Finset.mem_coe] at hx ⊢    have hx' := hA hx    rw [Finset.mem_Icc] at hx' ⊢    dsimp [f]    split_ifs <;> omega  have hinj : (A : Set ℕ).InjOn f := by    intro a ha b hb hfab    rw [Finset.mem_coe] at ha hb    dsimp [f] at hfab    by_contra hne    have hd1 := hdiff a ha b hb hne    have hd2 := hdiff b hb a ha (Ne.symm hne)    split_ifs at hfab <;> omega  have hcard := Finset.card_le_card_of_injOn f hmaps hinj  rw [Nat.card_Icc] at hcard  omega
See it in the graphDiscuss this resultChallenge it