Определение

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

 b  A(ba  (b, a)) ( bA(ba  (a, b))).

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

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

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

 a,b A((ba)  (ab)).

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

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

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

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

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

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

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

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

a  A b A (b  a)   a  A  b A ((a, b)   (b, a) ). (1)

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

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

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

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

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

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

Доказанная теорема справедлива для бесконечных множеств, всякое подмножество которого имеет минимальный элемент. При этом отношению  соответствует бесконечная последовательность, имеющая начальный элемент.

Упражнение.

1. Приведите не менее 5 видов диаграмм для отношения линейного порядка на произвольном счетно-бесконечном множестве.

2. Приведите пример упорядоченного множества (A, ), для которого множества максимальных и минимальных элементов являются бесконечными.

3. Докажите или опровергните следующее утверждение: всякое отношение линейного порядка представляется диаграммой в виде бесконечной последовательности без первого и последнего элементов либо только с первым элементом либо только с последним элементом.

4. Пусть ₁ и ₂ являются отношениями порядка. Являются ли ₁ ^–1 и ₁ ₂ отношениями порядка?

68