Relations: partial orders, equivalences

Let $\mathbb{A}$ be a set.

• A relation on $\mathbb{A}$ is a subset $\mathbb{R}$ of $\mathbb{A}\times \mathbb{A}$.
• The empty relation on $\mathbb{A}$ is the subset $\mathbb{R} = \phi$ of $\mathbb{A}\times \mathbb{A}$.
• The full relation on $\mathbb{B}\subset \mathbb{A}$ is the subset $\mathbb{R}_{\mathbb{B}} = \mathbb{B}\times \mathbb{B}$ of $\mathbb{A}\times \mathbb{A}$.
• The identity relation on $\mathbb{B}\subset \mathbb{A}$ is the subset $\mathbb{I}_\mathbb{B} = \{(b, b): b\in \mathbb{B}\}$ of $\mathbb{A}\times \mathbb{A}$. Note that if $\mathbb{R} \subset \mathbb{I}_\mathbb{A}$, then $\mathbb{R} = \mathbb{I}_{\mathbb{B}}$, for a unique subset $\mathbb{B}$ of $\mathbb{A}$.

If $\mathbb{R}$ is a relation on $\mathbb{A}$ and if $(a, b) \in \mathbb{R}$, we often write $a\mathbb{R}b$.

• The transpose $\mathbb{R}'$ of a relation on $\mathbb{A}$ is the set $\mathbb{R}' = \{(b, a): (a, b) \in \mathbb{R}\}$. Then $\mathbb{R}'$ is a relation on $\mathbb{A}$ and we have $(\mathbb{R}')' = \mathbb{R}$.
  We have $a\mathbb{R}'b$ if and only if $b\mathbb{R}a$.
• If $\mathbb{R}$ and $\mathbb{S}$ are relations on a set $\mathbb{A}$, then their composition $\mathbb{R}\circ \mathbb{S}$ is the set:
  $$\hspace{-20pt} \mathbb{R}\circ \mathbb{S}= \{ (a, c) \in \mathbb{... ...b) \in \mathbb{R}\hspace{3pt} \textrm{and} \hspace{3pt}(b, c) \in \mathbb{S}\}.$$
  Then $\mathbb{R}\circ \mathbb{S}$ is a relation on $\mathbb{A}$.
  We have $a\mathbb{R}\circ \mathbb{S}b$ if and only if $a\mathbb{R}b$ and $b\mathbb{S}c$, for some $b \in \mathbb{A}$.
  We abbreviate the composition $\mathbb{R}\circ \mathbb{R}$ by $\mathbb{R}^2$.
  The composition of relations is associative: for example, if $\mathbb{R}$, $\mathbb{S}$ and $\mathbb{T}$ are relations on $\mathbb{A}$ we may put:
  $$\hspace{-20pt}\mathbb{R}\circ \mathbb{S}\circ \mathbb{T}= \{(a, d... ...\textrm{and} \hspace{3pt} c \hspace{3pt} \textrm{in} \hspace{3pt} \mathbb{A}\}.$$
  Then we have, for any relations $\mathbb{R}$, $\mathbb{S}$ and $\mathbb{T}$ on $\mathbb{A}$:
  $$\mathbb{R}\circ ( \mathbb{S}\circ \mathbb{T}) = (\mathbb{R}\circ \mathbb{S})\circ \mathbb{T}= \mathbb{R}\circ \mathbb{S}\circ \mathbb{T}.$$
  In general, we may compose relations successively, without using parentheses.
  In particular, for any relation $\mathbb{R}$ on $\mathbb{A}$ and for any positive integer $n$, we may construct the $n$-fold composition of $\mathbb{R}$ with itself, giving the relation $\mathbb{R}^n$, with $\mathbb{R}^1 = \mathbb{R}$ and $\mathbb{R}^2 = \mathbb{R} \circ \mathbb{R}$.
  Notice that $\mathbb{R}^n$ consists of chains of successively related elements of $\mathbb{A}$:
  $$\hspace{-35pt} \mathbb{R}^n = \{(a_1, a_{n+1}) \in \mathbb{A}\tim... ...in \mathbb{R}, \hspace{3pt} \textrm{for all} \hspace{3pt} j \in \mathbb{N}_n\}.$$

A relation $\mathbb{R}$ on a set $\mathbb{A}$ is said to be:

• Reflexive, if and only if $\mathbb{I}_\mathbb{A} \subset \mathbb{R}$, if and only if $(a, a) \in \mathbb{R}$ for all $a \in \mathbb{A}$.
• Symmetric, if and only if $\mathbb{R} = \mathbb{R}'$, if and only if $(a, b) \in \mathbb{R}$ implies that $(b, a) \in \mathbb{R}$.
• Anti-symmetric, if and only if $\mathbb{R}\cap\mathbb{R}' = \phi$, if and only if whenever $(a, b) \in \mathbb{R}$, then $(b, a) \notin \mathbb{R}$.
• Transitive, if and only if $\mathbb{R}^2 \subset \mathbb{R}$, if and only if whenever $(a, b) \in \mathbb{R}$ and $(b, c) \in \mathbb{R}$, then $(a, c) \in \mathbb{R}$.

There are many special kinds of relations $\mathbb{R}$ on a set $\mathbb{A}$:

• A relation $f$ on $\mathbb{A}$ is said to be a function if and only if whenever $(x, y) \in f$ and $(x, z) \in f$, then $y = z$, if and only if $f'\circ f \subset \mathbb{I}_\mathbb{A}$.

Then $f'\circ f = \mathbb{I}_{\mathcal{R}(f)}$, for some unique subset $\mathcal{R}(f)$ of $\mathbb{A}$, called the range of $f$.
Also we have $(f\circ f')\cap \mathbb{I}_{\mathbb{A}} = \mathbb{I}_{\mathcal{D}(f)}$, for some unique subset $\mathcal{D}(f)$ of $\mathbb{A}$.
Then the set $\mathcal{D}(f)$, called the domain of $f$.

• If $f$ is a function on $\mathbb{A}$, then $f$ is said to be surjective if and only if it has range $\mathbb{A}$ if and only if $f'\circ f = \mathbb{I}_\mathbb{A}$.
• If $f$ is a function on $\mathbb{A}$, then $f$ is said to be injective if and only if $f'$ is also a function if and only if $f'\circ f \subset \mathbb{I}_\mathbb{A}$ and $f\circ f' \subset \mathbb{I}_\mathbb{A}$.
• If $f$ is a function with domain $\mathbb{B}$ and with $\mathcal{R}(f) \subset \mathbb{C}$, then $f$ is said give a well-defined function from $\mathbb{B}$ to $\mathbb{C}$.
  • $f$ is an surjection from $\mathbb{B}$ to $\mathbb{C}$ if and only if $(f\circ f')\cap \mathbb{I}_{\mathbb{A}} = \mathbb{I}_{\mathbb{B}}$ and $f'\circ f = \mathbb{I}_{\mathbb{C}}$.
  • $f$ is an injection from $\mathbb{B}$ to $\mathbb{C}$ if and only if $f\circ f' = \mathbb{I}_{\mathbb{B}}$. and $f'\circ f \subset \mathbb{I}_{\mathbb{C}}$.
  • $f$ is an bijection from $\mathbb{B}$ to $\mathbb{C}$ if and only if $f\circ f' = \mathbb{I}_{\mathbb{B}}$ and $f'\circ f = \mathbb{I}_{\mathbb{C}}$. In this case $f'$ is a bijection from $\mathbb{C}$ to $\mathbb{B}$.

• A relation $f$ on $\mathbb{A}$ is a bijection from $\mathbb{A}$ to itself, if and only if we have $f\circ f' = f'\circ f = \mathbb{I}_{\mathbb{A}}$.
• If $f$ and $g$ are functions on $\mathbb{A}$, so are $f\circ g$ and $g\circ f$ (although one of both of these may be empty relations).
• $\mathbb{R}$ is a partial order if and only if $\mathbb{R}$ is anti-symmetric and transitive.
• $\mathbb{R}$ is a total order if and only if $\mathbb{R}$ is a partial order and trichotomy holds: $\mathbb{R}\cup \mathbb{R}' \cup \mathbb{I}_{\mathbb{A}} = \mathbb{R}_{\mathbb{A}} = \mathbb{A}\times \mathbb{A}$.
• $\mathbb{R}$ is an equivalence relation if and only if $\mathbb{R}$ is reflexive, symmetric and transitive.

Let $\mathbb{R}$ be any relation on $\mathbb{A}$.
Put $\mathbb{S} = \mathbb{R}\cup \mathbb{R}'\cup \mathbb{I}_\mathbb{A}$.
Then $\mathbb{S}$ is symmetric and reflexive.
Then put $\mathbb{E}(\mathbb{R}) = \bigcup_{n \in \mathbb{N}} \mathbb{S}^n$.
Then $\mathbb{E}(\mathbb{R})$ is an equivalence relation on $\mathbb{A}$, called the equivalence relation generated by $\mathbb{R}$.
Then we have $\mathbb{E}(\mathbb{R}) = \mathbb{E}(\mathbb{R}')$ and $\mathbb{E}(\mathbb{E}(\mathbb{R})) = \mathbb{E}(\mathbb{R})$, for any relation $\mathbb{R}$ on $\mathbb{A}$. If $\mathbb{T}$ is another relation on $\mathbb{A}$, then $\mathbb{R}\subset \mathbb{T}$ implies that $\mathbb{E}(\mathbb{R}) \subset \mathbb{E}(\mathbb{T})$.
Also $\mathbb{R}$ is an equivalence relation if and only if $\mathbb{E}(\mathbb{R}) = \mathbb{R}$.
Also if $\mathbb{F}$ is any equivalence relation, such that $\mathbb{R}\subset \mathbb{F}$, then $\mathbb{E}(\mathbb{R}) \subset \mathbb{F}$.
So we have:

$$\mathbb{E}(\mathbb{R}) = \bigcap_{\mathbb{R}\subset \mathbb{F}, \... ...\, \textrm{an equivalence relation}\,\, \textrm{on}\,\, \mathbb{A}} \mathbb{F}.$$

So the equivalence relation generated by $\mathbb{R}$ is the smallest subset of $\mathbb{A}\times \mathbb{A}$ that contains $\mathbb{R}$ as a subset and is an equivalence relation. Note that if $\mathbb{B}\subset \mathbb{A}$, then the relation $\mathbb{B}\times \mathbb{B}$ on $\mathbb{A}$ is symmetric and transitive and the relation $(\mathbb{B}\times \mathbb{B})\cup \mathbb{I}_{\mathbb{A}}$ is an equivalence relation on $\mathbb{A}$.

Let now $\mathbb{R}$ be an equivalence relation on a set $\mathbb{A}$.

• For each $a \in \mathbb{A}$ define:
  $$\mathbb{R}(a) = \{x \in \mathbb{A}: (a, x) \in \mathbb{R}\}\subset \mathbb{A},$$
  $$\mathcal{X}(a) = \mathbb{R}_a\times \mathbb{R}_a = \{ (x, y) \in ... ...space{3pt} \textrm{and}\hspace{3pt} (a, y) \in \mathbb{R}\} \subset \mathbb{R}.$$

Then we have the properties:

• $a \in \mathbb{R}(a) \ne \phi$ and $(a, a) \in \mathcal{X}(a) \ne \phi, \hspace{3pt} \textrm{for any} \hspace{3pt} a \in \mathbb{A}$.
• $\mathcal{X}(a)$ is a symmetric and transitive relation on $\mathbb{A}$.
• If $a$ and $b$ are elements of $\mathbb{A}$ such that $\mathcal{X}(a) \cap \mathcal{X}(b) \ne\phi$, or such that $\mathbb{R}(a) \cap \mathbb{R}(b) \ne \phi$, then we have $\mathbb{R}(a) = \mathbb{R}(b)$ and $\mathcal{X}(a) = \mathcal{X}(b)$.
• We have $\bigcup_{a \in \mathbb{A}} \mathbb{R}(a) = \mathbb{A}$ and $\bigcup_{a \in \mathbb{A}} \mathcal{X}(a) = \mathbb{R}$.

So given an equivalence relation $\mathbb{R}$ we may define:

$$\mathcal{X}(\mathbb{R}) = \{ \mathbb{R}(a): a \in \mathbb{A}\} \subset \mathcal{P}(\mathbb{A}).$$

Then we have shown that if $\mathbb{B} \in \mathcal{X}(\mathbb{R})$, then $\mathbb{B}$ is non-empty.
Also we have shown that if $\mathbb{B}$ and $\mathbb{C}$ are distinct elements of $\mathcal{X}(\mathbb{R})$ then $\mathbb{B}\cap \mathbb{C} = \phi$.
Finally we have the formulas:

$$\bigcup_{\mathbb{B}\in \mathcal{X}(\mathbb{R})}\mathbb{B}= \mathb... ...\mathbb{B}\in \mathcal{X}(\mathbb{R})}\mathbb{B}\times \mathbb{B}= \mathbb{R}.$$

If $\mathbb{A}$ is a non-empty set a partition of $\mathbb{A}$ is a subset $\mathcal{X}$ of $\mathcal{P}(\mathbb{A})$, such that:

• If $\mathbb{B}$ and $\mathbb{C}$ are distinct elements of $\mathcal{X}$, then $\mathbb{B}\cap \mathbb{C} = \phi$.
• $\bigcup_{\mathbb{B} \in \mathcal{X}} = \mathbb{A}$.
• Each element $\mathbb{B}$ of $\mathcal{X}$ is non-empty.

If $\mathbb{R}$ is an equivalence relation on $\mathbb{A}$, then we have shown above that $\mathcal{X}(\mathbb{R}) = \{ \mathbb{R}(a): a \in \mathbb{A}\}$ is a partition of $\mathbb{A}$.

Conversely, given a partition $\mathcal{X}$ of $\mathbb{A}$, define a relation $\mathbb{R}(\mathcal{X})$ on $\mathbb{A}$ by the formula:

$$\mathbb{R}(\mathcal{X}) = \bigcup_{\mathbb{B}\in \mathcal{X}}\mathbb{B}\times \mathbb{B}.$$

Then $\mathbb{R}(\mathcal{X})$ is an equivalence relation.

The main theorem is then:

• For any partition $\mathcal{X}$ of a set $\mathbb{A}$, we have: $\mathcal{X}(\mathbb{R}(\mathcal{X})) = \mathcal{X}$.
• For any equivalence relation $\mathbb{R}$ on a set $\mathbb{A}$, we have: $\mathbb{R}(\mathcal{X}(\mathbb{R})) = \mathbb{R}$.