Теорема 2. Любое подмножество счетного множества счетно.

Теорема 3. Сумма двух счетных множеств счетна.

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

- множество значений последовательности .

Тогда сумма  есть множество значений полседовательности , и поэтому счетно.

Можно доказать по индукции, что сумма любого конечного числа счетных множеств счетно.

Следствие 4. Сумма конечного и счетного множества счетна.

Теорема 5. Декартово произведение двух счетных множеств счетно.

Д о к а з а т е л ь с т в о.  Если  и  счетные и бесконечные, то ,  (в силу теоремы 1 §3, глава III).

Если одно из множеств ,  или оба они конечны, то  равномощно некоторому подмножеству произведения , т.е. подмножеству множества .

Таким образом, утверждение данной теории следует из теоремы 2.

Теорема 7. Если - бесконечная последовательность, члены которой – также бесконечные последовательности, то множество  элементов x, являющихся членами последовательности , счетно.

Д о к а з а т е л ь с т в о.  По определению .

Таким образом, - это множество значений последовательности , определенной равенством .

°Теорема 8. Если - последовательность, члены которой – непустые счетные множества, то сумма  счетна.

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

Тогда, согласно аксиоме выбора, существует такая последовательность , что  для каждого . Таким образом, сумма  есть множество тех , для которых существуют такие , что . В силу теоремы 7 это множество счетно.

Замечание. Необходимость применения аксиомы выбора в доказательстве теоремы 8 обусловлена тем, что хотя для каждого множества существует бесконечная последовательность, состоящая из всех его элементов, но для данного множества таких последовательностей бесконечно много и у нас нет способа выделения какой-то одной из них. Другими словами, у нас нет способа сопоставления каждому счетному множеству бесконечной последовательности, содержащей все его элементы.

Примеры счетных множеств.

Пример 1. Множество целых чисел счетно.

Действительно, это множество представляет собой сумму , где - множество чисел . Т.к.  (равномощность этих множеств устанавливает функция ), то множество  и  оба счетны, а тогда  также счетна.

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

В самом деле, последовательность , заданная равенством , содержит в качестве своих членов все положительные рациональные числа и только их. Значит, множество всех положительных рациональных чисел счетно, и поэтому (смотреть пример 1) множество всех рациональных чисел также счетно.

Пример 3. Множество многочленов от одной переменной с целыми коэффицентами счетно.

Действительно, каждому многочлену с целыми коэффицентами взаимно однозначно соответствует последовательность его коэффицентов, а множество всех конечных последовательностей целых чисел (согласно теореме 6) счетно.

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

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

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

Шкала кардинальных чисел.

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

Теорема 1 (о диагонали (Кантор)). Если область определения  функции  содержится в , и значениям функции  служит подмножество множества , то множество  не является значением функции .

Д о к а з а т е л ь с т в о.  Мы должны показать, что  для всех . Из определения множества  следует, что для . Если , получается противоречие .

В случае  теорема 1 имеет наглядную геометрическую интерпритацию.

Представим множество  в виде квадрата (смотреть главу II, §4) и рассмотрим в нем множество . Тогда - проекция на ось одинат  тех точек из , абсциссы которых равны , - проекция на ось ординат множества тех точек диагонали квадрата, которые не принадлежат . Из такого геометрического представления совершенно очевидно, что  для всех . В самом деле :

если , то , но ,

если же , то , но .

Эта интерпритация объясняет название «теоремы о диагонали».

Разница в этом предельном случае будет хотя бы в одну точку .

 , , .

Применим теорему 1 для доказательства существования различных бесконечных мощностей.

Теорема 2. Множество  не равномощно ни самому , ни его подмножеству.

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