Item 2 (00QJ) — The Clowder Project

8.1.5 The Converse of a Relation

Let $A$, $B$, and $C$ be sets and let $R\subset A\times B$ be a relation.

Definition 8.1.5.1.1 ▶ The Converse of a Relation

The converse 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}}}=}}\left\{ (b,a)\in B\times A\ \middle |\ \text{we have $a\sim _{R}b$}\right\} . \]
•
Viewing relations as functions $A\times B\to \{ \mathsf{true},\mathsf{false}\} $, we define

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

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

\[ R^{\dagger }(b)\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ a\in A\ \middle |\ b\in R(a)\right\} \]

for each $b\in B$.

¹Further Terminology: Also called the opposite of $R$ or the transpose of $R$.
²Note that $R^{\dagger }(b)=R^{-1}(\left\{ b\right\} )$.

Example 8.1.5.1.2 ▶ Examples of Converses of Relations

Here are some examples of converses of relations.

1.
Less Than Equal Signs. We have $(\mathord {\leq })^{\dagger }=\mathord {\geq }$.

2.
Greater Than Equal Signs. Dually to Item 1, we have $(\mathord {\geq })^{\dagger }=\mathord {\leq }$.

Functions. Let $f\colon A\to B$ be a function. We have

\begin{align*} \operatorname {\mathrm{Gr}}(f)^{\dagger } & = f^{-1},\\ (f^{-1})^{\dagger } & = \operatorname {\mathrm{Gr}}(f), \end{align*}

where $\operatorname {\mathrm{Gr}}(f)$ and $f^{-1}$ are the relations of Section 8.2.2 and Section 8.2.3.

Proposition 8.1.5.1.3 ▶ Properties of Converses of Relations

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.

1.
Functoriality. The assignment $R\mapsto R^{\dagger }$ defines a functor (i.e. morphism of posets)

\[ (-)^{\dagger }\colon \mathbf{Rel}(A,B)\to \mathbf{Rel}(B,A). \]

In other words, given relations $R,S\colon A\mathrel {\rightrightarrows \kern -9.5pt\mathrlap {|}\kern 6pt}B$, we have:
- (★)
2.
Interaction With Ranges and Domains. We have

\begin{align*} \operatorname {Dom}(R^{\dagger }) & = \mathrm{Im}(R),\\ \mathrm{Im}(R^{\dagger }) & = \operatorname {Dom}(R). \end{align*}
3.
Interaction With Composition. We have

\[ (S\mathbin {\diamond }R)^{\dagger } = R^{\dagger }\mathbin {\diamond }S^{\dagger }. \]
4.
Interaction With Apartness Composition. We have

\[ (S\mathbin {\square }R)^{\dagger } = R^{\dagger }\mathbin {\square }S^{\dagger }. \]
5.
Invertibility. We have

\[ (R^{\dagger })^{\dagger } = R. \]
6.
Identity I. We have

\[ \Delta ^{\dagger }_{A} = \Delta _{A}. \]
7.
Identity II. We have

\[ \nabla ^{\dagger }_{A} = \nabla _{A}. \]
8.
Interaction With Direct Images. We have

\[ R^{\dagger }_{!}=R^{-1}. \]
9.
Interaction With Coinverse Images. We have

\[ R^{\dagger }_{-1}=R_{*}. \]
10.
Interaction With Inverse Images. We have

\[ (R^{\dagger })^{-1}=R_{!}. \]
11.
Interaction With Codirect Images. We have

\[ R^{\dagger }_{*}=R_{-1}. \]

Proof of Proposition 8.1.5.1.3.

Item 1: Functoriality

We have

\begin{align*} R^{\dagger } & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ a\in A\ \middle |\ b\in R(a)\right\} \\ & \subset \left\{ a\in A\ \middle |\ b\in S(a)\right\} \\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}S^{\dagger }. \end{align*}

This finishes the proof.

Item 2: Interaction With Ranges and Domains

We have

\begin{align*} \operatorname {Dom}(R^{\dagger }) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ b\in B\ \middle |\ \text{$b\sim _{R^{\dagger }}a$ for some $a\in A$}\right\} \\ & = \left\{ b\in B\ \middle |\ \text{$a\sim _{R}b$ for some $a\in A$}\right\} \\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\mathrm{Im}(R) \end{align*}

and

\begin{align*} \mathrm{Im}(R^{\dagger }) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ a\in A\ \middle |\ \text{$b\sim _{R^{\dagger }}a$ for some $b\in B$}\right\} \\ & = \left\{ a\in A\ \middle |\ \text{$a\sim _{R}b$ for some $b\in B$}\right\} \\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\operatorname {Dom}(R). \end{align*}

This finishes the proof.

Item 3: Interaction With Composition

We have

\begin{align*} (S\mathbin {\diamond }R)^{\dagger } & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ (c,a)\in C\times A\ \middle |\ c\sim _{(S\mathbin {\diamond }R)^{\dagger }}a\right\} \\ & = \left\{ (c,a)\in C\times A\ \middle |\ a\sim _{S\mathbin {\diamond }R}c\right\} \\ & = \left\{ (c,a)\in C\times A\ \middle |\ \begin{aligned} & \text{there exists some $b\in B$ such}\\ & \text{that $a\sim _{R}b$ and $b\sim _{S}c$}\\ \end{aligned} \right\} \\ & = \left\{ (c,a)\in C\times A\ \middle |\ \begin{aligned} & \text{there exists some $b\in B$ such}\\ & \text{that $b\sim _{R^{\dagger }}a$ and $c\sim _{S^{\dagger }}b$}\\ \end{aligned} \right\} \\ & = \left\{ (c,a)\in C\times A\ \middle |\ \begin{aligned} & \text{there exists some $b\in B$ such}\\ & \text{that $c\sim _{S^{\dagger }}b$ and $b\sim _{R^{\dagger }}a$ }\\ \end{aligned} \right\} \\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}R^{\dagger }\mathbin {\diamond }S^{\dagger }. \end{align*}

This finishes the proof.

Item 4: Interaction With Apartness Composition

We have

\begin{align*} (S\mathbin {\square }R)^{\dagger } & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ (c,a)\in C\times A\ \middle |\ c\sim _{(S\mathbin {\square }R)^{\dagger }}a\right\} \\ & = \left\{ (c,a)\in C\times A\ \middle |\ a\sim _{S\mathbin {\square }R}c\right\} \\ & = \left\{ (c,a)\in C\times A\ \middle |\ \begin{aligned} & \text{for each $b\in B$, we have}\\ & \text{$a\sim _{R}b$ or $b\sim _{S}c$}\\ \end{aligned} \right\} \\ & = \left\{ (c,a)\in C\times A\ \middle |\ \begin{aligned} & \text{for each $b\in B$, we have}\\ & \text{$b\sim _{R^{\dagger }}a$ or $c\sim _{S^{\dagger }}b$}\\ \end{aligned} \right\} \\ & = \left\{ (c,a)\in C\times A\ \middle |\ \begin{aligned} & \text{for each $b\in B$, we have}\\ & \text{$c\sim _{S^{\dagger }}b$ or $b\sim _{R^{\dagger }}a$}\\ \end{aligned} \right\} \\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}R^{\dagger }\mathbin {\square }S^{\dagger }. \end{align*}

This finishes the proof.

Item 5: Invertibility

We have

\begin{align*} (R^{\dagger })^{\dagger } & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ (a,b)\in A\times B\ \middle |\ b\sim _{R^{\dagger }}a\right\} \\ & = \left\{ (a,b)\in A\times B\ \middle |\ a\sim _{R}b\right\} \\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}R. \end{align*}

This finishes the proof.

Item 6: Identity I

We have

\begin{align*} \Delta ^{\dagger }_{A} & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ (a,b)\in A\times A\ \middle |\ a\sim _{\Delta _{A}}b\right\} \\ & = \left\{ (a,b)\in A\times A\ \middle |\ a=b\right\} \\ & = \Delta _{A}. \end{align*}

This finishes the proof.

Item 7: Identity II

We have

\begin{align*} \nabla ^{\dagger }_{A} & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ (a,b)\in A\times A\ \middle |\ a\sim _{\nabla _{A}}b\right\} \\ & = \left\{ (a,b)\in A\times A\ \middle |\ a\neq b\right\} \\ & = \nabla _{A}. \end{align*}

This finishes the proof.

Item 8: Interaction With Direct Images

This is a repetition of Item 5 of Proposition 8.7.1.1.5 and is proved there.

Item 9: Interaction With Coinverse Images

This is a repetition of Item 5 of Proposition 8.7.2.1.5 and is proved there.

Item 10: Interaction With Inverse Images

This is a repetition of Item 5 of Proposition 8.7.3.1.4 and is proved there.

Item 11: Interaction With Codirect Images

This is a repetition of Item 5 of Item 5 and is proved there.