Why is $\mathbb Q $ (rational numbers) countable?

Question

By definition, a set $S$ is called countable if there exists an bijective function $f$ from $S$ to the natural numbers $N$.

If we take a function $g\colon\mathbb{Z\times N\to Q}$ given by $g(m, n) = \frac{m}{ n} $ to "construct" rational numbers, $g$ would only be a surjection from the countable set $\mathbb{Z\times N}$ to $\mathbb Q$. It's not injective, or is it?

Answer 1

Explicit bijections are overrated.

We can prove the following three things (without the axiom of choice, which has been mentioned in the comments):

1. If $A\subseteq\Bbb N$ then it is either finite or countably infinite.
2. If $f\colon\Bbb N\to X$ is surjective, then $X$ is finite or countably infinite.
3. There is a surjection from $\Bbb N$ onto $\Bbb Q$.

The first proof is quite easy, we simply start to enumerate $A$ according to the order induced from the usual order of the the natural numbers. Either we "finish" the set, in which case it's finite, or the enumeration produces a bijection of $A$ with $\Bbb N$.

The second proof is also easy, since the function is a surjection, every $x\in X$ has a least $n\in\Bbb N$ such that $f(n)=x$. This minimal $n$ is unique, so we defined an injection from $X$ into $\Bbb N$, which is a bijection with a subset of $\Bbb N$. By the first claim, $X$ is finite or countably infinite.

The last proof is also not difficult. First write a surjection of $\Bbb N$ onto $\Bbb{N\times N}$ and a surjection from $\Bbb N$ onto $\Bbb Z\setminus\{0\}$, compose them to a surjection from $\Bbb N$ onto $\Bbb{N\times (Z\setminus\{0\})}$. Then you the surjection you have defined, $(n,m)\mapsto\frac nm$.

Now we can conclude the fourth statement:

4. $\Bbb Q$ is countably infinite.

Of course $\Bbb Q$ is not finite, and since there is a surjection from $\Bbb N$ onto $\Bbb Q$, the claim is proved.

Answer 2

You are correct. In fact, this is not the function used to count rational numbers.

Imagine listing all of those numbers excluding the ones in which the fraction can be simplified.

A possible bijection could be that function that gives the position of the rational number in that list. Since the list contains each rational number, the function is surjective. But each number has a different position in the list: hence, the function is surjective.

This is an "intuitive" point of view. If you want a more formal demonstration here it is:

Define the mapping $\psi: \mathbb Q \rightarrow \mathbb Z \times \mathbb N$ such that for every $\frac{m}{n} \in \mathbb Q$ in canonical form $\psi(\frac{m}{n})=(m,n)$

Then $\psi$ is clearly injective. From the fact that cartesian product of countably infinite sets is countably infinite, $\mathbb Z \times \mathbb N$ is countable. Because the domain of injection to a countable set is countable, $\mathbb Q$ is countable.

Answer 3

Here's an intuitive but very helpful to understand picture.

Answer 4

Consider the plane $\mathbb Z\times\mathbb Z$. Clearly you can fill it by spiraling from the origin. Avoid counting the undefined fractions and those already seen before (after simplification).

Answer 5

The Farey sequence gives a bijection between the nonnegative rationals and $\mathbb{N}$.
Step 0: Start with two numbers $\frac01,\frac10$ ($\frac10$ is just a place-holder.) $\frac01$ is rational number $1$.
Step N: between consecutive numbers$\frac{a}{b},\frac{c}{d}$, write $\frac{a+c}{b+d}$ These are rationals number $2^{N-1}+1$ to number $2^N$
The sequence starts
$$\frac01,\frac10\\ \frac01,\frac11,\frac10\\ \frac01,\frac12,\frac11,\frac21,\frac10\\ \frac01,\frac13,\frac12,\frac23,\frac11,\frac32,\frac21,\frac31,\frac10$$
To include the negatives, put the negative numbers in the even positions and positive numbers in the odd positions.

Answer 6

Let us enumerate the elements of $\{0\}\cup\{1,2,...\}\!\!\times\!\!\{1,2,...\}\!\!\times\!\!\{+,-\}$. Start with $0$. Then, for given $n$, list all $2n$ elements $(j,k,\pm)$ such that $j+k=n$, successively in the order $(1,n-1),...,(n,1)$, with $+$ signs attached, followed by the same elements with $-$ signs. Do this consecutively for $n=1,2,...$. This list is countable. Now run through the list in order and delete any element $(l,m,\pm)$ for which there was an earlier-occurring element $(j,k,\pm)$ (with the same sign) such that $j/k=l/m$. Now we have a countable list that is in one-to-one correspondence with the rational numbers $\Bbb Q$: namely, $(j,k,\pm)$ corresponds to $q\in\Bbb Q$ if and only the signs are the same and $j/k=q$, with the initial $0$ corresponding to the $0$ in $\Bbb Q$.