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

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

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

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

В то же время, любое разбиение множества на классы определяет некоторое отношение эквивалентности, а именно отношение «входить в один и тот же класс данного разбиения».

Это очень важное утверждение, так как дает основание строго определить свойства рефлексивности, симметричности и транзитивности некоторых отношений. Например, что сказать об отношении, заданном нуль–графом с петлями? Таким будет отношение «жить в одном городе» на множестве, где все люди живут в разных городах. Сам факт, что данное отношение разбивает множество на классы эквивалентности говорит о том, что оно симметрично и транзитивно, хотя граф не имеет ни одного ребра.

Пример.

Пусть множество – это набор разноцветных шаров, а отношение задается условием тогда и только тогда, когда а и b имеют одинаковый цвет. Поскольку – отношение эквивалентности, каждый класс эквивалентности будет состоять из шаров, имеющих одинаковый цвет.

Замечание. Из того, что отношение «жить в одном городе» разбивает множество людей на непересекающиеся подмножества, т.е. является эквивалентностью, следует, что с точки зрения математики вполне естественно утверждение «Иванов живет в одном городе с самим собой», как условие рефлексивности данного отношения. Такие утверждения, не вызывающие сомнения при работе с числами, например , выглядят непривычно, если элементами множеств являются люди.

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

Например, отношение «быть не старше» на множестве людей, «быть не больше» на множестве натуральных чисел» – нестрогий порядок. Отношения «быть моложе», «быть прямым потомком» на множестве людей – строгий порядок.

Элементы сравнимы по отношению порядка на , если выполняется или .

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

· полностью упорядоченным множеством, если любые два элемента этого множества сравнимы по отношению порядка ,

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

Пример.

Отношения полного порядка на множестве людей – быть моложе, быть выше и т.д.

Отношение частичного порядка на множестве людей – быть начальником.

Пример. Каков индекс разбиения и мощности классов эквивалентности по отношению , если – отношение равенства (тождества) на любом множестве;

Ответ: Все классы эквивалентности по отношению равенства на любом множестве состоят из одного элемента. Индекс разбиения по отношению равенства равен мощности множества, т.е. .

Пример. Каков индекс разбиения и мощности классов эквивалентности по отношению , если – отношение «иметь один и тот же остаток от деления на 5» на множестве натуральных чисел .

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