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

Бинарные отношения в общем случае обладают свойствами рефлексивности, антирефлексивности, симметричности, антисимметричности, транзитивности, связности.

 

1. Рефлексивное отношение – отношение , в котором для любого выполняется

.

Другая запись такого отношения .

Главная диагональ матрицы такого отношения содержит только единицы.

Примером рефлексивного отношения является отношение «подобие треугольников, заданное на множестве всех треугольников евклидовой плоскости»: каждый треугольник подобен себе самому;

отношения « » и «иметь общий делитель».

2. Антирефлексивное отношение – отношение , в котором ни для какого не выполняется

или .

Главная диагональ матрицы такого отношения содержит только нули.

Примером антирефлексивного отношения является отношение «перпендикулярность прямых, заданных на множестве всех прямых евклидовой плоскости»: никакая прямая не перпендикулярна себе самой;

отношения «<» и «быть сыном».

Отношение «быть симметричным относительно оси » не является ни рефлексивным, ни антирефлексивным: точка плоскости симметрична сама себе, если она лежит на оси и несимметрична сама себе в противном случае.

3. Симметричное отношение – отношение , в котором для пары

из следует или .

Иначе говоря, для любой пары отношение симметричности выполняется либо в обе стороны, либо не выполняется вообще. Матрица симметричного отношения симметрична относительно главной диагонали: для любых и . Для симметричного отношения .

Примером симметричного отношения является отношение «быть симметричным относительно оси », которое является симметричным: если первая точка симметрична второй, то и вторая симметрична первой;

отношение «проживать в одном доме», заданное на множестве всех жителей некоторого города: если живет в одном доме с , то живет в одном доме с .

4. Антисимметричное отношение – отношение ,в котором для

пары из и следует, что или

.

Примером антисимметричного отношения является отношение « », заданное на множестве действительных чисел: действительно, если , и , то .

5. Транзитивное отношение – отношение ,в котором для любых

из и следует или

.

Примером транзитивного отношения являются отношения «равенство», « », «жить в одном городе»: действительно если ; если ; если и живут в городе и и живут в городе , то и также живут в городе .

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

Транзитивное замыкание отношения. Транзитивное замыкание отношения – это отношение , которое определяется следующим образом: , если в существует цепочка из элементов , в которой между соседними элементами выполнено отношение : .

Если транзитивно, то . Действительно, если , то (цепочка состоит из двух элементов и ), поэтому . Если же , тосуществует цепочка . Но так как транзитивно, то , поэтому . Из включения в обе стороны следует .

Транзитивным замыканием отношения «быть сыном» является отношение «быть прямым потомком», являющееся объединением отношений «быть сыном», «быть внуком», «быть правнуком» и т.д.

Транзитивным замыканием отношения «иметь общую стену» для жильцов дома является отношение «жить на одном этаже».

6. Связное (полное) отношение – отношение , в котором для пары

из следует или ,

или .

Примером связного (полного) отношения является отношение «быть старше», заданное на множестве родных братьев и сестер некоторой семьи: если , то либо старше , либо старше .

Рассмотренные свойства можно определить с помощью выражений:

1. , 2. , 3. , 4. ,

5. (где – композиция отношений), 6. .

Если даны два отношения и , то операции над этими отношениями сводятся к операциям над ними, аналогичные операциям над множествами:

объединению ; пересечению ; разности ; симметрической разности . Дополнение отношения ( ) будет равно .

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

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

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

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

Отношение строгого линейного порядка – связное отношение строгого порядка.

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