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.

  • 1
    $\begingroup$ I do not understand the point you made in the last paragraph. $\endgroup$ – Asaf Karagila Jul 27 '11 at 23:22
  • $\begingroup$ 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. $\endgroup$ – Harry Williams Jul 27 '11 at 23:28
  • $\begingroup$ I see. If so, I hope my answer is to your liking. $\endgroup$ – Asaf Karagila Jul 27 '11 at 23:30
  • 2
    $\begingroup$ 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? $\endgroup$ – Srivatsan Jul 27 '11 at 23:30
  • 3
    $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ 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)? $\endgroup$ – Harry Williams Jul 27 '11 at 23:38
  • $\begingroup$ 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. $\endgroup$ – Srivatsan Jul 27 '11 at 23:40
  • $\begingroup$ @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. $\endgroup$ – Asaf Karagila Jul 27 '11 at 23:41
  • 2
    $\begingroup$ Should I upvote this, or wait, just to annoy you, Mr 9999? :) $\endgroup$ – t.b. Jul 28 '11 at 0:23
  • 2
    $\begingroup$ @Theo: Wheeee... moderator tools are so sexy ;-) $\endgroup$ – 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.

  • $\begingroup$ gary: the OP writes in the comment, he knows that this proof is possible, but he wanted to examine the given function in particular. $\endgroup$ – Asaf Karagila Jul 27 '11 at 23:45
  • $\begingroup$ gary, I have heard of Cantor-Bernstein-Schroeder. Is this the one? Who is Rick? :-) $\endgroup$ – Srivatsan Jul 27 '11 at 23:48
  • $\begingroup$ 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. $\endgroup$ – Srivatsan Jul 27 '11 at 23:51
  • $\begingroup$ Srivatsa: The Rick part is just a stupid joke on my part; sorry :), there is an actor with that name. $\endgroup$ – gary Jul 27 '11 at 23:51
  • 3
    $\begingroup$ 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. $\endgroup$ – gary Jul 27 '11 at 23:58

In the OP's question he writes

is a surjection from $\mathbb{N}$ to $\mathbb{N} \times \mathbb{N}$, and so ends the proof

That is a bit amusing since surjectivity is all that is needed - the image of any enumeration is either a finite or countably infinite set.

The OP also states

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.

So for another 'exciting' (or perhaps only humorous bordering on silly) excursion, we ask,

What is the minimal amount of number theory needed to build a surjective enumeration of
$\mathbb{N}$ onto $\mathbb{N} \times \mathbb{N}$?

Let $T = \{\,(2^j3^k,m) \, | \, j,k \in \Bbb N_0 \land m \in \Bbb N\}$.

We have an injective mapping $f$ from $\mathbb{N}$ into $T$ defined by

$\quad m \mapsto (2^0 3^0, m)$

We can define an equivalence relation $\sim$ on $T$,

$\quad (2^j 3^k, m) \sim (2^\bar j 3^\bar k, \bar m) \; \text{ if } 2^j 3^k m = 2^\bar j 3^\bar k \bar m $.

We have the quotient map $\rho$ defined by $\sim$,

$\quad \rho: T \mapsto \frac{T}{\sim}$

Any element in the image of $\rho$ can be represented by an ordered pair $(2^j 3^k, m)$ with $m$ minimal. To show that these representatives must be unique boils down to proving that

$\tag 1 \text{If } 2^s = 3^t \text{ Then } s = 0 \land t = 0$

So we can define a mapping $g$ from the quotient to $\mathbb{N} \times \mathbb{N}$, by taking the unique representative $(2^j 3^k, m)$ of a block and mapping it to $(j,k)$.

It is always true that $(2^0 3^0, 2^j 3^k) \sim (2^j 3^k, 1)$.

Putting this altogether we see that the mapping $g \circ \rho \circ f$ is a surjection.

So $\text{(1)}$ is the only number theory needed here.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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