Математика · объяснение и практика

Как перечислить положительные дроби, не пропустив знаменатель

Постройте порядок перечисления положительных рациональных чисел: обойдите пары по диагоналям и уберите повторные записи равных дробей.

Синяя и оранжевая половины складываются в целый круг.

В теме Доказательства и комбинаторные модели · Учебная карта

Главная мысль

Положительные рациональные числа можно перечислить по возрастанию суммы числителя и знаменателя, оставляя только несократимые дроби. Каждая такая пара достигается за конечное число шагов.

Почему движение по одной строке не подходит

Расположим дроби в бесконечной таблице: строка задаёт положительный числитель, столбец — положительный знаменатель. Если сначала перебирать все знаменатели при числителе один, переход ко второй строке никогда не произойдёт. Так нельзя доказать, что перечисление охватило таблицу. Нужен порядок, который за конечное время доходит до каждой конкретной клетки.

Выбираем диагонали с постоянной суммой числителя и знаменателя. В каждой диагонали лишь конечное число положительных целых пар. После её полного просмотра переходим к следующей сумме. Любая заданная пара имеет некоторую конечную сумму, а перед ней стоит только конечное число диагоналей. Поэтому клетка с этой парой будет просмотрена на определённом конечном шаге.

Одно число не должно получать бесконечно много мест

Дроби 1/2, 2/4 и 3/6 занимают разные клетки, но обозначают одно число. Чтобы получить перечисление самих чисел без повторов, сохраняем только пары с взаимно простыми числителем и знаменателем. У каждого положительного рационального числа есть единственная такая запись с положительным знаменателем. Проверка на общий делитель отбрасывает лишние клетки, не удаляя число целиком.

Например, число 4/7 появится на диагонали с суммой одиннадцать, потому что числитель и знаменатель взаимно просты. Равная ему дробь 8/14 позже будет пропущена. Нельзя просто запретить большие знаменатели: это исключило бы другие настоящие числа. Удаляется только повторная запись уже представимого значения, а не целый диапазон размеров.

Пример

Почему дробь 5/8 не потеряется при диагональном обходе с отбрасыванием сократимых дробей?

Её клетка находится на конечной диагонали с суммой 13. Числа 5 и 8 взаимно просты, поэтому фильтр оставит клетку. Все предыдущие диагонали конечны, следовательно, номер в списке также конечен.

Плотность не мешает перечислению

Между любыми двумя различными рациональными числами есть ещё рациональное: достаточно взять их среднее. Это свойство называется плотностью, но оно не означает невозможность перечисления. Наш порядок не возрастает по величине числа. После небольшой дроби вполне может идти большая; от списка требуется покрытие без повторов, а не монотонное движение по числовой оси.

Для перечисления всех рациональных чисел добавим ноль, а затем будем чередовать положительное число из полученного списка и противоположное ему отрицательное. Каждое значение по-прежнему получит конечный номер. Аналогичная попытка перечислить все действительные числа не следует из этого доказательства: таблица целых пар описывает только рациональные отношения, а не произвольные бесконечные десятичные записи.

От чтения к действию

А теперь — вы

При диагональном обходе клетки p/q просматриваются по сумме p+q. Какое обоснование гарантирует достижение клетки 7/10?

Частые вопросы

Счётное множество обязательно имеет промежутки между соседними числами?

Нет. Рациональные числа плотны, хотя счётны. Соседство по номеру в перечислении не равно соседству по величине на прямой.

Почему можно пропускать сократимые дроби?

Потому что после сокращения остаётся несократимая положительная пара того же числа. Именно она гарантированно включается в перечисление.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться