Задачи повышенной трудности
1. Пусть S, T, U – любые отношения. Показать:
а)
б)
2.
Показать, что отношение Т
с областью определения М
тогда и только тогда является отношением
эквивалентности на М,
когда
и
.
Тема 8. Отношение порядка
Т – отношение частичного порядка (отношение порядка) на множестве М, если оно транзитивно и антисимметрично.
Отношение порядка Т – отношение нестрогого порядка на множестве М, если оно рефлексивно.
Отношение порядка Т – отношение строгого порядка на множестве М, если оно антирефлексивно.
Известно, что Т – отношение строгого порядка тогда и только тогда, когда оно транзитивно и антирефлексивно.
Отношение порядка Т на множестве М называется отношением линейного порядка (линейным порядком), если оно связно на М.
Если на множестве задано отношение порядка, то множество называется упорядоченным.
Если порядок линейный, то множество называется линейно упорядоченным. Если порядок не является линейным, то множество называется частично упорядоченным.
Особую наглядность приобретают эти факты, если ввести в рассмотрение понятие графа отношения Т.
Е
сли
(a,b)T,
то элементы a
и b
изображаются точками (вершины графа) и
от точки, изображающей а,
к точке, изображающей b,
проводится стрелка (ребро графа).
Т
ак
как отношение порядка антисимметрично,
то изображение можно упростить следующим
соглашением: если (a,b)T,
то точку, изображающую а,
расположить ниже точки, изображающей
b,
и соединить эти точки не стрелкой, а
просто отрезком (прямолинейным или
криволинейным).
Элемент
а
называется минимальным элементом
упорядоченного множества М,
если (х)
.
Элемент а
называется максимальным элементом
упорядоченного множества М,
если (х)
.
Элемент а называется наименьшим, если он является минимальным, и для любого х М выполняется (а,х)Т. Элемент а называется наибольшим, если он является максимальным, и для любого х М выполняется (х, а)Т.
Известно, что если в М есть наименьший элемент, то он единственный и никаких других минимальных элементов нет. Соответственное утверждение справедливо и для наибольшего элемента.
Наконец, линейно упорядоченное множество называется вполне упорядоченным, если каждое непустое подмножество этого множества имеет наименьший элемент.
В
заключение заметим, что отношения
порядка принято обозначать не буквами,
а символами: <, ,
>, ,
и т.п. и вместо записи (а,b)
принята запись а
b.
Практические задания
1. Покажите, что отношение Т = {(x, y) | x N, y N , х < y} является отношением линейного порядка на множестве N.
2. Докажите, что тождественное отображение iA множества А есть отношение порядка на множестве А.
3. Покажите, что конечное множество, состоящее из n элементов, можно строго линейно упорядочить n! способами.
4. Докажите, что в конечном множестве всегда имеются минимальные и максимальные элементы.
5. Докажите, что любое вполне упорядоченное множество является линейно упорядоченным.
6. Придумайте примеры частично упорядоченных множеств с a минимальными, b максимальными, из которых с являются одновременно и минимальными и максимальными элементами, е наибольшими, d наименьшими элементами:
-
а) a = b = c = d = e = 0;
б) a = 2, b = 3, c = 1, d = e = 0;
в) a = 2, b = 2, c = 0, d = e = 1;
г) a = 0, b = 3, c = d = e = 0;
д) a = b = c = d = e = 1;
е) a = , b = c = 1, d = e = 0;
ж) a = 1, b = , c = d = 0, e = 1.
7. Постройте на множестве N N линейный порядок.
8. Покажите, что отношение включения не является линейным порядком на совокупности Р(А) всех подмножеств множества А, если А содержит не менее двух элементов.
9.
Докажите, что бинарное отношение Т
на множестве М
является отношением нестрогого порядка
тогда и только тогда, когда
iM,
где iM
= {(x,
х)
| x
М}.
10. Пусть < - бинарное отношение антирефлексивное и транзитивное на множестве М. Докажите, что отношение такое, что х у (x < y) (x = y), есть отношение нестрогого порядка на М.
11. Докажите, что если Т – частичный (линейный, полный) порядок на множестве М и А М, то Т (А А) – частичный (линейный, полный) порядок на множестве А.
1
2.
Опишите отношения, заданные графами:
а) б) в) г) д)
Найдите минимальные, максимальные, наименьшие, наибольшие элементы.