$\Bbb Z$ $\times$ $\Bbb N$ Countably Infinite 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.
 A: 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$
A: 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)$.
