# Proving that a set is countable by finding a bijection

$Z$ is the set of non-negative integers including $0$. Show that $Z \times Z \times Z$ is countable by constructing the actual bijection $f: Z\times Z\times Z \to \mathbb{N}$ ($\mathbb{N}$ is the set of all natural numbers). There is no need to prove that it is a bijection.

After searching for clues on how to solve this, I found $(x+y-1)(x+y-z)/z+y$ but that is only two dimensional and does not include $0$. Any help on how to solve this?

-
If you have too bijections $g: Z\times Z\to Z$ and $id:Z\to Z$, can you find a way to combine them into a bijection $h: Z\times Z\times Z\to Z\times Z$? If you have such bijections, what can you say about the composition $g\circ h$? –  Martin Sleziak Apr 3 '12 at 18:21
There's nothing which says that it needs to be a polynomial. The question could be rephrased by saying "Let $A,B,C$ be countable sets: show that $A\times B\times C$ is countable." Have you seen the proof that $\mathbb{N}\times\mathbb{N}$ is countable? –  you Apr 3 '12 at 18:22
Do you mean $(x+y-1)(x+y-2)/2+y$? –  Thomas Andrews Apr 3 '12 at 18:22
Note that the question sentence is somewhat non-sensical. A bijection is not countable, a set is countable. (Yes, in some technical sense, a bijection is a set, but nowhere here are you referring to such a set.) What you want is a bijection that shows that the set $Z\times Z\times Z$ is countable. –  Thomas Andrews Apr 3 '12 at 18:24
Please fix the title along the lines of what Thomas suggests so that it makes sense! :) –  Mariano Suárez-Alvarez Apr 3 '12 at 18:43

$1$. If you have a bijection $f(x,y)$ from the set of ordered pairs $(x,y)$ of positive integers to the set of positive integers, you can adapt it to map pairs of non-negatives to the non-negatives by using $g(x,y)=f(x+1,y+1)-1$. If you want to map pairs of non-negatives to the positive integers, as you seem to, use $g(x,y)=f(x+1,y+1)$.

Look up Cantor pairing function. Depending on who defines it, it will be from pairs of positives to positives, in which case you adapt as above, or it will be from pairs of non-negatives to non-negatives, in which case you need to add $1$.

$2$. If you have a pairing function $g$, then you can obtain a ménage à trois function $h$ by letting $h(x,y,z)=g(g(x,y),z)$.

Remark: It is traditional in mathematical logic to think of $0$ as a natural number. This does not seem to be the way the rest of the world thinks. But maybe things will change. After all, in classical Pythagorean mathematics, $1$ is not a number. It is the source of all number, but numbers start at $2$ (which is female, and $3$ is male, and $5$ symbolizes marriage).

-
Ah, I misread that. –  Alex Becker Apr 3 '12 at 18:49
This remark is just awesome. –  Asaf Karagila Apr 3 '12 at 19:31

If you have a bijection $f:\mathbb N\times \mathbb N\to \mathbb N$, you can make a bijection $g:\mathbb N\times \mathbb N\times \mathbb N\to \mathbb N$ by letting $g(x,y,z)=f(f(x,y),z)$. This can then be turned into a bijection $h:Z\times Z\times Z\to \mathbb N$ by letting $h(x,y,z)=g(x+1,y+1,z+1)$.

-

If you don't need an actual "formula", then you can write $$\mathbb{Z}\times\mathbb{Z}\times\mathbb{Z} = \bigcup_{n=0}^\infty \{ (x,y,z)\in \mathbb{Z}^3 : |x|+|y| +|z| = n \}$$ and then rely on the fact that each term in this union is a finite set.

-

Just for fun, here’s an explicit enumeration.

First do it with $\Bbb N\times\Bbb N\times\Bbb N$. If you think of this as a subset of $\Bbb R^3$, you can chop it up into points lying in the parallel planes $P_k$ defined by $x+y+z=k$ for $k\in\Bbb N$. $P_0$ contains only $\langle 0,0,0\rangle$, $P_1$ contains $\langle 0,0,1\rangle,\langle 0,1,0\rangle$, and $\langle 1,0,0\rangle$ and so on. There are $\binom{k+2}2$ solutions to $x+y+z=k$ in non-negative integers $x,y$, and $z$, so $P_k$ contains $\binom{k+2}2$ members of $\Bbb N^3$. We’ll enumerate $\Bbb N^3$ by enumerating the individual $P_k$ in order of increasing $k$. We’ll start by explicitly enumerating the $\binom{k+2}2$ points of $P_k$.

Suppose that $\langle x,y,z\rangle\in P_k$. Then $x+y=k-z$, and a little thought shows that there are only $k-z+1$ possibilities, namely $x=i$ and $y=k-x-i$ for $i=0,\dots,k-z$. We’ll start by listing $P_k$ in reverse order of $z$. For $z=k$ there is only one point, $\langle 0,0,k\rangle$; in this ordering it has $0$ predecessors in $P_k$. For $z=k-1$ there are two points, $\langle 0,1,k-1\rangle$ and $\langle 1,0,k-1\rangle$; we’ll list them in increasing order of $x$, so that $\langle 0,1,k-1\rangle$ has $1$ predecessor, and $\langle 1,0,k-1\rangle$ has $2$ predecessors. For $z=k-2$ there are $3$ points; again listing them in increasing order of $x$, we have $\langle 0,2,k-2\rangle$ with $3$ predecessors, $\langle 1,1,k-2\rangle$ with $4$ predecessors, and $\langle 2,0,k-2\rangle$ with $5$ predecessors.

In general, $\langle 0,i,k-i\rangle$ has $\sum_{j=1}^ij=\binom{i+1}2$ predecessors, so $\langle j,i-j,k-i\rangle$ has $\binom{i+1}2+j$ predecessors. Thus, if $\langle x,y,z\rangle\in P_k$, it has $\binom{k-z+1}2+x$ predecessors in this ordering of $P_k$.

Next, note that $$\sum_{0\le i<k}|P_i|=\sum_{0\le i<k}\binom{i+2}2=\binom{k+2}3\;.$$ Thus, in the ordering of $\Bbb N^3$ as a whole, $\langle 0,0,k\rangle$ has $\binom{k+2}3$ predecessors. Combining results, we see that $\langle x,y,z\rangle$ has $$\binom{x+y+z+2}3+\binom{x+y+1}2+x$$ predecessors in this ordering of $\Bbb N^3$. (That last term can be thought of as $\binom{x+0}1$, and the obvious pattern can be generalized to higher powers of $\Bbb N$.) Since an enumeration $X\to\Bbb N$ of a set $X$ is simply a function that assigns to each $x\in X$ the number of predecessors of $x$ in the induced ordering, we have our enumeration of $\Bbb N^3$:

$$\varphi:\Bbb N^3\to\Bbb N:\langle x,y,z\rangle\mapsto\binom{x+y+z+2}3+\binom{x+y+1}2+x\;.$$

All that remains is to convert this to an enumeration of $\Bbb Z^3$. This is easily done by starting with the enumeration $$\psi:\Bbb Z\to\Bbb N:n\mapsto(-1)^n\left\lceil\frac{n}2\right\rceil\;,$$ which orders $\Bbb Z$ as $\langle 0,-1,1,-2,2,-3,3,\dots\rangle$. Let $$\overline\psi:\Bbb Z^3\to\Bbb N^3:\langle x,y,z\rangle\mapsto\langle \psi(x),\psi(y),\psi(z)\rangle\;;$$ this is clearly a bijection, and the desired explicit enumeration $\sigma:\Bbb Z^3\to\Bbb N$ is now given by $\sigma=\varphi\circ\overline\psi$. That is, $\langle x,y,z\rangle\in\Bbb Z^3$ is sent to

\begin{align*} &\binom{(-1)^x\left\lceil\frac{x}2\right\rceil+(-1)^y\left\lceil\frac{y}2\right\rceil+(-1)^z\left\lceil\frac{z}2\right\rceil+2}3+\\ &\qquad\qquad+\binom{(-1)^x\left\lceil\frac{x}2\right\rceil+(-1)^y\left\lceil\frac{y}2\right\rceil+1}2+(-1)^x\left\lceil\frac{x}2\right\rceil\;. \end{align*}

-