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