Счетное множество — самое маленькое из бесконечных.
Мы уже говорили, что любая бесконечная часть множества натуральных чисел счетна. Это означает, что не может существовать бесконечное множество, мощность которого была бы меньше мощности счетного множества. Докажем теперь, что в каждом бесконечном множестве есть счетное подмножество. Отсюда будет следовать, что мощность счетного множества не больше мощности любого бесконечного множества, то есть что эта мощность — самая маленькая из бесконечных.
Чтобы выбрать счетное подмножество из бесконечного множества A, поступим так. Выберем один элемент x1 — это можно сделать, так как множество A бесконечно и, во всяком случае, не пусто. Ясно, что после удаления элемента x1 множество A не исчерпывается, и мы сможем выбрать из него второй элемент x2. После этого выберем третий элемент x3 и т. д. В результате мы извлечем из множества А счетное подмножество занумерованных элементов
X = {x1, x2, ..., xn, ...}.
Немного усовершенствовав это доказательство, можно добиться, чтобы после удаления счетного подмножества осталось бесконечное множество. Для этого надо после извлечения подмножества X вернуть обратно все элементы с четными номерами. В результате получится, что мы извлекли счетное подмножество
Y = {x1, x3, x5, ...},
а оставшееся множество еще содержит бесконечное множество элементов {x2, x4, x6, ..., x2n, ...} и, быть может, еще много других элементов.
Нетрудно доказать следующие теоремы.
Мощность бесконечного множества не изменяется от прибавления к нему счетного множества.
Мощность несчетного множества не меняется от удаления из него счетного множества.
Эти теоремы еще раз подтверждают, что счетные множества — самые малые из бесконечных множеств.