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

Будем рассматривать отношения, заданные на множестве X, т.е. хρу, х, уX.

Опр. Отношение ρ на множестве X называется рефлексивным, если для любых х X выполняется хρх. Если для всех х  X не выполняется хρх, то отношение называется антирефлексивным.

Примеры. Отношение равенства рефлексивно. Отношение ху, х, у  R рефлексивно, так как хх. Отношение х > у, х, уR антирефлексивно, так как ни для одного числа не выполнимо х > х.

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

Иными слонами, отношение симметрично, если всякий раз, как выполняется хρу, выполняется и уρх.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры.

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

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