декартовы отношения

Отношение — множество упорядоченных пар; один набор пар можно читать как список, матрицу или ориентированный граф.

упорядоченные пары и произведение

В паре $(a,b)$ порядок важен: $(a,b)=(c,d)$ тогда и только тогда, когда $a=c$ и $b=d$.

$A\times B$ состоит из всех $(a,b)$, где $a\in A$, $b\in B$. Для конечных множеств выборы независимы, поэтому мощности перемножаются.

$$A\times B=\{(a,b)\mid a\in A\land b\in B\},\qquad |A\times B|=|A|\cdot|B|$$

выписываем все пары

условие: $A=\{1,2\}$, $B=\{x,y,z\}$. Найти $A\times B$.

ход решения

1. Для $1$ берём все три вторых компонента

2. Повторяем для $2$

3. Проверяем: $2\cdot3=6$

ответ: $A\times B=\{(1,x),(1,y),(1,z),(2,x),(2,y),(2,z)\}$.

проверка: $|A\times B|=6$.

отношение и его области

Бинарное отношение из $A$ в $B$ — любое $R\subseteq A\times B$. Область определения содержит первые компоненты пар, область значений — вторые. Для $R=\{(1,a),(1,b),(3,b)\}$ это $\{1,3\}$ и $\{a,b\}$.

$$\operatorname{Dom}R=\{a\in A\mid\exists b\in B:(a,b)\in R\},\quad\operatorname{Ran}R=\{b\in B\mid\exists a\in A:(a,b)\in R\}$$

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

Для свойств $R$ должно быть отношением на одном $A$: $R\subseteq A\times A$.

антисимметричность не есть «несимметричность»

Петли $(a,a)$ разрешены; запрещены две встречные пары для разных $a,b$.

матрица и орграф

Для $A=\{1,2,3\}$ и $R=\{(1,1),(1,2),(2,3),(3,1)\}$ строка матрицы — первая компонента, столбец — вторая; в орграфе $(i,j)$ становится стрелкой $i\to j$.

что запомнить

• В упорядоченной паре важен порядок.

• $|A\times B|=|A|\cdot|B|$ для конечных множеств.

• Отношение из $A$ в $B$ — подмножество $A\times B$.

• Матрица и орграф кодируют один набор пар.

самопроверка

• Почему $A\times B$ обычно не равно $B\times A$?

• Как найти $\operatorname{Dom}R$ и $\operatorname{Ran}R$?

• Как в матрице видны рефлексивность и симметричность?

• Почему $\le$ антисимметрично, но не симметрично?

источники

• материал занятия: конспект «декартовы отношения» — /materials/lectures/cartesian-relations.pdf

• редакционная сверка: Discrete Mathematics: An Open Introduction — Relations and Graphs — https://discrete.openmathbooks.org/dmoi4/sec_gt-relations.html

• редакционная сверка: MIT OpenCourseWare: Mathematics for Computer Science, readings — https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-fall-2010/resources/readings/