Binary Relations

\[ A = \{1, 3, 5, 7, 9\}\\ B = \{2, 4, 6, 8, 10\}\\ \\ \begin{aligned} \textrm{Relation: Is less than} = \{&\\ &(1, 2),\\ &(1, 4),\\ &(1, 6),\\ &(1, 8),\\ &(1, 10),\\ &(3, 4),\\ &(3, 6),\\ &(3, 8),\\ &(3, 10),\\ &(5, 6),\\ &...\\ \} \end{aligned} \]
  • A binary relation $R$ is a subset of the cartesian product $A \times B$ of two sets
  • We often write $aRb$ instead of $(a, b) \in R$ ie:
    • “1 $\leq$ 2” instead of $(1, 2) \in \leq$
    • “Bill runs Microsoft” instead of $(\textrm{Bill}, \textrm{Microsoft}) \in \textrm{runs}$

Graphical Representation

  • We can represent the relation $R \subseteq A \times B$ graphically
    • Elements of $A \cup B$ are points
    • Pairs $(a, b) \in R$ are directed edges from $a$ to $b$
---
config:
    layout: elk
---
flowchart TB
    1
    3
    5
    7
    9

    2
    4
    6
    8
    10

    1 --> 2
    1 --> 4
    1 --> 6
    1 --> 8
    1 --> 10

    3 --> 4
    3 --> 6
    3 --> 8
    3 --> 10

    5 --> 6
    5 --> 8
    5 --> 10

    7 --> 8
    7 --> 10

    9 --> 10

Matrix Representation

The relation $R \subseteq A \times B$ can be represented as a $(0, 1)$ matrix

  • Rows represent $A$, columns represent $B$

\[ \begin{pmatrix} 1 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 1 & 1\\ 0 & 0 & 1 & 1 & 1\\ 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 1 \end{pmatrix} \]

Rows top to bottom represent ${1, 3, 5, 7, 9}$ and columns left to right represent ${2, 4, 6, 8, 10}$

Inverse Relation

For a relation $R \subseteq A \times B$, its inverse is the relation $R^{-1}$ such that:
$(a, b) \in R$ if and only if $(b, a) \in R^{-1}$

IE:
The inverse of $\textrm{teaches} \subseteq \textrm{teachers} \times \textrm{classes}$ is $\textrm{is taught by} \subseteq \textrm{classes} \times \textrm{teachers}$

  • Alice teaches Physics
  • Bob teaches CS
$\left(R^{-1}\right)^{-1} = R$

Complement Relation

  • For a relation $R \subset A \times B$, its complement is relation $\overline{R}$ such that:
    • $(a, b) \in \overline{R}$ if and only if $(a, b) \notin R$
  • Example: The complement of $\textrm{teaches} \subseteq \textrm{teachers} \times \textrm{classes}$ is $\textrm{does not teach} \subseteq \textrm{teachers} \times \textrm{classes}$
    • Alice does_not_teach CS
    • Bob does_not_teach Physics

Relations on set

  • A relation on set $A$ is a subset $R \subseteq A \times A$
  • Relations on set are relations where the cartesian product is formed from the same set (the relation is from elements in the same set)
  • Examples:
    • $\textrm{isfriendof} \subseteq \textrm{People} \times \textrm{People}$
    • $\{(1,1), (1,2), (1, 3). (2, 2), (2, 3), (3, 3)\}$ on set $\{1, 2, 3\}$
    • $\{(2, 2), (2, 4), (2, 6), (3, 3), (3, 6), (4, 4), (5, 5), (6, 6)\}$ on set $\{2, 3, 4, 5, 6\}$
    • $\leq \subseteq \mathbb{N} \times \mathbb{N}$
      • $3 \leq 5$
      • $1 \leq 15$
      • $2 \leq 25$
    • $\textrm{divides} \subseteq \mathbb{N} \times \mathbb{N}$
      • 2 divides 6
      • 3 divides 21
      • etc

Properties of Relations

Reflexive

A relation is reflexive iff

  • For all $a \in A$ then $(a, a) \in R$
\[ \begin{pmatrix} 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1 \end{pmatrix} \]

Symmetric

A relation is symmetric iff

  • For all $a, b \in A$ then $(a, b) \in R$ iff $(b, a) \in R$
  • (aka if $a$ and $b$ are related then $b$ and $a$ must be related)
\[ \begin{pmatrix} ? & a & b & c & d\\ a & ? & e & f & g\\ b & e & ? & h & i\\ c & f & h & ? & j\\ d & g & i & j & ? \end{pmatrix} \]

Transitive

A relation is transitive iff

  • For all $a, b, c \in A$
    • If $(a, b) \in R$ and $(b, c) \in R$ then $(a, c) \in R$
    • NOTE THE DIRECTION OF RELATIONS HERE
  • For all $a \in A$, the set of elements we can “reach” is equal to $\{b | (a, b) \in R\}$

Transitive Closure

  • The transitive closure of $R \subseteq A \times A$ is $R^+ \subseteq A \times A$ defined by:

  • The transitive closure of a relation is not transitive (it’s “closing” them)

    • $(a, b) \in R^+$ iff there exist $a_0, …, a_n$ such that
      • $a_0 = a$
      • $a_{n+1} = b$
      • and for every $0 \leq i \lt n$, $(a_i, a_{i+1}) \in R$

  • If $a$ can “reach” $c$ through $b$ then the transitive closure would linke $a$ with $c$ [needs citation]

  • todo: add graphical relation

Transitive and Reflexive closure

  • Like the name suggests the relation $R^*$ is the same as $R$ only transitive relations have been closed and symmetric relations have also been closed
  • $R^* \subseteq A \times A$
    • $R^* = R^+ \cup \{(a, a) | a \in A\}$

Equivalence Relation

The equivalence relation is defined as the relation that is:

  • reflexive
  • symmetric
  • transitive

The set of all equivalence classes in a set under an equivalence relation is denoted as:

\[ A/R = \{[x] : x \in A\} \]

Where $A$ is a set under the equivalence relation $R$.

  • Equivalence classes can be defined formally as such:
    • For every $a \in A$: $[a]_R = \{b | (a, b) \in R\}$
    • $A/_R = \{[a]_r | a \in A\}$ is called the quotient set of $A$ by $R$

Equivalence class of $a$: $[a]_R = \{b | (a, b) \in R\}$
Quotient set: $A/_R = \{[a]_R | a \in A\}$

Example

\[ \textrm{Let } A = \{1, 2, 3, 4\}\\ R = \{(1, 2), (2, 1), (1, 1), (2, 2), (3, 3), (4, 4)\}\\ \\ \textrm{Equivalence Classes:}\\ [1]_R = \{1, 2\}\\ [2]_R = \{1, 2\}\\ [3]_R = \{3\}\\ [4]_R = \{4\}\\ \\ \textrm{Quotient Set:}\\ A/R = \{[1], [2], [3], [4]\}\\ \textrm{or}\\ A/R = \{\{1, 2\}, \{3\}, \{4\}\} \]

Example Equivalence Relation

---
config:
    layout: elk
---
flowchart TD
    a --> a["a"]
    b --> b["b"]
    c --> c["c"]
    d --> d["d"]
    e --> e["e"]
    f --> f["f"]
    g --> g["g"]
    h --> h["h"]
    a <--> b & c
    b <--> c
    d <--> e
    f <--> g
    g <--> h
    h <--> f

Equivalence classes for the above:

  • $[a]_R = [b]_R = [c]_R = \{a, b, c\}$
  • $[d]_R = [e]_R = \{d, e\}$
  • $[f]_R = [g]_R = [h]_R = \{f, g, h\}$

Quotient Set:

  • $\{\{a, b, c\}, \{d, e\}, \{f, g, h\}\}$

Equivalence Relation Theorems

Given equivalence relation $R \subseteq A \times A$, the following is equivalent for all $x, y \in A$

\[ \begin{aligned} (x, y) \in& R\\ [x]_R =& [y]_R\\ [x]_R \cap [y]_R \neq& \emptyset \end{aligned} \]

Given equivalence relation $R \subseteq A \times A$, its equivalence classes form a partition of $A$

\[ \begin{aligned} \cup_{a \in A} [a]_R =& A\\ [x]_R \cap [y]_R =& \emptyset \textrm{ if } [x]_R \neq [y]_R \end{aligned} \]

Example Exercises

Given a partition $P$ and relation $R$ is an equivalence relation:

\[ P = \{A_1, ..., A_n\} \textrm{ of } A\\ R = \{(a, b) | \{a, b\} \subseteq A_i \textrm{ and } i \in \{1, ..., n\}\} \]

Reflexivity

\[ \textrm{Let } a \in A\\ P \textrm{ is a partition, so } a \in A_i \textrm{ and } \{a\} \subseteq A_i \textrm{ for some } i \in \{1, ..., n\}\\ (a, a) \in R \textrm{ for all } a \in A \]

Symmetry

\[ \textrm{Let } (a, b) \in R\\ \textrm{By definition of } R \textrm{:}\\ \{a, b\} \subseteq A_i\\ \therefore \{b, a\} \subseteq A_i\\ \\ (b, a) \in R \]

Transivity

\[ \textrm{Let } (a, b) \in R \textrm{ and } (b, c) \in R\\ \textrm{By definition of } R \textrm{:}\\ \{a, b\} \subseteq A_i\\ \{b, c\} \subseteq A_i\\ \\ A_i \cap A_j \neq \emptyset \textrm{ and } P \textrm{ is a partition}\\ \therefore A_i = A_j\\ \therefore \{a, c\} \subseteq A_i\\ \\ (a, c) \in R \]

Translation:

  • $(a, b)$ and $(b, c)$ are both elements of the equivalence relation
  • By definition of the relation, $\{a, b\}$ must be a subset of an element of the partition
  • By definition of the relation, $\{b, c\}$ must be a subset of an element of the partition
  • Since $b$ appears in both elements, $A_i \cap $_j \neq 0$
  • Since $P$ is a partition, this is only possible if $A_i$ and $A_j$ are the same element
  • Therefore, elements $a$, $b$ and $c$ are all in the same set from the partition
  • Therefore, the set $\{a, c\}$ must be a subset of that element of the partition.
  • This means that $(a, c)$ is in the equivalence relation

Another (Easier?) Exercise

Given a relation $R$ on $A$ calculate the smallest equivalence relation that contains $R$

\[ \begin{aligned} R = \{&\\ &(a, b),\\ &(a, c),\\ &(c, b),\\ &(d, b),\\ &(e, e),\\ &(e, f)\\ \}\\ \end{aligned} \\ \\ \begin{aligned} A = \{&\\ &a,\\ &b,\\ &c,\\ &d,\\ &e,\\ &f,\\ &g\\ \} \end{aligned} \]

Simple answer: connected components will be equivalence classes

\[ \{a, b, c, d\} \times \{a, b, c, d\} \cup\\ \{e, f\} \times \{e, f\} \cup\\ \{(g, g)\} \]

This results in a relation that results in an equivalence relation where transitive, symetric and reflexive properties have been resolved

The Empty Set

Given the relation $R = \emptyset$ on the set $\emptyset$…

The relation is vacuously reflexive as there are no elements to prove otherwise.
This goes for symmetric and transitive.

This means that $R$ is an equivalence relation - HOWEVER, if it is defined on a non-empty set, then it will not be reflexive (as there will be a case where $x \in X$ where $(x, x)$ is not in $R$)

(The above is from stackexchange)