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.

Solution 1:

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.

Solution 2:

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

Solution 3:

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.