Proving $\mathbb{N} \times \mathbb{N}$ is countable

Question

This is straightforward when $\mathbb{N} = \{1,2,3, \ldots\}$. I define the map $f(a,b) = 2^{a-1} \cdot (2b - 1)$, which I can prove directly is bijective. When I define $\mathbb{N} = \{0,1,2, \ldots\}$, things get much more complicated. By composing bijective maps on both sides, both $\mathbb{N} \cup \{0\} \times \mathbb{N} \cup \{0\} \to \mathbb{N} \times \mathbb{N}$ and $\mathbb{N} \to \mathbb{N} \cup \{0\}$, I come up with the map $$ f(a,b) = 2^a (2b + 1) - 1. $$ It is straightforward to prove this map is injective because the $-1$ cancels. But I don't know how to prove this map is surjective. I can deal with the zero case by simply letting $a = b = 0$, but I can't "map" between the previous bijection and this one. Though this is a composition of bijections and hence bijective, I want to try to prove this directly.

I'd appreciate any tips.

EDIT: Here is my prove that $f(a,b) = 2^{a-1} \cdot (2b - 1)$ is bijective, provided that I exclude $0$ from the definition of $\mathbb{N}$. I will call this set $\mathbb{N}' = \{1,2,3, \ldots\}$.

I claim that $f$ is a bijection. First, let $y \in \mathbb{N}'$. If $y$ is odd, then $y = 2k - 1$ for some $k \in \mathbb{N}'$. Then we have $y = 1y = 2^{1-1} \cdot (2k-1)$, so $f(1,k) = y$. If $y$ is even, then $y = 2m$ for some $m \in \mathbb{N}'$. Let $r \in \mathbb{N}'$ be the highest power of $2$ such that $2^r \mid y$. Then $y = 2^r \cdot z$ for some $z \in \mathbb{N}'$, where $z$ is odd. Then $z = 2n - 1$ for some $n \in \mathbb{N}'$, so we have $y = 2^{(r+1)-1} \cdot (2n - 1)$. Then $f(r+1, n) = y$. Therefore, $f$ is surjective. Now, given $(a,b), (p,q) \in \mathbb{N}' \times \mathbb{N}'$ for which $f(a,b) = f(p,q)$, we have $2^{a-1} \cdot (2b - 1) = 2^{p-1} \cdot (2q - 1)$. Notice that neither $2b - 1$ nor $2q - 1$ are odd, so $2$ divides neither. Without loss of generality, suppose that $a - 1 \geq p - 1$, so $a \geq p$, so $a - p$ is a non-negative integer. Dividing through by $2^{p-1}$, we obtain $2^{a-p} \cdot (2b - 1) = 2q - 1$. If $a > p$, then $a - p - 1 \geq 0$, so $2\left(2^{a-p-1} \cdot (2b - 1)\right) = 2q - 1$, so $2q - 1$ is even, which is a contradiction. So $a = p$, so $2^{a-p} = 2^0 = 1$, so $2b - 1 = 2q - 1$, so $b = q$. Therefore, $(a,b) = (p,q)$, so $f$ is injective and hence bijective, so $\mathbb{N}' \times \mathbb{N}' \cong \mathbb{N}'$.

Answer 1

Per comment by ascheler, let $\mathbb{N}_+=\{1,2,\dots\}$ and $\mathbb{N}_0=\{0,1,2,\dots\}$.

The map $p:\mathbb{N}_0\to\mathbb{N}_+$ given by $p(n)\colon=n+1$ is a bijection, with $p^{-1}(n)=n-1$.

The function $p\times p:\mathbb{N}_0^2\to\mathbb{N}_+^2$ given by $$(p\times p)(n,m)\colon=(p(n),p(m))=(n+1,m+1)$$ is a bijective map with inverse given by $$(p\times p)^{-1}(n,m)\colon=(p^{-1}(n),p^{-1}(m))=(n-1,m-1)$$

The map you you want to define is the composition of bijective maps, specifically,

$$f\circ (p\times p):\mathbb{N}_0^2\to\mathbb{N}_+$$ which is again bijective, where $f:\mathbb{N}_+^2\to\mathbb{N}_+$ is $f(n,m)\colon=2^{n-1}(2m-1)$.

Answer 2

I find the formula in this approach to showing that $\Bbb{N} \times \Bbb{N}$ is countable to be much easier to understand and remember when $0$ is considered to be a member of $\Bbb{N}$. Let's expand your formula for $f(a, b)$: $$ f(a, b) = 2^a(2b+1) - 1 = 2^{a+1}b + 2^a - 1 $$ $2^a-1$ is a $a$ written in unary notation (i.e., a string of $a$ $1s$). $2^{a+1}b$ in binary notation is what you get by tacking $a+1$ $0$s to the right of the binary notation for $b$. So $f(a, b)$ (in binary) is what you get by writing down $b$ in binary, then a $0$ and then $a$ $1s$. That's clearly injective (because the position of the rightmost $0$ in a number expressed in binary uniquely determines $a$ and $b$ according to this construction) and surjective (because any number expressed in binary has a rightmost $0$).

A formal recursive definition for this $f$ is: \begin{align*} f(0, b) &= 2a \\ f(a+1, b) &=2f(a, b) + 1 \end{align*} and you can use this to give inductive proofs that $f$ is injective and surjective that mirror my intuitive arguments above.

Answer 3

Define $a(n)$ recursively by $a(2m)=0$ for all $m\in\mathbb N_0.$ Define $a(2m+1)=a(m)+1.$

Then prove recursively that $$n\equiv 2^{a(n)}-1\pmod{2^{a(n)+1}}\tag1$$

This lets you define $$b(n)=\frac{n-(2^{a(n)}-1)}{2^{a(n)+1}}.$$

Then $f(a(n),b(n))=n.$

---

Proving (1)

When $n=2m,$ $a(n)=0,$ and this is:

$$2m\equiv 0\pmod 2$$ which is trivially true.

Assume true for $n<2m+1.$ Then for $n=m:$

$$m\equiv 2^{a(m)}-1\pmod {2^{a(m)+1}}$$

Multiply by $2$ and add $1,$ you get:

$$2m+1\equiv 2^{a(m)+1}-1\pmod{2^{a(m)+2}}$$

Then substitute $a(m)+1=a(2m+1)$ and you get the result for $n=2m+1.$

---

$a(n)$ can be thought of as the number of consecutive $1$s on the right of the binary representation of $n,$ which is the same as the number of $0$s on the right of the binary representation of $n+1.$

Answer 4

Since $\Bbb N$ is in bijection with $\Bbb N\times \{i\}$ for all $i\in\Bbb N$, we have that $\Bbb N\times \{i\}$ is countable. But

$$\Bbb N\times \Bbb N=\bigcup_{i\in \Bbb N}(\Bbb N\times \{i\}),$$

which is countable since any countable union of countable sets is countable.