op_153_card_le_of_avoiding_diff
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$.
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\}$.
uses
Finset.mem_coe,Finset.mem_Icclet 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
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.
uses
Finset.mem_coe,Ne.symmhave 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
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).
uses
Finset.card_le_card_of_injOn,Nat.card_Icchave 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$.
- The difference condition is formulated using integer subtraction, $(a : ℤ) - b \neq k$, to avoid the truncation at zero that natural number subtraction would perform.
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.
/-- 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