Бинарные отношения, их свойства.

Любое подмножество декартова произведения называется (бинарным) отношением на множестве M.

Пусть и . Тогда пишут .

Приведем основные свойства отношения P, заданного на множестве M:

рефлексивность: для всех xÎM выполняется xPx;

антирефлексивность: для всех xÎM неверно, что xPx;

симметричность: для всех x,yÎM из xPy следует, что yPx;

асимметричность: для всех x,yÎM из xPy следует неверно, что yPx;

антисимметричность: для всех x,yÎM из xPy и yPx следует, что x=y;

транзитивность: для всех x,y,zÎM из xPy и yPz следует, что xPz;

связность: для всех x,yÎM верно, что xPy, или yPz или x=y.

3. Обратное отношение. Композиция отношений. Над отношениями, заданными на множестве M, можно производить те же операции, что над множествами: объединение , пересечение , дополнение .

Отношение называется диагональю множества M.

Отношение называется обратным к отношению .

Отношение называется композицией отношений и .

С помощью операций над отношениями можно охарактеризовать свойства отношений: отношение P на множестве M

рефлексивно тогда и только тогда, когда ;

антирефлексивно тогда и только тогда, когда ;

симметрично тогда и только тогда, когда ;

асимметрично тогда и только тогда, когда ;

антисимметрично тогда и только тогда, когда ;

транзитивно тогда и только тогда, когда ;

связно тогда и только тогда, когда .