Счётность множества рациональных чисел

Нумерация положительных рациональных чисел

Чтобы оценить количество рациональных чисел, нужно найти мощность их множества. Легко доказать, что множество рациональных чисел счётно. Для этого достаточно привести алгоритм, который нумерует рациональные числа, т. е. устанавливает биекцию между множествами рациональных и натуральных чисел. Примером такого построения может служить следующий простой алгоритм. Составляется бесконечная таблица обыкновенных дробей, на каждой i -ой строке в каждом j -ом столбце которой располагается дробь . Для определённости считается, что строки и столбцы этой таблицы нумеруются с единицы. Ячейки таблицы обозначаются , где i — номер строки таблицы, в которой располагается ячейка, а j — номер столбца.

Полученная таблица обходится «змейкой» по следующему формальному алгоритму.

§ Если текущее положение таково, что i — нечётное, а j = 1, то следующим положением выбирается .

§ Если текущее положение таково, что i = 1, а j — чётное, то следующим положением выбирается .

§ Если для текущего положения сумма индексов нечётна, то следующее положение — .

§ Если для текущего положения сумма индексов чётна, то следующее положение — .

Эти правила просматриваются сверху вниз и следующее положение выбирается по первому совпадению.

В процессе такого обхода каждому новому рациональному числу ставится в соответствие очередное натуральное число. Т. е. дроби 1 / 1 ставится в соответствие число 1, дроби 2 / 1 — число 2, и т. д. Нужно отметить, что нумеруются только несократимые дроби. Формальным признаком несократимости является равенство единице наибольшего общего делителя числителя и знаменателя дроби.

Следуя этому алгоритму, можно занумеровать все положительные рациональные числа. Это значит, что множество положительных рациональных чисел счётно. Легко установить биекцию между множествами положительных и отрицательных рациональных чисел, просто поставив в соответствие каждому рациональному числу противоположное ему. Т. о. множество отрицательных рациональных чисел тоже счётно. Их объединение также счётно по свойству счётных множеств. Множество же рациональных чисел тоже счётно как объединение счётного множества с конечным.

Разумеется, существуют и другие способы занумеровать рациональные числа. Например, для этого можно воспользоваться такими структурами как дерево Калкина — Уилфа, дерево Штерна — Броко или ряд Фарея.

Утверждение о счётности множества рациональных чисел может вызывать некоторое недоумение, т. к. на первый взгляд складывается впечатление, что оно гораздо обширнее множества натуральных чисел. На самом деле это не так и натуральных чисел хватает, чтобы занумеровать все рациональные.