Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ.docx
Скачиваний:
183
Добавлен:
01.05.2025
Размер:
262 Кб
Скачать
☆
    1. Некоторые свойства бесконечных множеств

Уже отмечалось, что конечное множество не равномощно своей части, в то же время, бесконечное множество может быть равномощным своей части. Оказывается, это характеристическое свойство бесконечных множеств.

Теорема 12. Всякое бесконечное множество равномощно некоторой своей части.

Доказательство. Пусть A – бесконечное множество. По Теорема 9, существует счетное множество . Не исключается случай равенства этих множеств! Построим следующее отображение:

f(x) = x при x , f(ai) = ai+1 (i=1,2,…).

Очевидно, что f – взаимно однозначное соответствие между A и A\{a1}, что и требовалось.

Теорема 8 утверждает, что множество [0,1] «массивнее» множества N. Между этими двумя множествами существует тесная связь.

Теорема 13. |[0,1]|=

Для доказательства надо установить взаимно однозначное соответствие между булеаном множества N и отрезком [0,1]. Нам потребуется запись чисел из отрезка [0,1] в двоичной системе счисления, т.е. в виде , где =0 или 1 при n=1,2,… (вам известно, как число представить в таком виде). Пусть AN. Сопоставим ему число в двоичной записи, где тогда и только тогда, когда nA. По числу множество A восстанавливается однозначно, т.е. установлено взаимно однозначное соответствие между множеством записей вида и множеством (В этом рассуждении есть пробел, найдите его! Его нетрудно заполнить, но мы этого делать не будем).

Мощность точек отрезка [0,1] называется мощностью континуума.

Отмечалось, что счетные множества это самые «маленькие» бесконечности. Естественным является вопрос: существует ли «самая большая» бесконечность или дорога вверх не имеет конца? Оказывается, справедливо второе: для каждого множества найдется более «мощное», а именно:

Теорема 14. (Вторая теорема Кантора) для всякого множества A.

Отметим, что в частных случаях этот факт вам уже известен: для конечных множеств это Теорема 1, для счетных – Теорема 13.

Доказательство в некотором смысле аналогично диагональному методу Кантора.

Вначале проверим, что (легкая часть). Рассмотрим подмножество , состоящее из одноэлементных множеств. = , поскольку отображение , имеющее вид , является взаимно однозначным соответствием. Итак, в есть подмножество, равномощное A, что и требовалось.

Докажем теперь, что (трудная часть). Доказательство будем проводить от противного. Пусть напротив . Это значит, что существует взаимно однозначное отображение . Важно, что любое подмножество является образом некоторого элемента множества ! Для каждого элемента a выполняется одно из двух свойств: либо af(a), либо af(a), причем существуют элементы каждого из двух видов: если f(u)=A (по предположению такой элемент существует), то u – элемент первого вида, если f(v)= (по предположению такой элемент также существует), то v – элемент второго вида. Рассмотрим множество, состоящее из элементов второго вида: . По предположению, существует элемент bA, для которого Если наше предположение о равномощности справедливо, то либо bV, либо bV.

Пусть bV. По определению V это означает, что – противоречие! Пусть теперь bV. Поскольку в V входят ВСЕ элементы A, для которых , то b этим свойством не обладает и потому bV. И здесь противоречие!

Мощность множества иногда называют мощностью гиперконтинуума.