§ 2. Свойства отношений

Отношение, заданное на множестве, может обладать рядом свойств, а именно:

2. Рефлексивность

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

Используя символы, это отношение можно записать в таком виде:

R рефлексивно наХ (х Х)х R х

Пример. Отношение равенства на множестве отрезков рефлексивно, т.к. каждый отрезок равен себе самому.

Граф рефлексивного отношения во всех вершинах имеет петли.

2. Антирефлексивность

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

R антирефлексивно наХ (х Х)

Пример.Отношение «прямаяхперпендикулярна прямойу» на множестве прямых плоскости антирефлексивно, т.к. ни одна прямая плоскости не перпендикулярна самой себе.

Граф антирефлексивного отношения не содержит ни одной петли.

Заметим, что существуют отношения, не являющиеся ни рефлексивными, ни антирефлексивными. Например, рассмотрим отношение «точка хсимметрична точкеу» на множестве точек плоскости.

 у

l

х

Точка хсимметрична точкех– истинно; точкау симметрична точкеу– ложно, следовательно, мы не можем утверждать, что все точки плоскости симметричны сами себе, также мы не можем и утверждать, что ни одна точка плоскости не симметрична сама себе.

3. Симметричность

Определение. ОтношениеR на множествеХназывается симметричным, если из того, что элементхнаходится в отношенииRс элементому, следует, что и элементунаходится в отношенииRс элементомх.

R симметрично наХ (х,у Х)х R у у R х

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

Граф симметричного отношения вместе с каждой стрелкой из точки хв точкуудолжен содержать стрелку, соединяющую те же точки, но в обратном направлении.

4. Асимметричность

Определение. ОтношениеR на множествеХназывается асимметричным, если ни для каких элементовх,уиз множестваХ не может случиться, что элементхнаходится в отношенииRс элементомуи элементунаходится в отношенииRс элементомх.

R асимметрично наХ (х,у Х)х R у

Пример. Отношение «х<у» асимметрично, т.к. ни для какой пары элементовх,унельзя сказать, что одновременнох<у иу < х.

Граф асимметричного отношения не имеет петель и если две вершины графа соединены стрелкой, то эта стрелка только одна.

5. Антисимметричность

Определение. ОтношениеR на множествеХназывается антисимметричным, если из того чтохнаходится в отношении су, аунаходится в отношении схследует, чтох=у.

R антисимметрично наХ (х,у Х)х R ууR х х = у

Пример. Отношение «х  у» антисимметрично, т.к. условиях  у иу  х одновременно выполняются только тогда, когдах=у.

Граф антисимметричного отношения имеет петли и если две вершины графа соединены стрелкой, то эта стрелка только одна.

6. Транзитивность

Определение. ОтношениеR на множествеХназывается транзитивным, если для любых элементовх,у,zиз множестваХиз того, чтохнаходится в отношении су, аунаходится в отношении сz следует, чтох находится в отношении сz.

R транзитивно наХ (х,у,z Х)х R ууR z х R z

Пример.Отношение «хкратноу» транзитивно, т.к. если первое число кратно второму, а второе кратно третьему, то первое число будет кратно третьему.

Граф транзитивного отношения с каждой парой стрелок от хкуи оту кzсодержит стрелку, идущую отхкz.

7. Связность

Определение. ОтношениеR на множествеХназывается связным, если для любых элементовх,у из множестваХхнаходится в отношении суилиунаходится в отношении схилих = у.

R связно наХ (х,у,z Х)х R ууR z  х =у

Другими словами: отношение R на множествеХназывается связным, если для любых различных элементовх,у из множестваХхнаходится в отношении суилиунаходится в отношении схилих = у.

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

На графе связного отношения все вершины соединены между собой стрелками.

Пример.Проверить, какими свойствами обладает

отношение «х – делительу», заданное на множестве

Х = {2; 3; 4; 6; 8}.

Построим граф данного отношения:

1. данное отношение рефлексивно, т.к. каждое число из данного множества является делителем самого себя;

2. свойством антирефлексивности данное отношение не обладает;

3. свойство симметричности не выполняется, т.к. например, 2 является делителем числа 4, но 4 делителем числа 2 не является;

4. данное отношение антисимметрично: два числа могут быть одновременно делителями друг друга только в том случае, если эти числа равны;

5. отношение транзитивно, т.к. если одно число является делителем второго, а второе – делителем третьего, то первое число обязательно будет делителем третьего;

6. отношение свойством связности не обладает, т.к. например, числа 2 и 3 на графе стрелкой не соединены, т.к. два различных числа 2 и 3 делителями друг друга не являются.

Таким образом, данное отношение обладает свойствами рефлексивности, асимметричности и транзитивности.