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

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

Бинарное отношение $\diamond$ из множества $A$ в множество $B$ — некоторое подмножество $\diamond \subseteq A \times B$ .

Утверждение $(a, b) \in \diamond$ коротко записывается $a \diamond b$ . Эта запись означает, что элемент $a \in A$ находится в отношении $\diamond$ с элементом $b \in B$ .

Если $A = B$ , то есть если $\diamond \subset A^2$ , то говорят, что отношение $\diamond$ является отношением на множестве $A$ .

Инфиксная форма записи

Чаще всего отношения записываются в инфиксной форме (это когда знак отношения стоит между операндами)

a \diamond b \iff (a, b) \in \diamond

С помощью этой инфиксной формы можно компактно записывать сложные утверждения

a \diamond b \diamond c \iff a \diamond b \land b \diamond c

Есть несколько широкоиспользуемых названий и обозначений для отношения $\diamond$ из $A$ в $B$

Множество $A$ называется областью отправления, а множество $B$ называется областью прибытия.

Подмножество $A$ , каждый элемент которого находится в отношении $\diamond$ с каким-то элементом из $B$ называется областью определения (domain) отношения $\diamond$ и обозначается

\dom (\diamond) \defeq \{ a \in A : \exists\, b \in B \; a \diamond b \}

Подмножество $B$ , каждый элемент которого участвует в отношении $\diamond$ с каким-то элементом из $A$ называется областью значений (image) отношения $\diamond$ и обозначается

\im (\diamond) \defeq \{ b \in B : \exists\, a \in A \; a \diamond b \}

Действия над отношениями

Отношения являются множествами, поэтому для них работают обычные множественные операции. Итак, для двух отношений $\alpha \subset A \times B$ и $\beta \subset A \times B$ с совпадающими областями отправления и прибытия можно определить

объединение $\alpha \union \beta$
пересечение $\alpha \sect \beta$
разность $\alpha \without \beta$

Также для одного отношения $\alpha \subset A \times B$ можно определить дополнение до универсального отношения

\alpha^\complement \defeq (A \times B) \without \alpha

Обратное отношение

Пусть $\alpha$ — бинарное отношение из $A$ в $B$ .

Обратное отношение к $\alpha$ — отношение $\alpha^-1$ из $B$ в $A$

\alpha^-1 = \{(b, a) \in B \times A : a \diamond b\}

Другими словами, $b \, \alpha^-1 \, a$ тогда и только тогда, когда $a \, \alpha \, b$

Когда мы ищем обратное, мы как бы «разворачиваем» отношение. Так, например, для отношения $<$ на $\RR$ обратным является $>$ , а для отношения равенства обратное оно само.

Обратным отношением к обратному является исходное

(\alpha^-1)^-1 = \alpha

Для множеств $A$ и $B$ можно задать универсальное отношение $U$ из $A$ в $B$ . Это отношение будет состоять из всех пар $(a, b) \in A \times B$ .

Бинарное отношение $\diamond$ на множестве $X$ можно рисовать в виде псевдоорграфа.

Множество вершин графа в данном случае совпадает с $X$ , а ребро $uv$ проводится только тогда, когда $u \diamond v$ , то есть когда $a$ находится в отношении $\diamond$ с $b$ .

G = \big( X, \{ (u, v) \in V^2 : u \diamond v \} \big)

Композиция отношений

Пусть $\alpha \subset A \times B$ и $\beta \subset B \times C$ — два отношения. Их композицией называется отношение

\alpha \compose \beta \defeq \big\{ (a, c) \in A \times C : \exists\, b \in B \? a \,\alpha\, b \land b \,\beta\, c \big\}

Другими словами, $a \,(\alpha\compose\beta)\, c$ тогда и только тогда, когда существует такое $b \in B$ , что $a \,\alpha\, b$ и $b \,\beta\, c$ .

Например, на множестве $\RR$ композицией отношений $>$ и $\ge$ является отношение $(>) \compose (\ge) = (>)$ .

Композиция отношений $\alpha$ и $\beta$ на одном множестве $X$ , в общем случае, не коммутативна

\alpha \compose \beta \neq \beta \compose \alpha

Композиция отношений ассоциативна. Для трех отношений $\alpha \subset A \times B$ , $\beta \subset B \times C$ и $\gamma \subset C \times D$

\alpha \compose (\beta \compose \gamma) = (\alpha \compose \beta) \compose \gamma

Обратное к произведению отношений является произведение обратных

(\alpha \compose \beta)^-1 = \beta^-1 \compose \alpha^-1

Степень отношения

Степенью отношения $\alpha$ на множестве $X$ называется отношение

\alpha^n \defeq \underbrace{\alpha \compose \alpha \compose \dotsb \compose \alpha}_{n ~\text{раз}}

Отсюда $\alpha^0 = I$ , $\alpha^1 = \alpha$ и $\alpha^2 = \alpha \compose \alpha$ . А вообще, из ассоциативности следует, что $\alpha^{n} = \alpha^{n-1} \compose \alpha$ .

Теорема о маленькой степени

Пусть на множестве $X$ из $n$ элементов задано отношение $\alpha \subset X^2$ .

Если какая-то пара $(x, y)$ принадлежит какой-то степени отношения $\alpha^k$ , то эта же пара принадлежит и степени этого отношения не выше $n-1$ .

\exists\, k \? x \, \alpha^k \, y \implies \exists\, m < n \? x \, \alpha^m \, y

Отсюда можно получить полезный факт. Пусть на множестве $X$ из $n$ элементов задано отношение $\alpha \subset X^2$ . Тогда

\bigunion_{i=1}^\oo \alpha^i = \bigunion_{i=1}^{n-1} \alpha^i

Свойства отношений

Пусть отношение $\diamond$ задано на множестве $X$ .

Рефлексивность

Рефлексивность — $x \diamond x$ для любых $x$ , то есть каждый элемент находится в отношении $\diamond$ с собой.

Антирефлексивность — $x \notdiamond x$ , то есть никакой элемент не находится в отношении $\diamond$ с собой.

Например, равенство по модулю чисел из $\ZZ$ является рефлексивным отношением.

Любое отношение $\alpha$ на множестве $X$ можно сделать рефлексивным, добавив к нему отношение $\nabla_X$ . Получившееся отношение $\alpha \union \nabla_X$ называется рефлексивным замыканием отношения $\alpha$ и обозначается $\alpha^r$ .

Также, любое отношение $\beta$ на множестве $X$ можно сделать антирефлексивным, убрав из него отношение $\nabla_X$ . Получившееся отношение $\beta \without \nabla_X$ не носит какого-то особого названия, но иногда бывает полезным.

Симметричность

Симметричность — $a \diamond b \Harr b \diamond a$ .

Симметричность отношения на псевдоорграфе означает, что между любыми двумя вершинами проведены ребра в обе стороны, а матрица смежности симметрична относительно главной диагонали.

Антисимметричность — $a \diamond b ~\text{и}~ b \diamond a \Rarr a = b$ .

Транзитивность

Транзитивность — $a \diamond b ~\text{и}~ b \diamond c \Rarr a \diamond c$

Нетранзитивность — существуют такие $a, b, c$ , что $a \diamond b ~\text{и}~ b \diamond c \,\nRightarrow\, a \diamond c$

Транзитивное замыкание

Пусть у нас есть какое-то отношение $\alpha$ на $X$ . Нам хочется построить