Коротко: дать несколько различных доказательств счётности $\mathbb{Q}$, кратко их описать, привести ключевые формулы и сравнить по наглядности, строгости и пригодности для урока.
1) Диагональная нумерация (классическая «сеточка»).
- Идея: представить все дроби $\frac{p}{q}$ (например, положительные с $p,q\in \mathbb{N}$) в виде бесконечной сетки и перечислять по диагоналям, пропуская несократимые дубликаты.
- Формулировка: перечислим пары $(p,q)\in \mathbb{N}\times \mathbb{N}$ по сумме индексов $p+q$ (или по диагоналям). Каждая пара даёт дробь $\frac{p}{q}$; убираем повторы (сокращённые).
- Ключевое: есть явная сюръекция $\mathbb{N}\to {\mathbb{Q}}_{>0}$ (после удаления дубликатов) — значит счётно.
- Плюсы: очень наглядна, легко рисовать на доске.
- Минусы: требуется объяснить удаление дубликатов; формально нужно обосновать, что обход по диагоналям даёт последовательность (то есть сопоставление с $\mathbb{N}$).
2) Разложение на пары: $\mathbb{Q}$ как часть $\mathbb{Z}\times \mathbb{N}$ и ясно выраженная биекция с $\mathbb{N}$.
- Идея: любое рациональное представимо как $\frac{p}{q}$ с $p\in \mathbb{Z},q\in \mathbb{N}$. Покажем, что $\mathbb{Z}\times \mathbb{N}$ счётно, а подмножество тоже счётно.
- Пример явной биекции $\mathbb{Z}\to \mathbb{N}$:
$$\psi (n)=\{\begin{array}{ll}0,& n=0,\\ 2n,& n>0,\\ -2n-1,& n<0,\end{array}$$ и затем используем канторову функцию сопряжения для $\mathbb{N}\times \mathbb{N}\to \mathbb{N}$, например
$$\pi (k,l)=\frac{(k+l)(k+l+1)}{2}+l.$$ Композиция даёт явную инъекцию/биекцию для пар и поэтому для дробей.
- Плюсы: формально строгий и конструктивный метод с явными формулами.
- Минусы: менее интуитивен для новичков (надо ввести кодирование $\mathbb{Z}$ в $\mathbb{N}$ и канторову пару).
3) Счётный союз множеств (по знаменателям).
- Идея: для каждого $q\in \mathbb{N}$ множество чисел вида $\{p/q:p\in \mathbb{Z}\}$ конечно или счётно; $\mathbb{Q}={\bigcup }_{q\in \mathbb{N}}\{p/q\}$. Так как объединение счётного числа счётных множеств счётно, то $\mathbb{Q}$ счётно.
- Формально: доказать лемму «счётный союз счётных множеств счётен» (можно с диагонализацией по матрице).
- Плюсы: очень коротко и чисто логически, хороша как теоретический аргумент.
- Минусы: требует доказательства вспомогательного факта о счётном союзе; не даёт явного удобного перечисления без дополнительной работы.
4) Calkin–WILF дерево (конструктивное, без дублирования).
- Идея: дерево, в корне $1/1$; каждому узлу $p/q$ сопоставляем детей $\frac{p}{p+q}$ и $\frac{p+q}{q}$. Обход в ширину даёт перечисление всех положительных рациональных в несократимом виде и без повторов.
- Ключ: каждое положительное рациональное встречается ровно один раз в дереве.
- Плюсы: даёт простую алгоритмическую конструкцию (подходит для программирования и демонстрации). Очень наглядна.
- Минусы: требуется объяснить и доказать уникальность появления; чуть более «алгоритмическая» идея, чем чистая диагональ.
5) Stern–Brocot дерево / перечисление по возрастанию.
- Идея: строится через медианты; при обходе в ширину получаем все положительные рациональные в несократимом виде; удобно, если хочется отсортированную последовательность.
- Плюсы: наглядно и даёт впорядоченную (по величине) последовательность.
- Минусы: требуется чуть больше теории о медиантах и доказательство полноты.
6) Кодирование через простые (Гёдель-тип).
- Идея: представить рационал $\frac{\pm p_1^{a_1}\cdots }{p_1^{b_1}\cdots }$ через степени простых и закодировать в натуральное число. Формально даёт явную инъекцию $\mathbb{Q}\to \mathbb{N}$.
- Плюсы: очень строгий, пригоден в теории вычислимости/логике.
- Минусы: скучен и нефилософски трудоёмок для начальной лекции.
Сравнение (наглядность / строгость / удобство в аудитории)
- Наиболее наглядна: диагональная сетка и деревья (Calkin–WILF, Stern–Brocot). Хорошо иллюстрируются рисунком, легко воспринимаются визуально.
- Наиболее строгие/формальные: кодирование через пары и канторова функция, кодирование через простые — дают явные формулы и простое доказательство биекции/инъекции.
- Удобство для урока:
- Для первого знакомства: диагональная нумерация или «по знаменателям» (счетный союз) — коротко и понятно.
- Для алгоритмической демонстрации или задания программирования: Calkin–WILF.
- Для курса анализа/теории множеств, где важны явные биекции: канторова пара и явные формулы.
- Дополнение: разумный путь обучения — сначала показать диагональ или объединение по знаменателям (интуиция), затем дать строгое формальное доказательство через пары/канторову биекцию или Calkin–WILF как конструкцию без повторов.
Резюме (рекомендация для преподавателя): начните с диагональной иллюстрации и соедините с простым аргументом «по знаменателям» (коротко). Для полноты — привести одну явную биекцию через $\mathbb{Z}\times \mathbb{N}$ и канторову функцию или показать Calkin–WILF как конструктивный метод без повторов.