Упорядоченное множество.

Пусть R — произвольное отношение порядка на непустом множестве .

ОПРЕДЕЛЕНИЕ. Упорядоченным множеством называется пара где — непустое множество и R — отношение порядка на . Если порядок R на линейный, то пара называется линейно упорядоченным множеством. Если порядок R на частичный, то пара называется частично упорядоченным множеством.

ОПРЕДЕЛЕНИЕ. Пусть — упорядоченное множество. Элемент а из называется наименьшим (наибольшим) в А, если а для любого элемента из , отличного от а.

Любое упорядоченное множество имеет не более одного наименьшего и не более одного наибольшего элемента.

ОПРЕДЕЛЕНИЕ. Пусть — упорядоченное множество. Элемент а из А называется минимальным (максимальным) в А, если выполняется условие; для любого из А, если , то (если , то ).

Упорядоченное множество может иметь несколько минимальных и максимальных элементов.

Пример. Пусть R — отношение делимости в множестве — множество натуральных чисел). В упорядоченном множестве любое простое число является минимальным элементом.

В линейно упорядоченном множестве понятия наименьшего (наибольшего) и минимального (максимального) элементов совпадают.

ОПРЕДЕЛЕНИЕ. Линейно упорядоченное множество называется вполне упорядоченным множеством, если каждое непустое подмножество множества А имеет наименьший элемент.

Примеры. 1. Если есть обычное отношение «меньше» на множестве N натуральных чисел, то является вполне упорядоченным множеством.

2. Пусть есть обычное отношение «меньше» на множестве R всех действительных чисел. Тогда линейно упорядоченное множество не является вполне упорядоченным множеством.