Subsection 7.3.11 (00QE): The Inverse of a Relation

Style	Class	Font	Theorem Environments
Style 1	`book`	Alegreya Sans	`tcbthm`
Style 2	`book`	Alegreya Sans	`amsthm`
Style 3	`book`	Arno*	`amsthm`
Style 4	`book`	Computer Modern	`amsthm`

The inverse of $R$¹ is the relation $\smash {R^{\dagger }}$ defined as follows:

Viewing relations as subsets, we define
\[ R^{\dagger } \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\webleft\{ \webleft (b,a\webright )\in B\times A\ \middle |\ \text{we have $b\sim _{R}a$}\webright\} . \]
Viewing relations as functions $A\times B\to \{ \mathsf{true},\mathsf{false}\} $, we define

\[ {\webleft [R^{\dagger }\webright ]}{}^{b}_{a} \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}R^{a}_{b} \]

for each $\webleft (b,a\webright )\in B\times A$.
Viewing relations as functions $A\to \mathcal{P}\webleft (B\webright )$, we define

\begin{align*} \webleft [R^{\dagger }\webright ]\webleft (b\webright ) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}R^{\dagger }\webleft (\webleft\{ b\webright\} \webright )\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\webleft\{ a\in A\ \middle |\ b\in R\webleft (a\webright )\webright\} \end{align*}

for each $b\in B$, where $R^{\dagger }\webleft (\webleft\{ b\webright\} \webright )$ is the fibre of $R$ over $\webleft\{ b\webright\} $.

¹Further Terminology: Also called the opposite of $R$, the transpose of $R$, or the converse of $R$.

Here are some examples of inverses of relations.

Less Than Equal Signs. We have $\webleft (\mathord {\leq }\webright )^{\dagger }=\mathord {\geq }$.
Greater Than Equal Signs. Dually to Item 1, we have $\webleft (\mathord {\geq }\webright )^{\dagger }=\mathord {\leq }$.
Functions. Let $f\colon A\to B$ be a function. We have
\begin{align*} \text{Gr}\webleft (f\webright )^{\dagger } & = f^{-1},\\ \webleft (f^{-1}\webright )^{\dagger } & = \text{Gr}\webleft (f\webright ). \end{align*}

Let $R\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$ and $S\colon B\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}C$ be relations.

Functoriality. The assignment $R\mapsto R^{\dagger }$ defines a functor (i.e. morphism of posets)
\[ \webleft (-\webright )^{\dagger }\colon \mathbf{Rel}\webleft (A,B\webright )\to \mathbf{Rel}\webleft (B,A\webright ). \]

In particular, given relations $R,S\colon A\mathrel {\rightrightarrows \kern -9.5pt\mathrlap {|}\kern 6pt}B$, we have:
- If $R\subset S$, then $R^{\dagger }\subset S^{\dagger }$.
Interaction With Ranges and Domains. We have
\begin{align*} \mathrm{dom}\webleft (R^{\dagger }\webright ) & = \mathrm{range}\webleft (R\webright ),\\ \mathrm{range}\webleft (R^{\dagger }\webright ) & = \mathrm{dom}\webleft (R\webright ). \end{align*}
Interaction With Composition I. We have
\[ \webleft (S\mathbin {\diamond }R\webright )^{\dagger } = R^{\dagger }\mathbin {\diamond }S^{\dagger }. \]
Interaction With Composition II. We have
\begin{align*} \chi _{B} & \subset R\mathbin {\diamond }R^{\dagger },\\ \chi _{A} & \subset R^{\dagger }\mathbin {\diamond }R. \end{align*}
Invertibility. We have
\[ \webleft (R^{\dagger }\webright )^{\dagger } = R. \]
Identity. We have
\[ \chi ^{\dagger }_{A} = \chi _{A}. \]

Item 1: Functoriality

Clear.

Item 2: Interaction With Ranges and Domains

Clear.

Item 3: Interaction With Composition I

Clear.

Item 4: Interaction With Composition II

Clear.

Item 5: Invertibility

Clear.

Item 6: Identity

Clear.

The Clowder Project

7.3.11 The Inverse of a Relation