§9. Экстремальные элементы в частично упорядоченных множествах и подмножествах Определение 1
а) Пусть
–
частично упорядоченное множество.
Элемент
называется максимальным элементом
множества
,
если не существует
,
такого, что
.
Иногда это определение можно встретить
в такой формулировке: для любого
.
б) Элемент
называется минимальным элементом
множества
,
если не существует элемента
,
такого, что
или для любого
.
Максимальные и минимальные элементы в частично упорядоченных множествах могут существовать, а могут и не существовать, их может быть несколько, как показывают нижеприведенные примеры.
Пример 1
–
множество вещественных чисел с
естественным порядком. В этом множестве
нет ни максимального, ни минимального
элементов.
Пример 2
В множестве
есть максимальный элемент
и минимальный элемент
.
В множестве
есть максимальный, но нет минимального
элемента, а в множестве
есть минимальный, но нет максимального
элемента.
Пример 3
Рассмотрим частично упорядоченное
множество
,
где
–
отношение делимости. Для наглядности
построим диаграмму этого множества:
Здесь 2, 3, 7 являются минимальными элементами, а 7, 12, 16, 18 – максимальными.
Задача 1
Придумать множество, которое имеет бесконечно много максимальных элементов.
Задача 2
Придумать множество, которое имеет бесконечно много максимальных и бесконечно много минимальных элементов.
Определение 2
Пусть – частично упорядоченное множество.
а) Элемент
называется наибольшим элементом
А, если для
любого
.
б) Элемент
называется наименьшим элементом
А, если для
любого
.
Следующая теорема показывает, что понятия максимального и наибольшего элементов существенно отличаются друг от друга (минимальный и наименьший элементы – аналогично).
Теорема 3
Если в частично упорядоченном множестве есть наибольший элемент, то он единственный.
Доказательство
Пусть а и
b –
наибольшие элементы в
,
тогда для любого
,
в частности,
.
Аналогично
.
Следовательно,
.
Замечание. Аналогичное верно для наименьших элементов.
Теорема 4
Если – линейно упорядоченное множество и a – максимальный элемент, то а является наибольшим, а значит, единственным максимальным элементом.
Доказательство
Так как а –
максимальный элемент, то не существует
,
такого, что
.
С другой стороны, так как
линейно упорядочено, то выполняется
альтернатива
,
поэтому
,
где b –
произвольный элемент А.
Теорема доказана.
Определение 5
Пусть
–
частично упорядоченное множество и
.
а) Элемент
называется верхней границей множества
В, если для
любого
.
Обозначение верхней границы:
.
б) Наименьшая из всех верхних границ
множества В,
если она существует, называется точной
верхней границей и обозначается:
.
в) Элемент
называется нижней границей множества
В, если для
любого
.
Обозначение нижней границы:
.
г) Наибольшая из всех нижних границ
множества В,
если она существует, называется точной
нижней границей и обозначается:
.
Пример
Рассмотрим
и
.
Числа 2, 1,
,
1000 являются верхними границами
множества
,
.
Числа
являются нижними границами множества
,
.
§10. Отображения
Определение 1
Отношение
называется функциональным, если
выполняется условие однозначности: для
любых
и
,
если
,
,
то
.
Функциональные отношения называются
отображениями, функциями, соответствиями.
Для отображения
используют запись
.
О некоторых других обозначениях
отображения будет сказано ниже.
Задачи
1. Найти все функциональные отношения порядка.
2. Найти все функциональные отношения строгого порядка.
3. Найти все функциональные отношения строгого линейного порядка.
4. Найти все функциональные отношения эквивалентности.
Отметим, что, несмотря на кажущуюся
сложность, все эти задачи решаются
весьма просто. Например, в первой и
четвертой задачах ответом является
отношение равенства на A:
,
которое определяется условием:
тогда и только тогда, когда
.
Определение 2
Пусть
,
тогда множество А
называется областью отправления
F, а B –
областью прибытия отображения F.
Если пара
,
то мы пишем
.
В этом равенстве элемент
называется образом элемента
,
а элемент
называется прообразом элемента
.
Определение 3
Пусть .
а) Множество
:
существует
,
такой, что
называется областью определения F
и обозначается
;
б) Множество
:
существует
,
такой, что
называется областью значений F
и обозначается
.
Определение 4
Отображения
и
называются равными, если:
1)
;
2) для любого
.
Определение 5
Пусть .
а) Если
,
то множество
называется образом множества X
при отображении F;
б) если
,
то
называется прообразом множества Y
при отображении F.
Теорема 6
Пусть
и
,
тогда
.
Доказательство
Пусть
.
Это значит, что существует
,
такой, что
.
Если
,
то
,
следовательно,
.
Аналогично рассматривается случай
.
Итак мы доказали, что
.
Теперь пусть
.
Возьмем для определенности
,
значит, существует
,
такой, что
.
Из того, что
,
следует
,
значит,
.
Аналогично рассматривается случай
.
Итак,
.
Поэтому
.
Теорема 7
Пусть
и
,
тогда
(Словами: прообраз объединения равен
объединению прообразов).
Доказательство
Возьмем
,
это значит, что
,
то есть
или
.
Если
,
то по определению прообраза
,
значит,
.
Аналогично, если
,
то
.
Мы доказали, что
.
Докажем включение в другую сторону.
Возьмем
,
значит,
или
.
Если
,
то
,
следовательно,
,
поэтому
.
Аналогично рассматривается случай
.
Значит,
.
Два доказанных включения дают требуемое равенство
.
Теорема доказана.
Теорема 8
Пусть
и
,
тогда
.
Доказательство
Возьмем
.
По определению образа множества это
значит, что существует
,
такой, что
.
Из того, что
,
следует, что
,
значит,
и
,
то есть
.
Мы доказали, что
.
Построим пример, который показывает,
что обратное включение, а значит, и
равенство, здесь не выполняется. Возьмем
.
В качестве множества
возьмем
,
.
Очевидно, что
,
,
значит и
.
Далее,
,
поэтому
.
Ясно, что в этом случае
.
Теорема 9
Пусть
и
,
тогда
.
Доказательство
Пусть
,
то есть
,
значит,
,
поэтому
и, наконец,
.
Итак,
.
Теперь возьмем
,
отсюда
,
значит,
и
,
то есть
,
следовательно,
.
Поэтому
.
Полученные включения и доказывают
равенство:
.
Определение 10
Пусть
и
.
Суперпозицией отображений G
и F называется
отображение
,
которое определяется следующими
условиями:
1)
;
2)
;
3) для любого
.
Суперпозиция отображений называется
еще композицией, или функциональным
произведением отображений G
и F,
или сложной функцией
.
Теорема 11
Если
,
,
,
то
(ассоциативность суперпозиции).
Доказательство
Легко заметить, что композиция отображений есть частный случай произведения бинарных отношений. Поскольку для произведения бинарных отношений ассоциативный закон выполняется, то и для композиции отображений он тоже выполняется.
Определение 12
Пусть .
1) Отображение F
называется взаимооднозначным (или
одно-однозначным), если для любых
из А
.
Другими словами, разные элементы из
области определения имеют разные образы.
Обозначение
.
Такие отображения называются еще вложениями.
2) Отображение называется отображением "на", если для любого существует , такой, что , то есть для любого имеется в А его прообраз.
Обозначение
;
3) Отображение
,
которое является одновременно и
взаимооднозначным и "на",
называется биекцией и обозначается
.