Кратко — несколько классических способов и сравнение их свойств.
1) Диагональный (канторовская параинговая функция).
- Построение: сначала бижекция $\mathbb{Z}\leftrightarrow \mathbb{N}$ (например, $g(0)=0,g(n)=2n-1,g(-n)=2n$ для $n>0$), затем бижекция $\mathbb{N}\times \mathbb{N}\leftrightarrow \mathbb{N}$ через кантор-функцию
$\pi (m,n)=\frac{(m+n)(m+n+1)}{2}+n.$ - Применение: кодируем дробь $\frac{p}{q}$ (взяв $q>0$) как пара $(g(p),q)$ и получаем явную биекцию $\mathbb{Q}\to \mathbb{N}$ (при желании отсеиваем нережущиеся копии, беря только несократимые дроби).
- Преимущества: простая, даёт явную формулу; легко доказывает счётность.
2) Счётная сумма счётных множеств (простое доказательство).
- Набор: $\mathbb{Q}=\bigcup _{q=1}^{\infty }\{\frac{p}{q}:p\in \mathbb{Z}\}.$ - Каждое множество в объединении счётно, значит объединение счётно (по теореме: сумма счётного числа счётных множеств — счётна).
- Преимущество: коротко, концептуально; не требует явной нумерации элементов.
3) Перечисление матрицы дробей (диагональный обход с исключением сокращённых).
- Разложим все пары $(p,q)$ на сетке и пройдём по диагоналям (канторовская "зигзагообразная" нумерация), при встрече берем только несократимые дроби с $q>0$.
- Преимущество: даёт явную возрастающую по «весу» нумерацию (по сумме индексов), легко реализуется программно; показывает конструктивное перечисление без пропусков.
4) Деревья: Calkin–Wilf и Stern–Brocot.
- Calkin–Wilf: корень $1/1$; если узел $a/b$, дети — $a/(a+b)$ и $(a+b)/b$. Обход в ширину перечисляет каждое положительное несократимое рациональное ровно один раз. По двоичному представлению номера $n$ можно вычислить $n$-ю дробь.
- Stern–Brocot: строится медиантами; обход даёт все положительные несократимые дроби в возрастающем порядке (полезно для приближений и двоичного поиска рационалов).
- Преимущества: никакого дублирования, эффективные алгоритмы для получения n-й дроби; Stern–Brocot даёт упорядоченную по величине последовательность (важно для приближений).
5) Кодирование простыми (Гёдель-подобно).
- Кодируем пару целых как $2^a{3}^b$ (или любая кодировка через простые). По фундаментальной теореме арифметики это даёт явную биекцию между конечными последовательностями целых и $\mathbb{N}$, откуда следует биекция для $\mathbb{Q}$.
- Преимущество: строгая арифметическая биекция, полезна в теории вычислимости и формальных конструкциях.
Сравнение конструкций (кратко):
- Простота доказательства: объединение счётных множеств и диагональный аргумент — самые простые.
- Явная формула/биекция: кантор-параинг и кодирование простыми дают явную замкнутую формулу.
- Отсутствие дубликатов и конструктивность: Calkin–Wilf и Stern–Brocot — лучшие (каждое положительное рациональное появляется ровно один раз).
- Упорядоченность: Stern–Brocot даёт возрастающий порядок дробей; диагональные методы — по «весу», но не по значению.
- Вычислимость n-й дроби: Calkin–Wilf (и через двоичное представление) даёт простой способ получить n-ю дробь; для кантор-функции тоже можно восстановить пару по номеру, но чаще сложнее интерпретировать как несократимую дробь.
Замечание: чтобы охватить отрицательные и ноль, в любую из конструкций достаточно добавить учёт знака (т.е. бить $\mathbb{Q}=\{0\}\cup \{\pm r:r\in {\mathbb{Q}}_{>0}\}$).