$\Bbb Z$ $\times$ $\Bbb N$ Countably Infinite

Question

I want to do this using an infinite grid as it seems easiest to me but I am open to other suggestions as well to improve my understanding.

My attempt: $$\begin{array}{c | c | c | c | c} (0,0) & (1,0) & (-1,0) & (2,0) & (-2,0).....\\ \hline (0,1) & (1,1) & (-1,1) & (2,1) & (-2,1).....\\ \hline (0,2) & (1,2) & (-1,2) & (2,2) & (-2,2)..... \\ \hline (0,3) & (1,3) & (-1,3) & (2,3) & (-2,3)..... \end{array}$$

$$\begin{array}{c | c | c | c | c} 1 & 3 & 6 & 10 & 15.....\\ \hline 2 & 5 & 9 & 14 & 20.....\\ \hline 4 & 8 & 13 & 19 & 26..... \\ \hline 7 & 12 & 18 & 25 & 33..... \end{array}$$

The columns also extend down by an infinite amount. I then tried to create a bijection from $\Bbb N$ $->$ $\Bbb Z$ $\times$ $\Bbb N$ by starting from the top left at $(0,0)$, and then preceding up each diagonal from bottom left to top right. So $1$ maps to $(0,0)$, $2$ maps to $(0,1)$, $3$ maps to $(1,0)$ and so on. This creates a bijection $f$: $\Bbb N$ $->$ $\Bbb Z$ $\times$ $\Bbb N$ in which each natural number maps to the pair ($a,b)$ in the grid above. I then explained why this is both injective and surjective to give a bijection.

Answer 1

Okay so taking the ideas together I have this for proving $\Bbb Q$ is countably infinite.

First, let's look at $\Bbb Z$ $\times$ $\Bbb N$ and prove this is countably infinite. We can write the elements of $\Bbb Z$ $\times$ $\Bbb N$ on an infinite grid as shown below.

The right hand side shows how the elements of this grid may be labelled with elements of $\Bbb N$, by taking $max(|a|,b)$ where $a \in \Bbb Z$ and $b \in \Bbb N$. This creates a bijection from $\Bbb Z$ $\times$ $\Bbb N$, namely the function $f$ : $\Bbb Z$ $\times$ $\Bbb N$ -> $\Bbb N$, in which each $n$ $\in$ $\Bbb N$ in the right hand grid maps to the pair $(a, b)$ in the corresponding position in the left hand grid (so, for instance, $f(5) = (-2, 2)$ and $f(8) = (1, 2))$. Indeed, $f$ is well-defined since every natural number appears once in the right hand grid and so is mapped to exactly one pair in the left-hand grid; $f$ is injective and surjective since each pair appears precisely once in the left-hand grid so is mapped to by exactly one element of $\Bbb N$. The existence of this bijection proves that $\Bbb Z$ $\times$ $\Bbb N$ is countably infinite.

Now, I want to prove there exists a surjection $g$: $\Bbb Z$ $\times$ $\Bbb N$ -> $\Bbb Q$, defined for $m$ $\in$ $\Bbb Z$ and $n$ $\in$ $\Bbb N$, by $(m,n) -> \frac{m}{n}$. This is clearly a surjective function because every rational number has at least one preimage in $\Bbb Z$ $\times$ $\Bbb N$. However, it isn't injective because some pairs $(m,n)$ map to the same rational number, such as $g((1,2)) = g((2,4)) = \frac{1}{2} = \frac{2}{4}$. So surjective.

Then $|\Bbb Q$| $\leq$ $|\Bbb Z$ $\times$ $\Bbb N|$ $=$ $\Bbb N$. Since $\Bbb N$ $\subseteq$ $\Bbb Q$ it follows from the CSB theorem that $|\Bbb N|$ $\leq$ $|\Bbb Q|$, so $|\Bbb N|$ $=$ $|\Bbb Q|$ and hence the $\Bbb Q$ is countably infinite. $\square$

Answer 2

You can define bijections in terms of other bijections.

To define the bijection: $f: \mathbb N \to \mathbb N\times \mathbb N$

$1 \to (1,1)$
$2\to (1,2); 3\to (2,1)$
$4\to (1,3); 5\to (2,2); 6\to (3,1)$ etc.

we not if the term $(a,b)$ is in the $k$th diagonal then $a+b=k+1$. To get to the $k$th diagonal we had to go through $k-1$ diagonals with increasing numbers of terms. So be fore we got to $f(n) = (a,b)$ where $a+b = k+1$ we had to got through a diagonals with $1,2,3,...,k-1$ terms. That is $\sum_{j=1}^{a+b-1} j$ terms. Then thes is the $a$th term so $(a,b) = f(a+ \sum_{j=1}^{a+b-1})$ or

$f^{-1}(a,b) = a+\sum_{j=1}^{a+b-1} j$.

That is enough to define $f: \mathbb N\to \mathbb N \times \mathbb N$. Note: You DON'T need to actually solve and write a formula for a bijection to know that it exists.

We can show that $f^{-1}(a,b) = a+\sum_{j=1}^{a+b-1}j$ is a bijection because all for all natural $n$ there is a unique value of $k$ so that $1+2+ .... + k \le n < 1+2+.... + k + (k+1)$ so let $a = n-k$ and let $b=k+1-a$ so $f^{-1}(a,b)=n$ so $f^{-1}$ is surjective. And if $f^{-1}(a,b) = f^{-1}(\alpha, \beta) = n$ we must have that $a+b-1= k =\alpha + \beta -1$ and that $a=n-k=\alpha$ and $b=k+1-a=k+1-\alpha = \beta$ so $(\alpha, \beta)=(a,b)$ so $f^{-1}$ is injective.

And so $f^{-1}$ is a bijections from $\mathbb N\times \mathbb N\to \mathbb N$ so $f:\mathbb N \to \mathbb N\times \mathbb N$ is a bijection.

Then we know that $g:\mathbb N \to \mathbb Z$ via $g(n) = \frac {n+1}2$ if $n$ is odd (maps the odd numbers to positive integers) and $g(n) =-(\frac n2 -1)$ if $n$ is even (maps the even numbers to non-positive integers) is a bijections.

We know this is surjective. If $z\in \mathbb Z$ and $z > 0$ then $2z- 1\in \mathbb N$ and is odd so $g(2z-1) = \frac{(2z-1)+1}2 = z$. ANd if $z \le 0$ then $-z\ge 0$ and $-z + 1\in \mathbb N$ and $2(-z+1)$ is even so $f(2(-z+1))= -(\frac {2(-z+1)}2-1)=-((-z+1)-1)=-(-z)=z$. So $g$ is surjective.

And if $g(n)=g(m)=z$ then either $z>0$ and therefore $n,m$ are both odd and $\frac{n+1}2 = \frac {m+1}2$ so $m =n$ or $z\le 0$ and $n,m$ are both even so $-(\frac n2 -1)=-(\frac m2-1)$ and $m =n$. So $f$ is surjective.

So combining we can go from $\mathbb Z \times \mathbb N \to \mathbb N \times \mathbb N \to \mathbb N$ by considering

For $(a,b)$ $a\in \mathbb Z$ and $b \in \mathbb N$ we can define $h^{-1}(a,b) = f^{-1}(g^{-1}a, b)$. $(a,b)\in \mathbb Z\times \mathbb N$ so $(g^{-1}(a),b) \in \mathbb N\times \mathbb N$ and so $f^{-1}(g^{-1}(a),b)\in \mathbb N$. And we know $h^{-1}: \mathbb Z \times \mathbb N \to \mathbb N$ is a bijection because it is a composition of bijections.

So $h:\mathbb N\to \mathbb Z \times \mathbb N$ is a bijection.

Again. We don't need a formula or an equation to know that something is a bijection.

But if you want.

To find $h(n)$. Find the unique $k$ so that $1+2+3+.... + k \le n < 1+2+3 +..... +k + (k+1)$.

Let $a = n-k$ and let $b = k+1-a$. Now let $c = \frac {a+1}2$ if $a$ is odd or $c =-(\frac a2 -1)$ if $a$ is even.

$h(n) = (c,a)$.