Relations

Introduction

A relation is a subset of the Cartesian product of two sets. For two sets $A$ and $B$, $R \subseteq A \times B$.

The equality relation for the set of integers can be expressed $R = \{(x,y) \in \mathbb{Z} \times \mathbb{Z} : x = y\}$. This is the set of pairs of equal integers.

The inverse of a relation, $R$, is the relation $R^{-1}$. This can be expressed as $R^{-1} = \{(b,a)\in B \times A : (a,b) \in \mathbb{R}\}$.

Because relations are sets, you can apply set theoretic operations to them.

Composition of relations

The composition of two relations, $R$ and $Q$ is shown as $R \circ Q$. Suppose $R$ is a relation between $a$ and $b$ and $Q$ is a relation between $b$ and $c$. $R \circ Q = \{(a,c) \in A \times C : \text{There is a } b \in B \text{ such that } (a,b) \in R, (b,c) \in Q\}$.

Properties of relations on a set

A relation $R$ on a set $S$ is reflexive if $aRa$ for every $a \in S$. This means the relation holds for every pair where both elements are the same.

A relation is symmetric if $aRb$ implies $bRa$ for all $a,b \in S$.

A relation is antisymmetric if $aRb$ and $bRa$ imply $a=b$. This means for a particular relation if $aRb$ and $bRa$ then $a = b$ must be true. For example, $R = \{(x,y) \in \mathbb{Z}^2 : x\leq y\}$ is antisymmetric because $aRb$ and $bRa$ only hold when $a =b$.

A relation is transitive if $aRb$ and $bRc$ implies $aRc$.

A relation is called an equivalence relation if it is reflexive, symmetric and transitive.

A relation is a partial order relation if it is reflexive, antisymmetric and transitive.

Equivalence relations

Equivalence relations and equivalence classes

Given a set $S$ which has an equivalence relation $R$, the equivalence class, $[a]$, is $\{x \in S : aRx\}$. This means the set of values in $S$ such that $a$ and $x$ are related by $R$.
As an example, given the set of integers $\mathbb{Z}$, $[5] = \{5\}$ as it is the only value in the set equal to 5.
Given $R = \{(x,y) \in \mathbb{Z}^2 : x-y \text{ is even }\}$, $[5]$ would be $\{5, 3, 1, ..., 7, 9, ...\}$ or just the set of odd numbers, as this is the set of numbers which when subtracted from 5 are even.

Representatives of equivalence classes

Any element from an equivalence class is called a representative of it.
For example, if $x \in [a]$, then $x$ is a representative of $[a]$.

Lemma 1 - Every equivalence class is generated by any of it's representatives.
This can be expressed as $\forall b \in [a],\: [b]=[a]$.

Second lemma

Lemma 2 - $\forall a,b \in S$ either $[a] \cap [b] = \emptyset$ or $[a]=[b]$. This means for two representatives of a set, their equivalence classes are either equal or do not overlap.

Partitions

Sets $(A_i){i \in I}$ form a partition of a set $B$ if $\displaystyle\bigcup{i \in I}{A_i} = B$ and $A_i \cap A_j = \emptyset$ for all $i,j \in I, i \neq j$.

The quotient of $S$ with respect to relation $R$ is denoted by $S/R$, where $S/R = \{[a]_R : a \in S\}$.

Examples

Example 1: Let $S = \mathbb{Z}$ and $E = \{(x,x) : x \in \mathbb{Z}\}$. $\mathbb{Z}/E=\{[a]_E:a \in \mathbb{Z}\} = \{\{x \in \mathbb{Z}:aEx\}:a \in \mathbb{Z}\}=$
$\{\{x\}:x \in \mathbb{Z}\}=\{\{0\},\{1\},...,\}$.

Example 2: Let $T = \{(x,y) : x,y \in \mathbb{Z}\}$. $\mathbb{Z}/T = \{\mathbb{Z}\}$?

Example 3: $S = \mathbb{Z} \times (\mathbb{Z} \setminus \{0\})$ and $R = \{((a,b),(c,d)): a \times d = b \times c\}$. $S/R = \mathbb{Q}$?