Свойства бинарных отношений

Пусть rзадано на множестве X, r Í Х².

1. Рефлексивность: " х Î Х х r х.

Отношение rна множестве X называется рефлексивным, если для любого хÎХимеет место х r х,то есть каждый элемент находится в отношении rк самому себе.

Матрица рефлексивного отношения имеет единичную главную диагональ, а граф – петлю возле каждого своего элемента.

 

2. Антирефлексивность: х Î Х х r х.

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

 

Матрица антирефлексивного отношения имеет нулевую главную диагональ,а граф – не имеет ни одной петли.

 

3. Нерефлексивность: $ х Î Х (x, x) Ï r.

4. Симметричность: " х, y Î Х х r y => y r х.

Отношение rна множестве X называется cимметричным, если для всех хи yизХ,из принадлежности(x,y)отношению rследует, что и (y,x)принадлежит отношению r.

Матрица симметричного отношения симметрична относительно главной диагонали, а граф – для каждой дуги (x,y)существует обратная дуга (y,x).

 

5. Антисимметричность: " х, y Î Х х r y, y r х Û x = y.

Отношение rна множестве X называется антиcимметричным, если для всех хи yизХ,из принадлежности(x,y)и (y,x)отношению rследует, что x=y.

Матрица антисимметричного отношения не имеет ни одной симметричной единицы относительно главной диагонали, а граф – для каждой дуги (x,y)не существует обратная дуга (y,x)и наоборот.

Свойства симметричности и антисимметричности не являются взаимоисключающими, примером может служить отношения равенства на множестве натуральных чисел.

 

6. Транзитивность: " х, y, z Î Х х r y, y r z => x r z.

Отношение rна множестве X называется транзитивным, если для всех х,y,zизХ,из принадлежности(x,y)и (y,z)отношению rследует, что (x,z)также принадлежитr.

Отношение rна множестве X называется антитранзитивным, если для всех х,y,zизХ,из принадлежности(x,y)и (y,z)отношению rне следует, что (x,z)также принадлежитr.

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

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

r= { (x, y) | x³y, x,y Î N},

r= { (x, y) | x£y, x,y Î N}.

На множестве множеств: “A Í B”, “A=B”.

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

r= { (x, y) | x>y, x,y Î N},

r= { (x, y) | x<y, x,y Î N}.

На множестве множеств: “A Ì B”.

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

Отношения полного порядка:

r= { (x, y) | x³y, x,y Î N },

r= { (x, y) | x£y, x,y Î N }.

Отношения частичного порядка:

r= { (x, y) | x>y, x,y Î N },

r= { (x, y) | x<y, x,y Î N },

на множестве множеств: “A Í B”, “A Ì B”.