# The cartesian product $\mathbb{N} \times \mathbb{N}$ is countable

I'm examining a proof I have read that claims to show that the Cartesian product $\mathbb{N} \times \mathbb{N}$ is countable, and as part of this proof, I am looking to show that the given map is surjective (indeed bijective), but I'm afraid that I can't see why this is the case. I wonder whether you might be able to point me in the right direction?

Indeed, the proof begins like this:

"For each $n \in \mathbb{N}$, let $k_n, l_n$ be such that $n = 2^{k_n - 1} \left(2l_n - 1 \right)$; that is, $k_n - 1$ is the power of $2$ in the prime factorisation of $n$, and $2 l_n - 1$ is the (necessarily odd) number $\frac{n}{2^{k_n - 1}}$."

It then states that $n \mapsto \left(k_n , l_n \right)$ is a surjection from $\mathbb{N}$ to $\mathbb{N} \times \mathbb{N}$, and so ends the proof.

I can intuitively see why this should be a bijection, I think, but I'm not sure how to make these feelings rigorous?

I suppose I'd say that the map is surjective since given any $\left(k_n , l_n \right) \in \mathbb{N} \times \mathbb{N}$ we can simply take $n$ indeed to be equal to $2^{k_n - 1} \left(2l_n - 1 \right)$ and note that $k_n - 1 \geq 0$ and thus $2^{k_n - 1}$ is both greater or equal to one so is a natural number (making the obvious inductive argument, noting that multiplication on $\mathbb{N}$ is closed), and similarly that $2 l_n - 1 \geq 2\cdot 1 - 1 = 1$ and is also a natural number, and thus the product of these two, $n$ must also be a natural number. Is it just as simple as this?

I suppose my gut feeling in the proving that the map is injective would be to assume that $2^{k_n - 1} \left(2 l_n - 1 \right) = 2^{k_m - 1} \left(2 l_m - 1 \right)$ and then use the Fundamental Theorem of Arithmetic to conclude that $n = m$. Is this going along the right lines? The 'implicit' definition of the mapping has me a little confused about the approach.

On a related, but separate note, I am indeed aware that if $K$ and $L$ are any countable sets, then so is $K \times L$, so trivially, taking the identity mapping we see trivially that this map is bijective and therefore that $\mathbb{N}$ is certainly countable (!), and thus so is $\mathbb{N} \times \mathbb{N}$. Hence, it's not really the statement that I'm interested in, but rather the exciting excursion into number theory that the above alternative proof provides.

-
I do not understand the point you made in the last paragraph. – Asaf Karagila Jul 27 '11 at 23:22
The point I made in the last paragraph was merely that I know that there are easier ways to prove that $\mathbb{N} \times \mathbb{N}$ is countable; therefore, the focus of my questioning is not on this fact itself, but the details of the number-theory proof I outline here. – Harry Williams Jul 27 '11 at 23:28
I see. If so, I hope my answer is to your liking. – Asaf Karagila Jul 27 '11 at 23:30
Your understanding seems fine. But if you aren't satisfied, I would recommend considering the inverse map $g: \mathbb N \times \mathbb N \to \mathbb N$ given by $g(x,y) = 2^{x-1} (2y-1)$. This map is quite explicit compared to the one you mentioned; so it should be easier to visualize this. Can you see why this is a bijection? – Srivatsan Jul 27 '11 at 23:30
If we wish, we can do it without the Fundamental Theorem, divide each by $2$ until we have to stop. Since equality is preserved, we must have reached the same odd number at the same time. – André Nicolas Jul 28 '11 at 0:00

Your intuition is correct. We use the fundamental theorem of arithmetic, namely the prime factorization is unique (up to order, of course).

First we prove injectivity:

Suppose $(k_n,l_n),(k_m,l_m)\in\mathbb N\times\mathbb N$ and $2^{k_n - 1} (2 l_n - 1 ) = 2^{k_m - 1} (2 l_m - 1)$.

$2$ is a prime number and $2t-1$ is odd for all $t$, and so we have that the power of $2$ is the same on both sides of the equation, and it is exactly $k_n=k_m$.

Divide by $2^{k_n}$ and therefore $2l_n-1 = 2l_m-1$, add $1$ and divide by $2$, so $(k_n,l_n)=(k_m,l_m)$ and therefore this mapping is injective.

Surjectivity it is even simpler, take $(k,l)\in\mathbb N\times\mathbb N$ and let $n=2^{k-1}(2l-1)$. Now $n\mapsto(k,l)$, because $2l-1$ is odd, so the powers of $2$ in the prime decomposition of $n$ are exactly $k-1$, and from there $l$ is determined to be our $l$. (If you look closely, this is exactly the same argument for injectivity only applied "backwards", which is a trait many of the proofs of this kind has)

As for simpler proofs, there are infinitely many... from the Cantor's pairing function ($(n,m)\mapsto\frac{(n+m)(n+m+1)}{2}+n$), to Cantor-Bernstein arguments by $(n,m)\mapsto 2^n3^m$ and $k\mapsto (k,k)$ for the injective functions. I like this function, though. I will try to remember it and use it next time I teach someone such proof.

-
Thanks very much for this. Just to be clear, when you state that "$2$ is a prime number" and so conclude that "$k_n = k_m$" I suppose that it must be the case that you are making the tacit assumption that $2l_n - 1$ and $2 l_m - 1$ are not multiples of $2$ (and hence you can use the uniqueness of the prime factorisation of either side of the equation implied by the Fundamental Theorem of Arithmetic to conclude)? – Harry Williams Jul 27 '11 at 23:38
For the sake of OP, I'll emphasize the number theory fact that this proof uses. First, if $p$ is prime, and $x,y$ are not divisible by $p$, then $p^a x = p^b y$ implies that $a=b$ and $x=y$. (This was used in the injectivity step.) For surjectivity, we used the fact that we can write $n$ as a product of a power of $2$ and an odd number. This basically follows from the Fundamental theorem of Arithmetic. – Srivatsan Jul 27 '11 at 23:40
@Harry: I have indeed added a bit on that, saying that $2t-1$ is always odd, so it cannot be a multiple of $2$. And indeed the fundamental theorem of arithmetic is heavily used. – Asaf Karagila Jul 27 '11 at 23:41
Should I upvote this, or wait, just to annoy you, Mr 9999? :) – t.b. Jul 28 '11 at 0:23
@Theo: Wheeee... moderator tools are so sexy ;-) – Asaf Karagila Jul 28 '11 at 0:25

It is possible that the notation is getting in the way of seeing what's going on.

Every positive integer $n$ is a power of $2$ times an odd number. (Note that $2^0$ is a power of $2$.)

For example, $840=2^3 \times 105$ and $747=2^0 \times 747$.

In symbols, $$n=2^e \times a$$ where $e$ is a non-negative integer, and $a$ is an odd positive integer.

Moreover, the above representation is unique: If we know $e$ and $a$, we know $n$, and if we know $n$, we know $e$ and $a$.

Since $a$ is odd, it is of the form $2b+1$, where $b$ is a non-negative integer. As $a$ ranges over the odd positive integers, $b$ ranges over the non-negative integers.

Let $f$ be the function that takes $n$ to the ordered pair $(e,b)$. For example, since $840=2^3 \times 105$, we have $f(840)=(3,52)$. Similarly, $f(747)=(0,373)$.

Let $\mathbb{N}_0$ be the set of non-negative integers. Then $f$ is a bijective map from $\mathbb{N}$ to $\mathbb{N}_0 \times \mathbb{N}_0$. This is an immediate consequence of the fact that if we know $e$ and $b$, we know $n$, and conversely that if we know $n$, we know $e$ and $b$.

Not exactly what are looking for, but awfully close! And easy to fix, since $\mathbb{N}$ is just $\mathbb{N}_0$ pushed forward by $1$.

All we need to do is to map $n$ to $(e+1, b+1)$.

-

For a quick proof, why not take a pair of primes, like, say , 2 and 3, then inject a pair (a,b) inf: $\mathbb N \times \mathbb N$ to $2^a3^b$, and, for the opposite direction, inject n in $\mathbb N$ into $\mathbb N\times \mathbb N$ by $n\rightarrow(n,0)$, and then use Rick Schroder-Bernstein. It seems clear that if f(a,b)=f(a',b'), so that $2^a3^b=2^{a'}3^{b'}$, then $2^{a-a'}3^{b-b'}=1$ , forcing a=a' and b=b'(alternatively, if $2^x3^y=1$ then both $2^x$ and $3^y$ must divide 1, so that x=y=0, and injectivity follows); OTOH, if (n,0)=(n',0) , then clearly n=n'

EDIT: Cantor-Schroeder-Bernstein maps can be extended (uniquely) into bijections.

-
gary: the OP writes in the comment, he knows that this proof is possible, but he wanted to examine the given function in particular. – Asaf Karagila Jul 27 '11 at 23:45
gary, I have heard of Cantor-Bernstein-Schroeder. Is this the one? Who is Rick? :-) – Srivatsan Jul 27 '11 at 23:48
Also to prove that the first map is an injection would take the same effort, no? But I agree I would usually prefer constructing an injection both ways and stitching them together as you suggested. – Srivatsan Jul 27 '11 at 23:51
Srivatsa: The Rick part is just a stupid joke on my part; sorry :), there is an actor with that name. – gary Jul 27 '11 at 23:51
Asaf: you're right. I'll leave it in case someone else wants a quick argument, and or an explicit use or refresher for Cantor-Bernstein-Schroeder. If I get bad comments, I'll delete it. – gary Jul 27 '11 at 23:58