Определение. Множество, эквивалентное множеству всех натуральных чисел, называют счетным множеством.
Можно сказать иначе: множество счетно, если все его элементы можно занумеровать всеми натуральными числами.
Всякое бесконечное подмножество счетного множества
счетно.
Действительно, пусть дано счетное множество
а — его бесконечное подмножество. Располагая в порядке возрастания номеров все элементы подмножества
можно перенумеровать их заново всеми натуральными числами, взятыми по порядку (в роли нового номера будет выступать индекс . Следовательно,
счетно.
Объединение конечной или счетной совокупности счетных множеств есть счетное множество.
Объединением множеств называется множество, состоящее из всех элементов, принадлежащих хотя бы одному из этих множеств, и обозначается через
.
Рассмотрим сначала случай конечного числа множеств. Пусть даны счетные множества
и
Выпишем элементы множеств в виде следующей таблицы:
Теперь перенумеруем заново все элементы этой таблицы, располагая их по столбцам:
Если множества содержат некоторые общие элементы, то один и тот же элемент может повториться несколько раз. В этом случае нумеруем его только один раз, например, тогда, когда этот элемент встретится впервые и пропускаем при последующих встречах с ним. Таким образом, все элементы множества
могут быть перенумерованы, т.е.
счетно.
Пусть теперь
где все множества счетны. Выпишем элементы множеств
в виде таблицы, аналогичной таблице
, но содержащей счетное множество строк. Элементы такой таблицы можно перенумеровать располагая их по группам элементов с равной суммой индексов:
При этом повторяющиеся элементы так же, как и в предыдущем случае, нумеруем по одному разу. Таким образом, все элементы множества могут быть перенумерованы, т.е. множество
счетно.
Множество всех рациональных чисел счетно.
Действительно, множество всех рациональных чисел есть объединение следующих счетных множеств:
т.е. . Множества
, составляют счетную совокупность счетных множеств. Из 11.3 следует, что их объединение
счетно.