Экстремальные элементы в частично упорядоченном множестве
Решение.
= 
с элементом a не сравнимы элементы b и d. С элементом d не сравнимы элементы a, b, c, e.
Рис. 2
Пусть М – частично упорядоченное множество. Элемент х
М называется минимальным элементом этого множества, если во множестве М не существует элемента a
x. Элемент yМ называется максимальным элементомэтого множества, если в нем не существует элемента a>y. Минимальный и максимальный элементы в упорядоченных множествах могут существовать, а могут и не существовать (в случае бесконечных множеств), их может быть несколько.
Пример 1.
M = {1, 2 ...
} = N; порядок – обычное сравнение чисел, минимальный элемент - это 1, максимальные элементы отсутствуют).
Пример 2.
M1 = [0; 1], M2 = (0; 1], M3 = [0; 1], M4 = (0; 1).
В M1 минимальный элемент - это 0, максимальный элемент это - 1.
В M2 минимального элемента нет, максимальный элемент - это 1.
В M3 минимальный элемент - это 0, максимального элемента нет.
В M4 минимальный и максимальный элементы отсутствуют (порядок – обычное сравнение чисел).
Пример 3.
М = {{1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
Отношение порядка – это отношение включения. В этом множестве три минимальных элемента, не сравнимых между собой, – множества {1;2}, {1; 3}, {2; 3} . Максимальный элемент один – множество {1, 2, 3}.
Пример 4.
М = {2 ,3, 4 ... }, a < b Û a делит b и a ≠ b.
Максимального элемента нет, а минимальные элементы - все простые числа.
Пример 6.
Покажем, как на диаграмме выглядят минимальный и максимальный элементы в случае множества: М = {2, 3, 4, 6, 7, 12, 16, 18}, a < b Û a делит b и a ≠ b. (рис.3)
Рис. 3
Минимальные элементы – 2, 3, 7. В минимальный элемент не входит ни одна линия со стрелкой.
Максимальные элементы – 7, 12, 16 18. Из максимального элемента не выходит ни одна линия со стрелкой. Один и тот же элемент может быть одновременно и максимальным, и минимальным. В этом случае он не сравним ни с каким другим элементом данного множества.
Утверждение.
Во всяком непустом конечном, частично упорядоченном множестве М существует хотя бы один минимальный (максимальный) элемент.
Доказательство.
Докажем существование минимального элемента.
Допустим, что в М нет минимальных элементов. Пусть |M| = n, выберем произвольный элемент аÎМ, обозначим его через х1. Так как х1 – не минимальный элемент, то существует bÎМ, (обозначим b через x2), такой, что x2 < х1. Далее, существует сÎМ, (обозначим с через х3), такой, что x3 < x2 < x1. Продолжим перебор элементов множества M. Перебрав все, получим цепочку: xn < xn-1 < ... < x2 < x1. Так как xn – не минимальный элемент, то (
k): xk < xn, k < n. Таким образом, xk < xn < xn-1 < ... < xk < ... < < x1. Но отношение порядка транзитивно, получаем, что xk < xk, - противоречие, строгий порядок антирефлексивен.
Определение. Пусть M – частично упорядоченное множество. Элемент хÎМ называется наименьшим элементом множества М, если ("аÎМ, a¹x): а > х. Элемент yÎM – наибольшим элементом множества М, если ("аÎМ, a¹y): а< y. По определению наименьший (наибольший) элемент сравним со всеми другими элементами множества М
Утверждение.
Если во множестве М существует наименьший (наибольший) элемент, то он единственен.
Доказательство.
Пусть х1 ≠ х2 – два наименьших элемента множества 
. По определению наименьшего элемента х1 < х2, (х1 – наименьший элемент), а также х2 < х1 – (х2 – наименьший элемент) Þ х1 = х2 в силу антисимметричности любого отношения порядка.
Примеры наибольших и наименьших элементов.
1. Æ и М – являются наименьшим и наибольшим элементами булеана 2М, упорядоченного по включению.
2. В множестве N наименьший элемент - 1, наибольшего элемента нет (порядок – обычное сравнение чисел).
3. Множество R – не имеет ни наибольшего элемента, ни наименьшего элемента (порядок – обычное сравнение чисел).
4. Во множестве В = {{1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}, частично упорядоченном по включению, нет наименьшего элемента; множество
{1, 2, 3} - наибольший элемент множества В.