Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$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?

share|improve this question
1  
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
7  
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
2  
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
show 1 more comment

4 Answers 4

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*}$$

share|improve this answer
add comment

$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).

share|improve this answer
    
Ah, I misread that. –  Alex Becker Apr 3 '12 at 18:49
1  
This remark is just awesome. –  Asaf Karagila Apr 3 '12 at 19:31
add comment

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.

share|improve this answer
add comment

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)$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.