# Is $C$ an infinite set?

Suppose $$H:\mathbb{N}\times\mathbb{N}\mapsto\mathbb{N}$$ is a injective map. Let $$C=\{c|c=H(i,j)-H(i-1,j)$$ or $$H(i,j)-H(i,j-1)\}$$. Is $$C$$ an infinite set?

## 2 Answers

Notation is not nice but lets say for numbers, $$\pm$$ means $$\{n\pm c\} = \{ n-c,n-c+1,\cdots,n+c\}$$

Let me only consider the set $$\{H(i,j)-H(i-1,j)\}$$.

Note that, for fixed $$j$$, $$H(i,j) \to \infty$$ as $$i\to \infty.$$ Assume $$H(i,j) - H(i-1,j) < c$$.

Consider the set $$\{n\pm c\}$$, and note that for any $$j$$ there exists $$n$$ s.t. $$H(1,j)\in \{n\pm c\}$$ and further $$H(i',j)\in \{n+k\pm c\}$$ since they cannot make jumps larger than $$c$$ and it must tend to $$\infty$$.

Therefore, $$|\{H(i,j)\in\{n \pm c \}\}|\to \infty$$ as $$n\to\infty$$, which contradicts with injective.

• Thank you for your wonderful answer! Nov 23, 2020 at 3:07

Suppose that $$|H(i,j)-H(i-1,j)|,|H(i,j)-H(i,j-1)|\le m$$ for all $$i,j\in\Bbb N$$. If $$0\le i,j\le k\in\Bbb N$$, then

$$H(0,0)-2km\le H(i,j)\le H(0,0)+2km\,.$$

(My $$\Bbb N$$ includes $$0$$.) Thus, there are only $$4km+1$$ possible values for $$H(i,j)$$ with $$i,j\le k$$, but there are $$(k+1)^2$$ pairs $$\langle i,j\rangle$$ with $$i,j\le k$$. Clearly $$(k+1)^2>4km+1$$ for sufficiently large $$k$$, so $$C$$ must be infinite.

• Thank you for your wonderful answer! Nov 23, 2020 at 3:07
• @vfenux: You’re welcome! Nov 23, 2020 at 3:10