Отношение на множестве

Всякое множество ГÌАхА декартово произведение множества А самого на себя называется отношением на множестве А.

Отношение Г называется рефлексивным, если для всех а ÎА верно а Г а. Отношение Г называется симметричным, если для всех а, b ÎА, верно а Г b Þ b Г а.

Отношение Г называется транзитивным, если для любого а,b, с ÎА, а Г b, b Г с Þ а Г с.

Отношение Г называется антирефлексивным, если для любого а ÎА а Г а никогда не выполняется.

Отношение Г называется антисимметричным, если для любого а ÎА и b ÎА а Г b и b Г а одновременно невозможно.

Отношение Г называется асимметричным, если для любых а, b ÎА из а Г b и b Г а Þ а=b.

Если отношение Г рефлексивно, симметрично и транзитивно, то оно называется отношением эквивалентности.

Теорема. Если на множестве А задано отношение эквивалентности Г, то множество А распадается на объединение непересекающихся классов эквивалентности.

Отношение Г называется отношением нестрогого порядка, если оно рефлексивно, асимметрично, транзитивно.

Отношение Г называется отношением строгого порядка, если оно антирефлексивно, антисимметрично и транзитивно.

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