• 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