How can $\mathbb Q$ be countable, when there is no “next” rational number?

Question

I understand this proof that $\mathbb{Q}$ is countable:

The rational numbers are arranged thus: $$\displaystyle \frac 0 1, \frac 1 1, \frac {-1} 1, \frac 1 2, \frac {-1} 2, \frac 2 1, \frac {-2} 1, \frac 1 3, \frac 2 3, \frac {-1} 3, \frac {-2} 3, \frac 3 1, \frac 3 2, \frac {-3} 1, \frac {-3} 2, \frac 1 4, \frac 3 4, \frac {-1} 4, \frac {-3} 4, \frac 4 1, \frac 4 3, \frac {-4} 1, \frac {-4} 3 \ldots$$ It is clear that every rational number will appear somewhere in this list. Thus it is possible to set up a bijection between each rational number and its position in the list, which is an element of $\mathbb N$. $\square$

However, given any rational number, say $3$, there is no "next" rational number, as $\mathbb Q$ is dense in $\mathbb R$. But, given any natural number, we can determine the next natural number (i.e. its successor, given by $S(n)=n+1$).

This seems to contradict the fact that there's a bijection between $\mathbb Q$ and $\mathbb N$. Could someone clear this up?

(Forgive me for any misconceptions/mistakes- I'm an amateur in set theory)

Answer 1

How can Q be countable, when there is no “next” rational number ?

The reason that there is no “next” rational number does not imply that the set is uncountable.

Just imagine, for instance, the following function: $f(n)=\begin{cases}0,\qquad n=0\\1/n,\quad n\neq0\end{cases}$. Obviously, then,

$f\big(\mathbb Z\big)$ is countable. However, $0\in f\big(\mathbb Z\big)$ does not possess a “next” $\big($or even “previous”$\big)$ element

in $f\big(\mathbb Z\big)$, despite the fact that it does so in $\mathbb Z$.

Answer 2

The 'next' rational after $\frac{3}{1}=3$, in this context, is $\frac{3}{2}$. If you like let $\varphi$ be the bijection $\varphi:\mathbb{N}\rightarrow \mathbb{Q}$. Then we do have

$$\varphi(12)=\frac{3}{1}=3$$ and perhaps we might write $$S^\varphi_{\mathbb{Q}}(3):=\varphi(S(\varphi^{-1}(3)))=\varphi(S(12))=\varphi(13)=\frac{3}{2},$$ where $S:\mathbb{N}\rightarrow\mathbb{N}$ is the successor function $S(n)=n+1$ and we might call $S^\varphi_\mathbb{Q}$ is the successor function of $\mathbb{Q}$ with respect to $\varphi$ defined by

$$S_\mathbb{Q}^\varphi:\mathbb{Q}\rightarrow \mathbb{Q},\,\,q\mapsto \varphi(S(\varphi^{-1}(q)))$$

Answer 3

First let's ask a different question.

How can $\Bbb Z$ be countable, if every number is a successor in the integers, whereas in $\Bbb N$ there is a number which is not a successor?

The answer to this question, and the answer to the question why is $\Bbb Q$ countable are the same answer: Because a bijection is not order preserving.

Cardinality of a set is what remains when you "shake off" any structure it has or might have had. Namely, cardinality is determined by functions which are not necessarily preserving any structure whatsoever (order, addition, multiplication, etc.).

It is true that it's harder to see why $\Bbb Q$ is countable compared to $\Bbb Z$, especially when $\Bbb R$ is not countable and both are dense ordered sets. But if you understand why $\Bbb Z$ is countable, then you shouldn't have any difficulties understand the case for $\Bbb Q$: we can prove that there is a bijection between $\Bbb Q$ and $\Bbb N$, and therefore it is countable.

Answer 4

When you say "next", you are probably transferring a feature from $\Bbb N$ that $\Bbb Q$ lacks, namely well-orderedness in the natural order.

But $\Bbb Q$ can be given other orders that allow each element to have a successor, and your partial organized list is a case in point. Any bijection with the naturals would induce a well ordering on $\Bbb Q$ by simply enforcing the order on the natural numbers on their images. Conversely, you can create an order on the naturals by finding a bijection of $\Bbb Q$ with $\Bbb N$ and then using $\Bbb Q$'s natural order to put a new order on the natural numbers in which elements wouldn't have successors.

Having successors for elements in a particular order simply doesn't have much to do with cardinality. You can have sets of large size where elements have successors, and sets of large size that don't.

Density and cardinality are two distinct types of "largeness." Lack of successors does not cause the cardinality to go out of control. It just speaks to the organization of the ordered set.

Answer 5

Basically your problem is that you don't distinguish between the ordered set $(\mathbb{Q},<)$ and the set $\mathbb{Q}$. Notice that you cannot say if a set is dense, well-ordered etc. or not - this is only defined for ordered sets. We have $\mathbb{N} \cong \mathbb{Q}$ (in the category of sets) and $(\mathbb{N},<) \not\cong (\mathbb{Q},<)$ (in the category of ordered sets).

Answer 6

You can't have an order-preserving bijection between the rational numbers and the natural numbers. But you can have a bijection between them. (The same could be said of bijections between the set of natural numbers and the set of integers.)

Answer 7

If you have an ordering of the rationals, then you can define a successor for each rational number. I suspect you want this successor function to be some "nice" function. One example where this actually happens is the ordering given by the Calkin-Wilf tree, where the successor to the rational number $x$ can be written as $$S(x) = {1 \over 2 \lfloor x \rfloor - x + 1},$$ where $\lfloor x \rfloor$ is the greatest integer less than or equal to $x$. The Calkin-Wilf sequence begins $$1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4,\ldots$$ and for example, you can see that the successor of $5/3$ is $${1 \over 2 \lfloor 5/3 \rfloor - 5/3 + 1} = {1 \over 2 - 5/3 + 1} = {1 \over 4/3} = 3/4.$$

It takes a bit of work to show that starting with 1 and iterating this function gives the sequence of positive rationals, with each one occurring once; the original paper of Calkin and Wilf shows this.