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

-
As Brian mentions "Cantor's pairing function" will do the job directly. However, it may be easier to understand: First prove that the union of countably many countable sets is countable (See Cantor's first diagonal argument). Then we can write $\mathbb{N}\times\mathbb{N} = \bigcup(\mathbb{N}\times\{n\})$ and hence the product is countable –  Deven Ware Aug 28 '12 at 4:24
Perhaps you mean natural numbers, rather than integers ($\mathbb N$ usually denotes natural numbers while $\mathbb Z$ denotes integers)? Either way, the set of pairs of natural numbers/integers is countably infinite; just because the function you found is not a bijection does not mean no bijection exists. –  Alex Becker Aug 28 '12 at 4:26
yes, i meant integers. sorry about that –  James Aug 28 '12 at 4:29

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.

-