Relations

Definition

A binary relation $R$ from set $A$ to set $B$ is a subset of $A \times B$: $R \subseteq A \times B$

If $(a, b) \in R$, we write $aRb$ or $R(a, b)$.

A relation on $A$ is a relation from $A$ to $A$: $R \subseteq A \times A$.

Representations

Set of Ordered Pairs

$R = \{(1, 2), (1, 3), (2, 3)\}$

Matrix Representation

For $A = \{a_1, \ldots, a_m\}$ and $B = \{b_1, \ldots, b_n\}$:

$M_R[i,j] = \begin{cases} 1 & \text{if } (a_i, b_j) \in R \\ 0 & \text{otherwise} \end{cases}$

Digraph (Directed Graph)

• Vertices represent elements
• Directed edge from $a$ to $b$ if $aRb$

Properties of Relations on a Set

Reflexive

Every element is related to itself: $\forall a \in A: (a, a) \in R$

Matrix: All diagonal entries are 1. Digraph: Every vertex has a self-loop.

Irreflexive

No element is related to itself: $\forall a \in A: (a, a) \notin R$

Symmetric

If $a$ is related to $b$, then $b$ is related to $a$: $\forall a, b \in A: (a, b) \in R \rightarrow (b, a) \in R$

Matrix: $M_R = M_R^T$ (symmetric matrix). Digraph: Every edge has a reverse edge.

Antisymmetric

If $a$ is related to $b$ and $b$ is related to $a$, then $a = b$: $\forall a, b \in A: ((a, b) \in R \land (b, a) \in R) \rightarrow a = b$

Equivalently: If $a \neq b$ and $(a, b) \in R$, then $(b, a) \notin R$.

Asymmetric

If $a$ is related to $b$, then $b$ is not related to $a$: $\forall a, b \in A: (a, b) \in R \rightarrow (b, a) \notin R$

Note: Asymmetric implies irreflexive and antisymmetric.

Transitive

If $a$ is related to $b$ and $b$ is related to $c$, then $a$ is related to $c$: $\forall a, b, c \in A: ((a, b) \in R \land (b, c) \in R) \rightarrow (a, c) \in R$

Examples

"Less than" on $\mathbb{Z}$

Property	$<$
Reflexive	No ($a \not< a$)
Symmetric	No ($a < b \not\Rightarrow b < a$)
Antisymmetric	Yes (vacuously)
Transitive	Yes

"Divides" on $\mathbb{Z}^+$

$a \mid b$ means $a$ divides $b$ (i.e., $b = ka$ for some integer $k$)

Property	$\mid$
Reflexive	Yes ($a \mid a$)
Symmetric	No ($2 \mid 4$ but $4 \nmid 2$)
Antisymmetric	Yes (on $\mathbb{Z}^+$)
Transitive	Yes

Combining Relations

Union

$R_1 \cup R_2 = \{(a, b) \mid (a, b) \in R_1 \lor (a, b) \in R_2\}$

Intersection

$R_1 \cap R_2 = \{(a, b) \mid (a, b) \in R_1 \land (a, b) \in R_2\}$

Complement

$\overline{R} = \{(a, b) \mid (a, b) \notin R\}$

Inverse

$R^{-1} = \{(b, a) \mid (a, b) \in R\}$

Composition of Relations

If $R$ is from $A$ to $B$ and $S$ is from $B$ to $C$: $S \circ R = \{(a, c) \mid \exists b \in B: (a, b) \in R \land (b, c) \in S\}$

Matrix Representation

If $M_R$ and $M_S$ are relation matrices: $M_{S \circ R} = M_R \odot M_S$

where $\odot$ is Boolean matrix multiplication.

Powers of a Relation

$R^1 = R$ $R^{n+1} = R^n \circ R$

Closure of Relations

The closure adds the minimum pairs to make a relation have a property.

Reflexive Closure

$r(R) = R \cup \{(a, a) \mid a \in A\} = R \cup I_A$

Symmetric Closure

$s(R) = R \cup R^{-1}$

Transitive Closure

$t(R) = R \cup R^2 \cup R^3 \cup \cdots = \bigcup_{i=1}^{\infty} R^i$

For finite set with $|A| = n$: $t(R) = \bigcup_{i=1}^{n} R^i$

Warshall's Algorithm

Computes transitive closure efficiently in $O(n^3)$:

for k = 1 to n:
    for i = 1 to n:
        for j = 1 to n:
            M[i,j] = M[i,j] OR (M[i,k] AND M[k,j])