- •1. Элементы теории множеств
- •1.1 Понятие множества. Основные определения
- •Способы задания множества
- •Равенство множеств
- •Подмножество
- •Операции над множествами
- •Предварительные замечания
- •Объединение множеств
- •1.5.3 Пересечение множеств
- •1.5.4 Разность множеств
- •1.5.5 Симметрическая разность
- •1.5.6 Универсальное множество
- •1.5.7 Дополнение множества
- •Принцип двойственности в алгебре множеств
- •Тождества алгебры множеств
- •Разбиение множества
- •Упорядочение элементов и прямое произведение множеств
- •Упорядоченное множество
- •Прямое произведение множеств
- •1.9.3 Проекция множества
- •1.10 Соответствия
- •1.10.1 Обратное соответствие
- •1.10.2 Композиция соответствий
- •1.10.3 Отображения и функции
- •1.10.4 Основные свойства отображений
- •1.11 Функция
- •1.11.1 Способы задания функции
- •1.11.2 Сужение функции
- •1.11.3 Обратная функция
- •1.11.4 Функция времени
- •1.11.5 Понятие функционала
- •1.11.6 Понятие оператора
- •1.12 Отношения
- •1.12.1 Задание бинарных отношений
- •Свойства отношений
- •1.12.3 Отношение эквивалентности
- •1.12.4 Отношение порядка
- •1.13 Конечные и бесконечные множества
- •1.13.1 Счётные и несчётные множества
- •1.13.2 Свойства счетных множеств
- •1. Всякое подмножество счетного множества конечно или счетно.
- •2. Объединение любого конечного или счетного множества счетных множеств есть снова счетное множество.
- •3. Всякое бесконечное множество содержит счетное подмножество.
- •1.13.3 Эквивалентность множеств
- •1.13.4 Теорема г. Кантора
- •1.13.5 Теорема Кантора – Бернштейна
- •1.13.6 Верхняя и нижняя границы множества
- •1.13.7 Теорема о верхних и нижних границах подмножества
- •1.13.8 Понятие мощности множества
- •2. Основные положения теории графов
- •2.1 Определение графа
- •2.2 Матричные представления графа
- •2.3. Достижимость
- •2.4. Неориентированные графы
- •2.5. Изоморфизм графов
- •2.6. Отношение порядка и отношение эквивалентности на графе
- •2.7. Характеристики графов
- •2.8 Операции над графами
- •2.9. Определение путей экстремальной длины
- •2.9.1. Задача о кратчайшем пути между двумя вершинами (ориентированного графа
- •2.9.2 Задача о нахождении пути максимальной длины между двумя фиксированными вершинами ориентированного графа
- •Номера работ обозначены числами в кружке.
- •Литература
1.13.5 Теорема Кантора – Бернштейна
Пусть А и В – два произвольных множества. Если существует взаимно однозначное отображение f множества А на подмножество В1 множества В и взаимно однозначное отображение g множества В на подмножество А1 множества А, то А и В эквивалентны.
1.13.6 Верхняя и нижняя границы множества
Рассматривая подмножество А упорядоченного основного (в частности, универсального) множества I и пусть R – некоторое отношение порядка на I. Если существует такой элемент МI, что для всех аА справедливо утверждение аRМ, то М называется мажорантой А.
Аналогично, если существует такой элемент mI, что для всех аА удовлетворяет отношение mRa, то m называется минорантой множества А.
Если мажоранта М множества А принадлежит множеству А, то М называется максимумом множества А (наибольшим элементом множества А). Обозначается следующим образом: maxA=M; . Максимум М единственен. Действительно, предположим противное, что множество А имеет два максимума (М1 и М2), тогда условия (а) (aRM1) и (а) (aRM2) влекут M1RM2 и M2RM1, следовательно, в силу антисимметричности отношений порядка M1=M2.
Если миноранта mA, то m называется минимумом множества А (наименьшим элементом). Обозначается: minA=m; . Минимум m единственен.
Пусть Z – множество вещественных чисел . Верхней границей Z является число H такое , что для любого z Z имеет место z H ( z|z Z z H ; H – sup Z ).
Точной верхней границей или супремумом множества Z, обозначаемой sup Z, называют верхнюю границу, которая не превосходит любую другую верхнюю границу. Множество может иметь только одну точную верхнюю границу .
Нижней границей множества Z является число L такое, что для любого z Z имеет место z L ( z|z Z z L inf Z = L) .
Точной нижней границей называют нижнюю границу , не меньшую любой другой нижней границы. Нижняя граница обозначается inf Z и называется инфинумом .
Рассмотрим отрезок [a, b], a < b на числовой оси. Основное множество – множество действительных чисел упорядочено отношением “”. Любое действительное число, большее или равно и b, является мажорантой. Множество этих мажорант имеет минимум, равный b, следовательно sup[a, b]=b. Аналогично inf[a, b]=a.
С другой стороны, мажоранта b принадлежит отрезку [a, b], следовательно, число b является максимумом: max[a, b]=b; min[a, b]=a.
Если бы рассматривали интервал (а, b), то а и b являются соответственно минорантой и мажорантой, но не принадлежат интервалу (a, b), поэтому не являются минимумом и максимумом (a, b). Числа а и b и в этом случае являются нижней и верхней границами множества (a, b) соответственно.
Таким образом, если множество мажорант (минорант) в свою очередь имеют минимум (максимум), то этот элемент единственен и соответствует верхней (нижней) границе.1
1.13.7 Теорема о верхних и нижних границах подмножества
Если B A то, inf B inf A; sup B sup A.
Доказательство.
Пусть - элемент множества B, имеющей наименьшее значение, т. е. B и = inf B. Но B A, тогда A.
Пусть - элемент множества А, имеющий наименьшее значение , т.е. А и = inf A. При этом, если , то = inf A; если , то = inf A. Таким образом , inf A или inf B inf A.
Аналогично доказывается вторая часть теоремы.