Cardinality of the set of all pairs of integers

The set $S$ of all pairs of integers can be represented as $\{i \ | \ i \in \mathbb{Z} \} \times \{j\ | \ j \in \mathbb{Z}\}$. In other words, all coordinates on the cartesian plane where $x, y$ are integers.

I also know that a set is countable when $|S|\leq |\mathbb{N}^+|$. I attempted to map out a bijective function, $f : \mathbb{N}^+ \rightarrow S$.

$1 \rightarrow (1,1) \\ 2 \rightarrow (1,2)\\ 3 \rightarrow (1,3) \\ \quad \vdots $

I determined from this that the natural numbers can only keep up with $(1,*)$. But there is the ordered pairs where $x=2,3,4,\cdots$ not to mention the negative integers. In other words, $|S|\geq |\mathbb{N}^+|$ and therefore $S$ is not countably infinite.

Is this correct? (I don't think it is... Something to do with my understanding of infinite sets)

Solution 1:

Natural Numbers: There are many pairing functions that map $\mathbb{N}\times \mathbb{N}$ bijectively to $\mathbb{N}$. A simple example is the mapping $f$ such that $f(a,b)=2^{a-1}(2b-1)$. For every positive integer $y$ can be uniquely expressed as a power of $2$ times an odd integer.

Integers: If you want a mapping $g(x,y)$ that maps $\mathbb{Z}\times \mathbb{Z}$ bijectively to $\mathbb{N}$, it is simplest to split the work into two parts.

Let $\phi$ be any mapping that maps $\mathbb{Z}$ bijectively to $\mathbb{N}$. For a concrete example of such a mapping, let $\phi(t)=2t+2$ if $t \ge 0$, and let $\phi(t)=-(2t+1)$ if $t \lt 0$. The non-negative integers are sent to the even integers $\ge 2$, and the negative integers are sent to the positive odd integers.

Then the mapping $g(x,y)=f(\phi(x),\phi(y))$ works, where $f$ is any bijective map from $\mathbb{N}\times \mathbb{N}$ to $\mathbb{N}$. For example, we can use the mapping $f$ of the first paragraph, or the Cantor pairing function.

Remark: For most purposes, there is no particular virtue in having an explicit bijection, as long as we can prove that a bijection exists.

Solution 2:

You simply haven’t yet found a function that works. One that does is the Cantor pairing function, which is described quite well in the Wikipedia article to which I linked.