Бинарные отношения

Пусть даны два конечных множества %%A%% и %%B%%. Бинарным отношением между элементами множеств %%A%% и %%B%% называется любое подмножество %%R%% множества %%A \times B%%, т.е. %%R \subset A \times B%%.

Для бинарных отношений обычно используется инфиксная форма записи: $$aRb \leftrightarrow (a, b) \in R \subset A \times B$$

Если %%R \subset A \times A%%, то говорят, что бинарное отношение определено на множестве %%A%%.

Областью определения бинарного отношения %%R%% называется множество всех первых элементов пар из %%R%%.

Областью значения бинарного отношения %%R%% называется множество всех вторых элементов пар из %%R%%.

Пусть %%R \subset A \times A%%. Тогда бинарное отношение %%R%% называется:

• рефлексивным, если для любых %%a \in A%% пара %%(a, a) \in R%%;
• антирефлексивным (иррефлексивным), если для любых %%a \in A%% пара %%(a, a) \notin R%%;
• симметричным, если %%(x, y) \in R \Rightarrow (y, x) \in R%%;
• антисимметричным, если %%(x, y) \in R%% и %%(y, x) \in R \Rightarrow x = y%%;
• транзитивным, если %%(x, y) \in R%% и %%(y, z) \in R \Rightarrow (x, z) \in R%%.

Рефлексивное, транзитивное и симметричное отношение %%R%% на множестве %%A%% называется отношением эквивалентности на множестве %%A%%.