Теорема 3. Всякое бесконечное подмножество счетного множества также счетно

Доказательство.

Пусть А – счетное множество и В Ì А также содержит бесконечное число элементов. Представим А в форме последовательности: А ={ a ₁, a ₂, a ₃,…}. Будем рассматривать элементы множества А по порядку, то есть а ₁, затем а ₂, а ₃ и т.д. При этом мы иногда будем «наталкиваться» на элементы подмножества В. Будем ставить этим элементам множества В в соответствие «номер встречи с ним». Тем самым, будет установлено взаимно-однозначное соответствие между В и N, что и говорит о счетности В. <

Суть теорем 2 и 3 можно сформулировать так: счетное множество есть самое маленькое из всех бесконечных множеств.

Теорема 4. Сумма конечного числа счетных множеств есть также счетное множество.

Доказательство.

Пусть для простоты имеются два счетных множества А и В.

А ={ a ₁, a ₂, a ₃,…}.

В ={ b ₁, b ₂, b ₃,…}.

Представим их сумму в виде

А È В ={ a ₁, b ₁, a ₂, b ₂, a ₃, b ₃,…}.

Из теоремы 1 следует, что А È В есть счетное множество.

Однако есть одна тонкость: дело в том, что в множествах А и В могут быть одинаковые элементы, которые надо оставить по одному разу. Но после того, как мы это сделаем, все равно останется бесконечное множество, и, по теореме 3, оно будет счетным.<

Замечание. Заметим, что представление А È В в виде

А È В ={ a ₁, а ₂, a ₃, … b ₁, b ₂, b ₃,…} не доказывало бы нашу теорему. Почему?

Теорема 5 Сумма счетного числа конечных множеств есть конечное или счетное множество.

Доказательство.

Пусть множества А_i, имеют вид

(обратите внимание на нумерацию элементов)

Представим в виде

Мы получили последовательность. Оставляя совпадающие во множествах А_i элементы только по одному разу, мы получим или конечное множество или бесконечное. Но по теореме 3 это бесконечное подмножество может быть только счетным. <

Теорема 6. Сумма счетного числасчетных множеств есть также счетное множество.

Доказательство.

Пусть А_i, есть счетные множества

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

.

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

В заключение этого раздела небольшая задача. Был (а может и есть) польский писатель-фантаст Станислав Лем, произведения которого посвящены теме космоса («Солярис», «Возвращение со звезд», «Эдем»). Среди них есть сборник рассказов «Звездные дневники Иона Тихого». Ион Тихий - это космический барон Мюнхгаузен, который на своей ракете шастает по всей Галактике, попадая при этом в самые невероятные ситуации (например, дерется сам с собой, попав в петлю времени), из которых он всегда выходит с честью.

Так вот, прилетает Ион Тихий в межгалактическую гостиницу. В ней счетное число номеров, и все номера заняты. Ион Тихий обращается к портье, и тот все-таки селит его в эту гостиницу, причем никого из прежних постояльцев не выгоняет. Как поступил портье?