Задачи повышенной трудности

Т – отношение частичного порядка (отношение порядка) на множестве М, если оно транзитивно и антисимметрично.

Отношение порядка Т – отношение нестрогого порядка на множестве М, если оно рефлексивно.

Отношение порядка Т – отношение строгого порядка на множестве М, если оно антирефлексивно.

Известно, что Т – отношение строгого порядка тогда и только тогда, когда оно транзитивно и антирефлексивно.

Отношение порядка Т на множестве М называется отношением линейного порядка (линейным порядком), если оно связно на М.

Если на множестве задано отношение порядка, то множество называется упорядоченным.

Если порядок линейный, то множество называется линейно упорядоченным. Если порядок не является линейным, то множество называется частично упорядоченным.

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

Если (a,b)ÎT, то элементы a и b изображаются точками (вершины графа) и от точки, изображающей а, к точке, изображающей b, проводится стрелка (ребро графа).

Так как отношение порядка антисимметрично, то изображение можно упростить следующим соглашением: если (a,b)ÎT, то точку, изображающую а, расположить ниже точки, изображающей b, и соединить эти точки не стрелкой, а просто отрезком (прямолинейным или криволинейным).

Элемент а называется минимальным элементом упорядоченного множества М, если ("х) . Элемент а называется максимальным элементом упорядоченного множества М, если ("х) .

Элемент а называется наименьшим, если он является минимальным, и для любого х Î М выполняется (а,х)ÎТ. Элемент а называется наибольшим, если он является максимальным, и для любого х Î М выполняется (х, а)ÎТ.

Известно, что если в М есть наименьший элемент, то он единственный и никаких других минимальных элементов нет. Соответственное утверждение справедливо и для наибольшего элемента.

Наконец, линейно упорядоченное множество называется вполне упорядоченным, если каждое непустое подмножество этого множества имеет наименьший элемент.

В заключение заметим, что отношения порядка принято обозначать не буквами, а символами: <, £, >, ³, и т.п. и вместо записи (а,b)Î принята запись а b.