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

Разбиение множества на попарно непересекающиеся классы.

Семейство множеств M_i, iÎI, называется разбиением M на классы, если:

1) для всех iÎI множество M_i непустое подмножество M: M_i¹Æ, M_iÍM;

2) множества M_i попарно не пересекаются: M_i ÇM_j=Æ, где i¹j;

3) объединение всех M_i, iÎI, совпадает с множеством M.

Теорема. Пусть дано разбиение M на классы. Тогда отношение P на M, такое, что xPyÛ"x и y принадлежат одному классу" есть эквивалентность.

Пример. Разбиение множества всех учеников школы на классы определяет эквивалентность "ученики x и y учатся в одном классе".

Асимметричное и транзитивное отношение называется порядком. Если порядок является также рефлексивным (антирефлексивным), то называется нестрогим (строгим) порядком. Связный порядок называется линейным. Примеры строгих порядков: <, > на множестве R, Ì, É на множестве 2^M, где M – некоторое множество. Примеры нестрогих порядков: £, ³ на множестве R, Í, Ê на множестве 2^M. Порядки <, >, £, ³ являются линейными, а порядки Ì, É,Í, Ê – нелинейными. Отношение «x делится на y» является нелинейным нестрогим порядком на множестве N, но не на множестве Z. Лексикографический порядок (Расположение слов по алфавиту) является линейным строгим порядком на множество слов некоторого алфавита.

Пара (M,£), где M – непустое множество, а £ – отношение порядка на M, называется упорядоченным множеством M. Наибольшим (наименьшим) элементом упорядоченного множества M называется такой его элемент u, что u³x (u£x) для всех xÎM. Максимальным (минимальным) элементом упорядоченного множества M называется такой его элемент m, что () для всех xÎM. Наибольший (наименьший) элемент является единственным максимальным (минимальным) элементом, но единственный максимальный (минимальный) элемент не является, вообще говоря, наибольшим (наименьшим) элементом.