Экстремальные элементы в частично упорядоченном множестве

Пусть М – частично упорядоченное множество. Элемент х М называется минимальным элементом этого множества, если во множестве М не существует элемента a x. Элемент y М называется максимальным элементомэтого множества, если в нем не существует элемента a>y. Минимальный и максимальный элементы в упорядоченных множествах могут существовать, а могут и не существовать (в случае бесконечных множеств), их может быть несколько.

Пример 1.

M = {1, 2 ... } = N; порядок – обычное сравнение чисел, минимальный элемент - это 1, максимальные элементы отсутствуют).

Пример 2.

M₁ = [0; 1], M₂ = (0; 1], M₃ = [0; 1], M₄ = (0; 1).

В M₁минимальный элемент - это0, максимальный элемент это- 1.

В M₂минимального элемента нет, максимальный элемент - это1.

В M₃ минимальный элемент - это0, максимального элемента нет.

В M₄ минимальный и максимальный элементы отсутствуют (порядок – обычное сравнение чисел).

Пример 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.

Максимального элемента нет, а минимальные элементы - все простые числа.

Пример 5.

М = N, a < b Û a - четно, b – нечетно, например: 2 < 1, 2 < 7, 6 < 3,

6 < 11. Определен строгий частичный порядок, в котором все четные числа – минимальные элементы, не сравнимые между собой, все нечетные числа – максимальные элементы, не сравнимые между собой.

Пример 6.

Покажем, как на диаграмме выглядят минимальный и максимальный элементы в случае множества: М = {2, 3, 4, 6, 7, 12, 16, 18}, a < b Û a делит b и a ≠ b. (рис.3)

Рис. 3

Минимальные элементы – 2, 3, 7. В минимальный элемент не входит ни одна линия со стрелкой.

Максимальные элементы – 7, 12, 16 18. Из максимального элемента не выходит ни одна линия со стрелкой. Один и тот же элемент может быть одновременно и максимальным, и минимальным. В этом случае он не сравним ни с каким другим элементом данного множества.