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

Пусть даны два конечных множества $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$.