ОПРЕДЕЛЕНИЕ. Элемент 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 ((b r a) Ú (a r b)).

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

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

Теорема 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.