Relations

• Ordered pair/tuple: $(a, b)$ pair of two objects where order matters
• Product set (cartesian product): $A \times B$, the set of all combinations of pairs from $A$ and $B$
  • Example:
    • $A$ = $\{ 1, 2, 3 \}$
    • $B$ = $\{ a, b, c \}$
    • $A \times B$ = $\{ (1, a), (1, b), (1, c), (2, a), (2, b), (2, c), (3, a), (3, b), (3, c)\}$
• Binary relation: a binary relation $R$ from $S$ to $T$ is a subset $R \subseteq S \times T$ of the product set $S \times T$
  • $(a, b) \subseteq R$: $a$ is related to $b$ by $R$ or $a\ R\ b$
• R-relative set: the $R$-related set of $x$ is set of all elements that are related to $x$
  • Of an element: $R(x)= \{ y \in T \mid x\ R\ y \}$
  • Of a subset: $S_1$ $R(S_1)= \{ y \in T \mid \exists x \in S_1 (x\ R\ y) \}$
• Domain $Dom(R)$: set of all elements that are $R$-related with an element from $T$
• Range $Ran(R)$: set of all elements that are $R^{-1}$-related with an element from $S$
• Inverse relation $R^{-1}$: $(s, t) \in R^{-1} \Leftrightarrow (t, s) \in R$
• In/out degree: count of related to/from elements
  • Digraph: arrows pointing to a vertex / pointing away from a vertex
• Restriction: a relation in which all of the pairs are in a specific set
• Digraph: in the directed graph of $R \subseteq A \times A$:
  • Each element of $A$ is a vertex
  • Each pair $(a, b) \subseteq R$ is an edge

Paths #

Path: a path from $a$ to $b$ is a sequence of legth $n+1$ such that:

$$a\ R\ x_1, x_1\ R\ x_2, ..., x_{n-1}\ R\ b$$

Or just a path in the digraph (easy way).

$R^n(x)$: the set of vertices that can be reached by a path with a length of exactly $n$ from $x$.

Connectivity relation: $R^\infty*x$: set of vertices reached from $x$ via some path.

Path Composition #

• $\pi_1 = a, x_1, ..., x_{n-1}, b$
• $\pi_2 = b, y_1, ..., y_{m-1}, c$
• $\pi_2 \circ \pi_1 = a, x_1, ..., x_{n-1}, b, y_1, ..., y_{m-1}, c$

($\pi_1$ with $\pi_2$ concatenated without middle overlapping element)

Cycles #

Cycle: a path that starts and ends at the same vertex

• Simple: a cycle that contains no other cycles
• Loop: a cycle of length 1

Relation Matrix #

Boolean matrix of a binary relation $R \subset S \times T$: $$ M_{ij} = \begin{cases} 1\ \text{if}(s_i, t_j) \in R \newline 0\ \text{if}(s_i, t_j) \notin R \end{cases} $$

$R^n$ can be calculated using the boolean matrix product:

$$M_{R^n} = M_R \circledcirc M_R \circledcirc ... \circledcirc M_R \text{ ($n$ factors)}$$

Relation Properties #

• Reflexive: $\forall x \in A$: $(x, x) \in R$
  • Matrix: 1's on diagonal
  • Digraph: self loop on all nodes
• Symmetric: $\forall x, y, \in A$: $(x, y) \in R \Rightarrow (y, x) \in R$
  • Matrix: symetric around digagonal
  • Digraph: all two-way edges
• Transitive: $\forall x, y, z \in A$: $(x, y) \in R \land (y, z) \in R$
  • No clear way of recognising, try to find a contradiction when checking
• Irreflexive: $\forall x \in A$: $(x, x) \notin R$
  • Matrix 0's on diagonal
  • Digraph: no self-loops
• Asymmetric: $\forall x, y, \in A$: $(x, y) \in R \Rightarrow (y, x) \notin R$
  • Implies anti-symetric and irreflexive?
  • Matrix: opposites are not both 1 and 0's in matrix diagonal
  • Digraph: one-way edges only and no self-loops
• Anti-symmetric: $\forall x, y \in A$: $((x, y) \in R \land (y,x) \in R) \Rightarrow x = y$
  • Also defined as: $x \neq y \Rightarrow ((x, y) \notin R \lor (y, x) \notin R)$
  • Matrix: opposites are not both 1
  • Digraph: one-way edges only (self loops are allowed)
• Connected: $\forall x, y \in A$: $a \neq b \Rightarrow x\ R\ y \lor y\ R\ x$
  • Digraph: vertices can be reached by a path from any other vertex
  • All elements are comparable which each other

Relation Equivelances #

$R$ is an equivalence relation on set $A$ if it is:

• Reflexive
• Symmetric
• Transitive

Equivalence classes [a] = R(a): partitions of connected elements of $S$

Relation Operations #

• Union $R_1 \cup R_2$: pairs in both relations
  • $(a, b) \in R_1 \cup R_2 \Leftrightarrow a\ R_1\ b \lor a\ R_2\ b$
• Intersection $R_1 \cup R_2$: pairs in at least one of the ralations
  • $(a, b) \in R_1 \cap R_2 \Leftrightarrow a\ R_1\ b \land a\ R_2\ b$
• Complement $\overline{R}$: all pairs that are not in $R$
  • $(a, b) \in \overline{R} \Leftrightarrow (a, b) \notin R$
  • Matrix: each 0 and 1 flipped
• Inverse $R^{-1}$: all pairs inverted
  • $(a, b) \in R^{-1} \Leftrightarrow (b, a) \in R$
  • Matrix: transposed (mirror over diagonal)
• Composition $R_2 \circ R_1$: all pairs from $R_1$ to $R_2$
  • $R_2 \circ R_1 = \{(a, c) \in A \times C \mid \exists b \in B((a, b) \in R_1 \land (b, c) \in R_2)\}$
  • Calculated using boolean matrix product: $M_{R_2 \circ R_1} = M_{R_1} \circledcirc M_{R_2}$
  • Associative

Special relations #

(on set $A$)

• Equalitity relation $\Delta = {(a, a)\mid a \in A}$
• Empty relation $\emptyset \subseteq A \times A$
• Universal relation $A \times A \subseteq A \times A$

Closure #

Closure: relation with added elements to make a certain property holds

Note: a closure does not always exist, sometimes you need to remove pairs instead of add them to make a property hold.

Warshall's algorithm #

Used to calculate the transitive closure $R^{\infty}$ of a relation $R$.

1. Create a matrix $W_0$ of the relation.
2. To calculate the matrix $W_k$ for iteration $k$:
   1. Copy all 1's from the previuos iteration
   2. List all positions of 1's $i$ in column $k$ and positions of 1's $j$ in row $k$
   3. Add 1's in all positions $(i, j)$
   4. Fill the remaining spaces with 0's