ОПРЕДЕЛЕНИЕ. Элемент a называется максимальным (минимальным) в упорядоченном множестве (A, r), если

Элемент a называется максимальным (минимальным) в упорядоченном множестве (A, r), если

" bÎ A(b¹a Þ (b, a)Ïr) (" bÎA(b¹a Þ (a, b)Ïr)).

Упорядоченное множество может иметь несколько или не иметь вообще максимальных и минимальных элементов. Например, для упорядоченного множества, представленного диаграммой на рис. 3.2., максимальными являются элементы a и b, а минимальными - e, f и g.

Если A - конечное множество, то любое упорядоченное множество (A, r) всегда имеет максимальные и минимальные элементы. Для бесконечных множеств такое свойство может оказаться неверным.

Частным случаем частичного порядка является линейный порядок. Порядок r называется линейным, если:

" a,bÎ A((bra) Ú (arb)).

То есть, в линейном порядке любые два элемента множества, на котором определено отношение порядка, являются сравнимыми.

Следующая теорема характеризует общий вид диаграмм для отношений линейного порядка.

Теорема 3.3.Если r является отношением линейного порядка на конечном множестве A, то диаграмма для этого отношения имеет вид последовательности, составленной из всех элементов A, в которой всякий предыдущий элемент связан ориентированной дугой со следующим элементом.

Доказательство. Пусть rявляется отношением линейного порядка на множестве A = {a₁, . . . , a_n}. Проведем доказательство индукцией по мощности множества A.

1. Базис индукции. Пусть A = {a₁}. Тогда диаграмма отношения rна A имеет вид одноэлементной последовательности a₁.

2. Индуктивное предположение. Пусть для каждого множества A содержащего не более чем n элементов выполнено утверждение теоремы.

3. Индуктивный переход. Пусть A = {a₁, . . . , a_n, a_n+1 }.

3.1. Покажем, что r имеет минимальный элемент. Предположим противное. Тогда для отношения rсправедливо условие (1):

"a Î A $bÎ A (b r a) Ú $ a Î A $bÎ A ((a, b)Ï r &(b, a)Ï r). (1)

В этом условии левая часть дизъюнкции неверна, поскольку означает существование бесконечной последовательности элементов A, в которой для любых двух соседних элементов a и b выполняется условие b r a, что противоречит условию конечности множества A.

Неверной является и правая часть условия (1). Поскольку в этом случае для отношения линейного порядка найдутся два несравнимых элемента.

Следовательно, rимеет минимальный элемент.

3.2. Покажем что для отношения r выполнено утверждение теоремы. Пусть a Î A является минимальным элементом в отношении r. Тогда часть этого отношения для множестве A \ { a }является линейным порядком. Если бы это было не так, то несравнимые элементы для части rна множестве A \ { a }оказываются несравнимыми и для отношения rна A.

По индуктивному предположению для A \ { a }выполнено утверждаемое в теореме свойство. Пусть b минимальный элемент для части rна A \ { a }. Тогда диаграмма для части rна множестве Aполучается из диаграммы для части rна множестве A \ { a },добавлением ориентированной дуги, соединяющей вершину a с вершиной b.