Эквивалентность и порядок

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

Отношением эквивалентности (или просто эквивалентностью ) называют бинарное отношение на множестве, если оно рефлексивно, симметрично, транзитивно. Например, отношение "жить в одном городе" на множестве людей - эквивалентность.

Отношение эквивалентности имеет важную особенность: эквивалентность R разбивает множество М, на котором оно задано, на непересекающиеся подмножества так, что элементы одного и того же подмножества находятся в отношении R, а между элементами из разных подмножеств отношение R отсутствует. В таком случае говорят, что отношение R задает разбиение на множестве М, или систему классов эквивалентности по отношению R. Мощность этой системы называется индексом разбиения. В то же время любое разбиение множества М на классы определяет некоторое отношение эквивалентности, а именно отношение "входить в один и тот же класс данного разбиения".

Отношением нестрогого порядка (или нестрогим порядком ) называют бинарное отношение на множестве, если оно рефлексивно, антисимметрично, транзитивно, и отношением строго порядка (строгим порядком), если оно антирефлексивно, антисимметрично, транзитивно. Оба эти отношения называются отношениями порядка. Например, отношения "быть не старше" на множестве людей, "быть не больше" на множестве натуральных чисел - нестрогий порядок; отношения "быть моложе", "быть прямым потомком" на множестве людей - строгий порядок.

Элементы а,bÎ M сравнимы по отношению порядка R на М, если выполняется a R b или b R a.

Множество М, на котором задано отношение порядка, может быть:

а) полностью упорядоченным множеством, если любые два элемента из М сравнимы по отношению порядка. В таком случае говорят, что отношение R задает полный порядок на множестве М. Например, отношение "быть не старше" задает полный порядок на множестве людей;

б) частично упорядоченным множеством - в противном случае. При этом говорят, что отношение R задает на множестве М частичный порядок. Например, отношение "быть начальником" задает на множестве сотрудников организации частичный порядок, так как, например, для пары сотрудников одного отдела данное отношение не выполняется: они не сравнимы по данному отношению.