- •Оглавление
- •Введение
- •Комбинаторика в задачах
- •Основной принцип комбинаторики
- •Размещения с повторениями
- •Размещения без повторений
- •Разбиения множеств
- •Перестановки
- •Сочетания (без повторений)
- •Свойства биномиальных коэффициентов
- •Сочетания с повторениями
- •Разные задачи
- •Производящие функции
- •Использование рекуррентных соотношений
- •Формула включений и исключений
- •Комбинаторные величины при больших значениях параметров
- •Множества и функции
- •Множества и простейшие операции над ними
- •Булеан множества
- •Прямое произведение множеств
- •Отношения на множествах
- •Отображения (функции)
- •Мощность множеств
- •Счетные множества
- •Некоторые свойства бесконечных множеств
- •Вопросы для самопроверки
- •Упражнения
- •Основы теории графов
- •Основные понятия
- •Компьютерные представления графов
- •Маршруты и связность
- •Кратчайшие пути в графах
- •Деревья
- •Кодирование деревьев
- •Центр дерева
- •Минимальное остовное дерево (остов)
- •Эйлеровы графы
- •Гамильтоновы графы
- •Графовые векторы
- •Паросочетания и реберные покрытия
- •Паросочетания в двудольных графах
- •Правильная нумерация вершин графа
- •Сетевые графики
- •Потоки в сетях
- •Вопросы для самопроверки
- •Упражнения
- •Рекомендуемая литература
- •Предметный указатель
Некоторые свойства бесконечных множеств
Уже отмечалось, что конечное множество не равномощно своей части, в то же время, бесконечное множество может быть равномощным своей части. Оказывается, это характеристическое свойство бесконечных множеств.
Теорема 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.
И
здесь противоречие!
Мощность
множества
иногда называют мощностью
гиперконтинуума.
