- •1.1.1. Понятие множества
- •1.1.2. Способы задания множеств
- •1.1.3. Основные определения
- •1.1.4. Диаграммы Эйлера – Венна
- •1.1.5. Операции над множествами
- •1.1.6. Системы множеств
- •1.1.7. Законы алгебры множеств
- •1.1.8. Решение задач 1-3 контрольной работы № 1
- •1.1.9. Контрольные вопросы и упражнения
- •1.2.1. Декартово произведение множеств. Соответствие множеств
- •1.2.2. Определение бинарного отношения
- •1.2.3. Способы задания бинарного отношения
- •1.2.4. Свойства бинарных отношений
- •1.2.5. Отношения эквивалентности
- •1.2.6. Отношения порядка
- •1.2.7. Частично упорядоченные множества
- •1.2.8. Диаграммы Хассе
- •1.2.9. Изоморфизм частично упорядоченных множеств
- •1.2.10. Решение задач 5,6 контрольной работы № 1
- •1.2.11. Контрольные вопросы и упражнения
- •1.3 Реляционная алгебра
- •1.3.1. Применение отношений для обработки данных
- •1.3.2. Теоретико-множественные операции реляционной алгебры
- •1.3.3. Специальные операции реляционной алгебры
- •1.3.4. Решение задачи 7 контрольной работы № 1
- •1.4. Конечные и бесконечные множества
- •1.4.1. Равномощные множества
- •1.4.2. Классы равномощных множеств
- •1.4.3. Сравнение множеств по мощности
- •1.4.4. Свойства конечных множеств
- •A b c
- •1.4.5. Определение счетного множества
- •1.4.6. Свойства счетных множеств
- •1.4.7. Несчетные множества
- •1.4.8. Булеан бесконечного множества. Выводы
- •1.4.9. Решение задач 8,9 контрольной работы 1
- •1.4.10. Контрольные вопросы и упражнения
1.4.2. Классы равномощных множеств
Введенное в 1.4.1 отношение равномощности является отношением эквивалентности “ “. В самом деле, оно рефлексивно: для каждого множестваХсправедливо (ХравномощноХ), так как существует тождественное отображение множестваХна множествоХ. Это отношение симметрично: если существует биекцияXнаY, то обратное отображение также является биекцией (если, то). Отношение транзитивно: если существует биекцияи существует биекция, то соответствие отображаетXнаZбиективно (если и, то).
По свойству отношения эквивалентности (см. 1.2.5) получаем разбиение всех множеств на непересекающиеся классы равномощных множеств. Каждому классу присвоим название -кардинальное число. Таким образом, кардинальное число – это то общее, что есть у всех равномощных множеств. Обозначим кардинальное число множества илиХ. Пустое множество имеет кардинальное число =0; для всех конечных множеств кардинальное число совпадает с количеством элементов множества; а для обозначения кардинального числа бесконечных множеств используется буква(алеф). Понятие кардинального числа (мощности множества) обобщает понятие “ количество элементов ” на бесконечные множества.
1.4.3. Сравнение множеств по мощности
Расположим классы эквивалентности равномощных множеств в порядке возрастания кардинальных чисел: .
Для конечных множеств это не вызывает затруднений: означает для конечных множеств, что количество элементов множестваXменьше количества элементов множестваY,и классXрасположен левее классаYв последовательности классов равномощных множеств. А что означает неравенствоX<Yдля бесконечных множеств? Договоримся о следующих обозначениях:
1) если множества XиYпопадают в один класс эквивалентности, пишемX=Y;
2) если класс эквивалентности множества Xнаходится левее класса эквивалентностиYв ряду кардинальных чисел, используем обозначениеX<Y;
3) если класс эквивалентности множества Xнаходится правее класса эквивалентности множестваY, тоX>Y;
4) в теории множеств строго доказано, что случай, когда множества Xи Yнесравнимы по мощности, невозможен – это означает, что классы равномощных множеств можно вытянуть в цепочку без разветвлений по возрастанию мощности.
Следующая теорема, приведенная без доказательства, позволяет устанавливать равномощность бесконечных множеств.
Теорема Кантора-Бернштейна.ПустьXиYдва бесконечных множества. Если во множествеXесть подмножество, равномощное множествуY, а во множествеYесть подмножество, равномощноеX, то множестваX и Yравномощны.
Пример. Пусть. Покажем, чтоX=Y. Непосредственно биекциюXнаYпостроить трудно, т.к.X- отрезок с включенными концами, аY– открытый интервал.
Применим теорему Кантора-Бернштейна. Возьмем в качестве подмножествамножестваXоткрытый интервал :. БиекциянаYлегко устанавливается: например, по закону(рис. 1.22) , осуществляется взаимно однозначное отображение интервала (0;1) на интервал.
В качестве подмножества возьмем любой замкнутый интервал изY, например,. В 1.4.1 уже показано, что[1;3]=[0;1](существует биекция). Таким образом, условия теоремы Кантора-Бернштейна выполняются, следовательно, множестваи равномощны (X=Y).