§ 4. Счетные и несчетные множества

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

1. Счетные множества

Определение 1. Множество X называется счетным, если оно равномощно множеству натуральцых чисел, т. е.

Утверждение, а) Бесконечное подмножество счетного множества счетно.

Объединение множеств конечной или счетной системы счетных множество есть множество счетное.

Достаточно проверить, что всякое бесконечное подмножество Е множества натуральных чисел равномощно Нужное биективное отображение построим следующим образом. В имеется минимальный элемент, который мы сопоставим числу и обозначим . Множество Е бесконечно, поэтому непусто. Минимальный элемент множества сопоставим числу 2 и назовем его Затем рассмотрим Поскольку Е — бесконечное множество, то построение не может оборваться ни на каком шаге с номером и, как следует из принципа индукции, таким способом каждому числу будет сопоставлено некоторое число . Построенное отображение , очевидно, инъективно.

Остается проверить его сюръективность, т. е. что Пусть . Множество конечно, и тем более конечно его подмножество . Пусть k — число элементов в последнем множестве. Тогда по построению

Если — счетная система множеств, причем каждое множество само счетно, то поскольку мощность множества состоящего из элементов где не меньше мощности каждого из множеств то X — бесконечное множество. Элемент можно отождествить с задающей его упорядоченной парой натуральных чисел. Тогда мощность X не больше мощности множества таких упорядоченных пар. Но отображение задаваемое формулой как легко проверить, биективно (оно имеет наглядный смысл: мы нумеруем точки плоскости с координатами последовательно переходя от точек одной диагонали, где постоянно, к точкам следующей, где эта сумма на 1 больше).

Таким образом, множество упорядоченных пар натуральных чисел счетно. Но тогда и, поскольку X — бесконечное множество, на основании доказанного в а) заключаем, что

Из доказанного утверждения следует, что любое подмножество счетного множества либо конечно, либо счетно. Если про множество известно, что оно либо конечно, либо счетно, то говорят, что оно не более чем счетно (равносильная запись:

Мы можем, в частности, утверждать теперь, что объединение не более чем счетного семейства не более чем счетных множеств само не более чем счетно.

Следствия.

Этот результат означает, что прямое произведение счетных множеств счетно.

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

Рациональное число — задается упорядоченной парой целых чисел.

Две пары задают одно и то же рациональное число в том и только в том случае, когда они пропорциональны. Такимубразом, выбирая каждый раз для записи рационального числа единственную пару с минимальным возможным натуральным знаменателем мы получим, что множество равномощно некоторому бесконечному подмножеству множества Но и, значит,

4) Множество алгебраических чисел счетно.

Заметим сначала, что из равенства по индукции получаем, что для любого выполнено

Элемент есть упорядоченный набор к рациональных чисел.

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

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