5. Основные свойства отношений

Примеры. Из того, что «х родственник у», следует, что «у родственник х», - отношение симметрично. Отношение «х – сестра у», определенное на множестве всех людей, несимметрично: возможно, что у является братом х. Однако то же отношение, определенное на множестве женщин, является симметричным.

Опр. Отношение ρ на множестве X называется антисимметричным, если для любых х, у  X, из того, что хρу и уρх, следует х = у.

Примеры. Отношение х у антисимметрично: из того, что х у и у х, следует, что х = у, т.е. это один и тот же элемент.

Опр. Если для любых х, у  Х из того, что хρу, следует, что не выполняется уρх, то отношение называется асимметричным.

Отношения «х предок у» и «у потомок х» асимметричны, причем второе является обратным к первому. Отношение строгого порядка х < у является асимметричным: если выполняется х < у. то не выполняется у < х.

Опр. Отношение ρ называется транзитивным, если из того, что хρу и yρz, следует xρz.

Пример. Отношение «х предок у» транзитивно: если «х предок у» и «у предок z», то «х предок z». Отношение х < у, где х, у  R,транзитивно: если х < у и у < z, то х < г. Отношение «х любит у», в общем случае нетранзитивно: если «х любит у», а «у любит z», то из этого не следует, что «х любит z».

6. Отношение эквивалентности

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

Примеры отношений эквивалентности.

1. Отношение параллельности прямых в евклидовом пространстве есть отношение эквивалентности.

2. Утверждения вида sin 2 x + cos 2 x = 1, (а + b)(a - b) = а 2 - b 2 , состоящие их формул, соединенных знаком равенства, задают би­нарное отношение на множестве формул, описывающих суперпози­ции элементарных функций. Это отношение равносильности также является отношением эквивалентности: формулы равносильны, если они задают одну и ту же функцию.

3. Отношение «студенты х и у учатся в одной группе», где х, у , есть отношение эквивалентности.

4. Отношение «жить в одном районе», определенное па множестве людей, живущих в г. Оренбург, является отношением эквивалентности. Множество всех жителей Оренбурга разбивается последним отноше­нием эквивалентности на ряд непересекающихся подмножеств, в данном случае на множества людей, живущих в одном и том же районе. Два жителя считаются эквивалентными по данному отноше­нию, если они живут в одном и том же районе, и в этом смысле они неразличимы, т.е. они обладают одним и тем же свойством: «жить в районе «XXX». Это свойство является определяющим свойством множества всех жителей района «XXX». С другой стороны, нельзя жить в двух (и более) районах сразу (во всяком случае, согласно прописке), поэтому множества жителей различных районов не пересекаются. Таким образом, отношение «жить в одном районе» разбивает все множество жителей города на ряд непересекающихся подмножеств, таких, что внутри каждого подмножества все жители эквивалентны по данному отношению, и никакие два жителя разных подмножеств не находятся в отноше­нии эквивалентности друг с другом. Такие подмножества называ­ются классами эквивалентности. Ладим более строгое определение.

Опр. Пусть на множестве X задано отношение эквивалентности ρ. Тогда подмножество А X называется классом эквивалентности по отношению ρ, если А состоит из всех тех элементов х  X, что для некоторого а  X, а  А и хρа.

Можно построить классы эквивалентности следующим образом. Выберем элемент а1, принадлежащий X, и образуем подмножество A1 X из а1 и всех элементов, эквивалентных а1. Это будет класс эквивалентности A1. Далее выберем элементу а2 Х, а2 ≠ А1 и образу­ем класс А2, состоящий из всех элементов, эквивалентных а2 и т. д.

Получим систему классов А1, А2, … такую, что любой элемент аi  X входит только в один класс, объединение всех классов А1 А2 . образует множество X, и для любых i, j Аi ∩ Аj = , т.е. множество классов эквивалентности образует разбиение множества X.

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

Будем обозначать класс эквивалентности, порожденный элемен­том а X через [a]. Тогда, если aρb, то [а]=[b].

Опр. Множество классов эквивалентности множе­ства X по отношению ρ называется фактор-множеством множе­ства X по отношению ρ и обозначается [X/ρ].

Свойство параллельности прямых на плоскости определяет отношение эквивалентности.

Типичным примером отношения эквивалентности является отношение равенства (=) на множестве чисел. Очевидно, что лю­бое число а из множества действительных чисел равно самому се­бе. Если а = b, то b = а. Если а =b, а b = с, то а = с.