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

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

Пример 4.

Отношение «жить в одном городе» на множестве людей.

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

Эта система обладает следующими свойствами:

1. она образует разбиение множества , то есть классы попарно не пересекаются;

2. любые два элемента из одного класса эквивалентны;

3. любые два элемента из разных классов не эквивалентны.

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

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

Пример 5.

Формулы, описывающие одну и ту же элементарную функцию, находятся в одном классе эквивалентности по отношению равносильности. В данном случае счётными являются само множество формул, множество классов эквивалентности (то есть индекс разбиения) и каждый класс эквивалентности.

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

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

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

Пример 6.

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

б) На системе подмножеств множества отношение включения « » задаёт нестрогий частичный порядок, а отношение строгого включения « » задаёт строгий частичный порядок. Например, , а и не сравнимы.

в) Отношение подчинённости в трудовом коллективе создаёт строгий частичный порядок. В нём, например, несравнимыми являются сотрудники различных структурных подразделений.

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

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

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

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