Бинарные отношения, их свойства.
Любое подмножество декартова произведения называется (бинарным) отношением на множестве 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
рефлексивно тогда и только тогда, когда ;
антирефлексивно тогда и только тогда, когда ;
симметрично тогда и только тогда, когда ;
асимметрично тогда и только тогда, когда ;
антисимметрично тогда и только тогда, когда ;
транзитивно тогда и только тогда, когда ;
связно тогда и только тогда, когда .