# 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)\}$

- Example:
**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$.

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