Proposition 2.4.4.1.1 (01JJ): Adjointness of Powersets II

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`

We have an adjunction

witnessed by a bijection of sets

\[ \mathrm{Rel}\webleft (\text{Gr}\webleft (X\webright ),Y\webright ) \cong \mathsf{Sets}\webleft (X,\mathcal{P}\webleft (Y\webright )\webright ) \]

natural in $X\in \text{Obj}\webleft (\mathsf{Sets}\webright )$ and $Y\in \text{Obj}\webleft (\mathrm{Rel}\webright )$, where $\text{Gr}$ is the graph functor of Chapter 7: Constructions With Relations, Item 1 of Proposition 7.3.1.1.2 and $\mathcal{P}_{*}$ is the functor of Chapter 7: Constructions With Relations, Proposition 7.4.5.1.1.

We have

$\mathrm{Rel}\webleft (\text{Gr}\webleft (A\webright ),B\webright ) \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\rlap {\mathcal{P}\webleft (A\times B\webright )}\phantom{\mkern 375mu}$

$\phantom{\mathrm{Rel}\webleft (\text{Gr}\webleft (A\webright ),B\webright )} \cong \rlap {\mathsf{Sets}\webleft (A\times B,\{ \mathsf{t},\mathsf{f}\} \webright )}\phantom{\mkern 375mu}$

(by Item 2 of Proposition 2.5.1.1.4)

$\phantom{\mathrm{Rel}\webleft (\text{Gr}\webleft (A\webright ),B\webright )} \cong \rlap {\mathsf{Sets}\webleft (A,\mathsf{Sets}\webleft (B,\{ \mathsf{t},\mathsf{f}\} \webright )\webright )}\phantom{\mkern 375mu}$

(by Item 2 of Proposition 2.1.3.1.3)

$\phantom{\mathrm{Rel}\webleft (\text{Gr}\webleft (A\webright ),B\webright )} \cong \rlap {\mathsf{Sets}\webleft (A,\mathcal{P}\webleft (B\webright )\webright )}\phantom{\mkern 375mu}$

(by Item 2 of Proposition 2.5.1.1.4)

with all bijections natural in $A$, (where we are using Item 3 of Proposition 2.5.1.1.4). Explicitly, this isomorphism is given by sending a relation $R\colon \text{Gr}\webleft (A\webright )\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$ to the map $R^{\dagger }\colon A\to \mathcal{P}\webleft (B\webright )$ sending $a$ to the subset $R\webleft (a\webright )$ of $B$, as in Chapter 6: Relations, Definition 6.1.1.1.1.

Naturality in $B$ is then the statement that given a relation $R\colon B\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B'$, the diagram

commutes, which follows from Chapter 7: Constructions With Relations, Remark 7.4.1.1.2.