Set Theory · Countable Sets

Lesson 2

Nikolai Chukhin · Alexander S. Kulikov

Theorem. The set \(\mathbb{Q}\) of rational numbers is countable.

Proof. Positive rational numbers can be enumerated by diagonals, skipping repetitions (for example, \(\frac{1}{2}= \frac{2}{4}\)).

After that, we can start with zero and take one positive and one negative number: \[\left\{0, 1, -1, 2, -2, \frac{1}{2}, -\frac{1}{2}, \frac{1}{3}, -\frac{1}{3}, 3, -3, 4, -4, \frac{3}{2}, -\frac{3}{2}, \dotsc \right\} \ .\]◼

For the curious 🤓

It turns out that there is a function that "generates" all positive rational numbers, so that each number appears exactly once! The Calkin-Wilf function: \[x \mapsto f(x) = \frac{1}{\lfloor x \rfloor + 1 - \{x\}}\ .\] This is how the beginning of this sequence looks: \[\frac{1}{1}\mapsto \frac{1}{2}\mapsto \frac{2}{1}\mapsto \frac{1}{3}\mapsto \frac{3}{2}\mapsto \frac{2}{3}\mapsto \frac{3}{1}\mapsto \frac{1}{4}\mapsto \dotsb\]

from math import floor
from fractions import Fraction


def next_rational(x: Fraction) -> Fraction:
    return Fraction(1, floor(x) + 1 - (x % 1))


a = 1
for _ in range(20):
    print(a)
    a = next_rational(a)

1
1/2
2
1/3
3/2
2/3
3
1/4
4/3
3/5
5/2
2/5
5/3
3/4
4
1/5
5/4
4/7
7/3
3/8