Утверждение.

Во всяком непустом конечном, частично упорядоченном множестве М существует хотя бы один минимальный (максимальный) элемент.

Доказательство.

Докажем существование минимального элемента.

Допустим, что в М нет минимальных элементов. Пусть |M| = n, выберем произвольный элемент аÎМ, обозначим его через х₁. Так как х₁ – не минимальный элемент, то существует bÎМ, (обозначим b через x₂), такой, что x₂< х₁. Далее, существует сÎМ, (обозначим с через х₃), такой, что x₃ < x₂ < x₁. Продолжим перебор элементов множества M. Перебрав все, получим цепочку: x_n < x_n-1 < ... < x₂ < x₁. Так как x_n – не минимальный элемент, то ( k): x_k < x_n, k < n. Таким образом, x_k < x_n < x_n-1 < ... < x_k < ... < < x₁. Но отношение порядка транзитивно, получаем, что x_k < x_k, - противоречие, строгий порядок антирефлексивен.

Определение. Пусть M – частично упорядоченное множество. Элемент хÎМ называется наименьшим элементом множества М, если ("аÎМ, a¹x): а > х. Элемент yÎM – наибольшим элементом множества М, если ("аÎМ, a¹y): а< y. По определению наименьший (наибольший) элемент сравним со всеми другими элементами множества М

Утверждение.

Если во множестве М существует наименьший (наибольший) элемент, то он единственен.

Доказательство.

Пусть х₁ ≠ х₂ – два наименьших элемента множества . По определению наименьшего элемента х₁< х₂, (х₁ – наименьший элемент), а также х₂ < х₁– (х₂ – наименьший элемент) Þ х₁ = х₂ в силу антисимметричности любого отношения порядка.

Примеры наибольших и наименьших элементов.

1. Æи М – являются наименьшим и наибольшим элементами булеана 2^М, упорядоченного по включению.

2. В множестве N наименьший элемент - 1, наибольшего элемента нет (порядок – обычное сравнение чисел).

3. Множество R – не имеет ни наибольшего элемента, ни наименьшего элемента (порядок – обычное сравнение чисел).

4. Во множестве В = {{1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}, частично упорядоченном по включению, нет наименьшего элемента; множество

{1, 2, 3} - наибольший элемент множества В.