План доказательства и сравнительный обзор способов перечисления.
Краткий итог: множество $\mathbb{Q}\cap (a,b)$ счётно бесконечно (имеет мощность ${\aleph }_0$).
План доказательства (шаги):
1. Показать, что $\mathbb{Q}$ — счётно. Конструкция: рассмотреть все упорядоченные пары $(p,q)\in \mathbb{Z}\times \mathbb{N}$ (с $q>0$) и сопоставить им рациональные $p/q$. Перечисление пар по неубыванию суммы $|p|+q$ (внутри равных сумм — по $p$) даёт сюръекцию $\mathbb{N}\to \mathbb{Q}$; при устранении повторов получаем биекцию с $\mathbb{N}$. Это доказывает счётность $\mathbb{Q}$.
2. Так как $\mathbb{Q}\cap (a,b)\subset \mathbb{Q}$, оно не более чем счётно. Остаётся показать, что оно бесконечно: по плотности рациональных между любыми двумя различными числами есть рационал. Тогда, взяв, например, последовательность $r_1\in (a,b)$, затем $r_2\in (a,r_1)$, и т.д., получаем бесконечный набор различных рационалов в $(a,b)$.
3. Явное перечисление для $\mathbb{Q}\cap (a,b)$: перечислим все пары $(p,q)\in \mathbb{Z}\times \mathbb{N}$ в порядке, указанном в пункте 1, и для каждой пары берём дробь $p/q$; пропускаем дроби, не лежащие в $(a,b)$, и повторяющиеся значения (т.е. не приведённые дроби). Это даёт явную последовательность, перечисляющую все элементы $\mathbb{Q}\cap (a,b)$.
Сравнение разных техник перечисления (коротко):
- Перечисление пар $(p,q)$ (диагональный метод, упорядочивание по $|p|+q$):
- Плюсы: простое и стандартное, конструктивное; легко доказать, что охватывает все рационалы.
- Минусы: требует явного удаления повторов (неприведённых дробей).
- Перечисление только приведённых дробей $p/q$ с $\gcd (p,q)=1,q>0$, упорядоченных по $|p|+q$:
- Плюсы: нет повторов, даёт более «чистую» последовательность.
- Минусы: надо следить за условием простоты дроби при переборе — чуть сложнее реализовать вручную.
- Дерево Кэликена—Вилфа (Calkin–Wilf tree):
- Плюсы: каждая положительная приведённая дробь встречается ровно один раз; очень элегантная рекурсивная конструкция; удобно генерировать положительные рационалы.
- Минусы: даёт только положительные числа (нужно дополнительно учесть ноль и отрицательные); порядок не монотонен, фильтрация по интервалу требует пропуска неподходящих элементов.
- Последовательности Фарея:
- Плюсы: дают хорошие аппроксимации рационалами с ограничёнными знаменателями; соседи имеют полезные свойства.
- Минусы: по каждому порядку даётся конечное множество, для полного перечисления нужно брать объединение по всем порядкам и удалить повторы — менее прямолинейно для доказательства счётности.
- Бесконечная аргументация «подмножество счётного множества»:
- Плюсы: самая короткая и понятная «абстрактная» аргументация (т. е. $\mathbb{Q}$ счётно ⇒ любая подсеть не более счётна); вместе с аргументом о бесконечности даёт итог.
- Минусы: не даёт явного перечисления элементов (неконструктивна).
К чему приводит выбор метода:
- Если достаточно доказать существование перечисления — достаточно аргумента «подмножество счётного множества + бесконечность».
- Если нужен явный список без повторов — лучше перечислять приведённые дроби (или использовать Calkin–Wlf с доработкой).
- Если важны дополнительные свойства (например, управление знаменателями или соседство дробей) — используют Farey или специализированные построения.
Это и есть план доказательства и краткое сравнение основных техник перечисления.