# Rational Numbers are Countably Infinite

## Theorem

The set $\Q$ of rational numbers is countably infinite.

## Proof 1

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 $\N$.

$\blacksquare$

## Proof 2

Let us define the mapping $\phi: \Q \to \Z \times \N$ as follows:

- $\forall \dfrac p q \in \Q: \phi \left({\dfrac p q}\right) = \left({p, q}\right)$

where $\dfrac p q$ is in canonical form.

Then $\phi$ is clearly injective.

From Cartesian Product of Countable Sets is Countable, we have that $\Z \times \N$ is countably infinite.

The result follows directly from Domain of Injection to Countable Set is Countable.

$\blacksquare$

## Proof 3

For each $n \in \N$, define $S_n$ to be the set:

- $S_n := \left\{{\frac m n: m \in \Z}\right\}$

By Integers are Countably Infinite, each $S_n$ is countably infinite.

Because each rational number can be written down with a positive denominator, it follows that:

- $\forall q \in \Q: \exists n \in \N: q \in S_n$

which is to say, $\displaystyle \bigcup_{n \mathop \in \N} S_n = \Q$.

By Countable Union of Countable Sets is Countable, it follows that $\Q$ is countable.

Since $\Q$ is manifestly infinite, it is countably infinite.

$\blacksquare$

## Proof 4

Let $Q_\pm = \left\{{q \in \Q: \pm q > 0}\right\}$.

For every $q \in Q_+$, there exists at least one pair $\left({m, n}\right) \in \N \times \N$ such that $q = \frac m n$.

Therefore, we can find an injection $i: Q_+ \to \N \times \N$.

By Cartesian Product of Natural Numbers, $\N \times \N$ is countable.

Hence $Q_+$ is countable, by Domain of Injection to Countable Set is Countable.

The map $-: q \mapsto -q$ provides a bijection from $Q_-$ to $Q_+$, hence $Q_-$ is also countable.

Hence $\Q$ is countable.

$\blacksquare$

## Sources

- Murray R. Spiegel:
*Theory and Problems of Complex Variables*(1964)... (previous)... (next): $1$: Supplementary Problems: $155$ - Allan Clark:
*Elements of Abstract Algebra*(1971)... (previous)... (next): $\S 15 \epsilon$ - H. Jerome Keisler and Joel Robbin:
*Mathematical Logic and Computability*(1996)... (previous)... (next): Appendix $\text{A}.6$: Cardinality: Problem $\text{A}.6.2$