4.4.5 Powersets as Free Cocompletions

Let $X$ be a set.

The pair $(\mathcal{P}(X),\chi _{(-)})$ consisting of

  • The powerset $(\mathcal{P}(X),\subset )$ of $X$ of Definition 4.4.1.1.1;

  • The characteristic embedding $\chi _{(-)}\colon X\hookrightarrow \mathcal{P}(X)$ of $X$ into $\mathcal{P}(X)$ of Definition 4.5.4.1.1;

satisfies the following universal property:

  • (★)
  • Given another pair $(Y,f)$ consisting of
    • A suplattice $(Y,\preceq )$;

    • A function $f\colon X\to Y$;

    there exists a unique morphism of suplattices
    \[ (\mathcal{P}(X),\subset )\overset {\exists !}{\to }(Y,\preceq ) \]
    making the diagram
    commute.

This is a rephrasing of Proposition 4.4.5.1.2, which we prove below.1


  1. 1Here we only remark that the unique morphism of suplattices in the statement is given by the left Kan extension $\operatorname {\mathrm{Lan}}_{\chi _{X}}(f)$ of $f$ along $\chi _{X}$.

We have an adjunction

witnessed by a bijection

\[ \mathsf{SupLat}((\mathcal{P}(X),\subset ),(Y,\preceq )) \cong \mathsf{Sets}(X,Y), \]

natural in $X\in \operatorname {\mathrm{Obj}}(\mathsf{Sets})$ and $(Y,\preceq )\in \operatorname {\mathrm{Obj}}(\mathsf{SupLat})$, where:

  • The category $\mathsf{SupLat}$ is the category of suplattices of Unresolved reference.

  • The map

    \[ \chi ^{*}_{X} \colon \mathsf{SupLat}((\mathcal{P}(X),\subset ),(Y,\preceq )) \to \mathsf{Sets}(X,Y) \]

    witnessing the above bijection is defined by

    \[ \chi ^{*}_{X}(f) \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}f\circ \chi _{X}, \]

    i.e. by sending a morphism of suplattices $f\colon \mathcal{P}(X)\to Y$ to the composition

    \[ X \overset {\chi _{X}}{\hookrightarrow } \mathcal{P}(X) \overset {f}{\to } Y. \]
  • The map

    \[ \operatorname {\mathrm{Lan}}_{\chi _{X}} \colon \mathsf{Sets}(X,Y) \to \mathsf{SupLat}((\mathcal{P}(X),\subset ),(Y,\preceq )) \]

    witnessing the above bijection is given by sending a function $f\colon X\to Y$ to its left Kan extension along $\chi _{X}$,

    Moreover, invoking the bijection $\mathcal{P}(X)\cong \mathsf{Sets}(X,\{ \mathsf{t},\mathsf{f}\} )$ of Item 2 of Proposition 4.5.1.1.4, $\operatorname {\mathrm{Lan}}_{\chi _{X}}(f)$ can be explicitly computed by

    \begin{align*} [\operatorname {\mathrm{Lan}}_{\chi _{X}}(f)](U) & = \int ^{x\in X}\chi _{\mathcal{P}(X)}(\chi _{x},U)\odot f(x)\\ & = \int ^{x\in X}\chi _{U}(x)\odot f(x)\\ & = \bigvee _{x\in X}(\chi _{U}(x)\odot f(x))\\ & = \left(\bigvee _{x\in U}(\chi _{U}(x)\odot f(x))\right)\vee \left(\bigvee _{x\in U^{\textsf{c}}}(\chi _{U}(x)\odot f(x))\right)\\ & = \left(\bigvee _{x\in U}f(x)\right)\vee \left(\bigvee _{x\in U^{\textsf{c}}}\varnothing _{Y}\right)\\ & = \bigvee _{x\in U}f(x) \end{align*}

    for each $U\in \mathcal{P}(X)$, where:

    • We have used Unresolved reference for the first equality.

    • We have used Proposition 4.5.5.1.1 for the second equality.

    • We have used Unresolved reference for the third equality.

    • The symbol $\bigvee $ denotes the join in $(Y,\preceq )$.

    • The symbol $\odot $ denotes the tensor of an element of $Y$ by a truth value as in Unresolved reference. In particular, we have

      \begin{align*} \mathsf{true}\odot f(x) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}f(x),\\ \mathsf{false}\odot f(x) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\varnothing _{Y}, \end{align*}

      where $\varnothing _{Y}$ is the bottom element of $(Y,\preceq )$.

    In particular, when $(Y,\preceq _{Y})=(\mathcal{P}(B),\subset )$ for some set $B$, the Kan extension $\operatorname {\mathrm{Lan}}_{\chi _{X}}(f)$ is given by

    \begin{align*} [\operatorname {\mathrm{Lan}}_{\chi _{X}}(f)](U) & = \bigvee _{x\in U}f(x)\\ & = \bigcup _{x\in U}f(x) \end{align*}

    for each $U\in \mathcal{P}(X)$.

Map I
We define a map

\[ \Phi _{X,Y}\colon \mathsf{SupLat}((\mathcal{P}(X),\subset ),(Y,\preceq )) \to \mathsf{Sets}(X,Y) \]

as in the statement, i.e. by

\[ \Phi _{X,Y}(f)\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}f\circ \chi _{X} \]

for each $f\in \mathsf{SupLat}((\mathcal{P}(X),\subset ),(Y,\preceq ))$.

Map II
We define a map

\[ \Psi _{X,Y}\colon \mathsf{Sets}(X,Y)\to \mathsf{SupLat}((\mathcal{P}(X),\subset ),(Y,\preceq )) \]

as in the statement, i.e. by

for each $f\in \mathsf{Sets}(X,Y)$.

Invertibility I
We claim that

\[ \Psi _{X,Y}\circ \Phi _{X,Y}=\operatorname {\mathrm{id}}_{\mathsf{SupLat}((\mathcal{P}(X),\subset ),(Y,\preceq ))}. \]

We have

\begin{align*} [\Psi _{X,Y}\circ \Phi _{X,Y}](f) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\Psi _{X,Y}(\Phi _{X,Y}(f))\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\Psi _{X,Y}(f\circ \chi _{X})\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\operatorname {\mathrm{Lan}}_{\chi _{X}}(f\circ \chi _{X})\\ \end{align*}

for each $f\in \mathsf{SupLat}((\mathcal{P}(X),\subset ),(Y,\preceq ))$. We now claim that

\[ \operatorname {\mathrm{Lan}}_{\chi _{X}}(f\circ \chi _{X})=f \]

for each $f\in \mathsf{SupLat}((\mathcal{P}(X),\subset ),(Y,\preceq ))$. Indeed, we have

\begin{align*} \left[\operatorname {\mathrm{Lan}}_{\chi _{X}}(f\circ \chi _{X})\right](U) & = \bigvee _{x\in U} f(\chi _{X}(x))\\ & = f\left(\bigvee _{x\in U}\chi _{X}(x)\right)\\ & = f\left(\bigcup _{x\in U}\left\{ x\right\} \right)\\ & = f(U)\end{align*}

for each $U\in \mathcal{P}(X)$, where we have used that $f$ is a morphism of suplattices and hence preserves joins for the second equality. This proves our claim. Since we have shown that

\[ [\Psi _{X,Y}\circ \Phi _{X,Y}](f)=f \]

for each $f\in \mathsf{SupLat}((\mathcal{P}(X),\subset ),(Y,\preceq ))$, it follows that $\Psi _{X,Y}\circ \Phi _{X,Y}$ must be equal to the identity map $\operatorname {\mathrm{id}}_{\mathsf{SupLat}((\mathcal{P}(X),\subset ),(Y,\preceq ))}$ of $\mathsf{SupLat}((\mathcal{P}(X),\subset ),(Y,\preceq ))$.

Invertibility II
We claim that

\[ \Phi _{X,Y}\circ \Psi _{X,Y}=\operatorname {\mathrm{id}}_{\mathsf{Sets}(X,Y)}. \]

We have

\begin{align*} [\Phi _{X,Y}\circ \Psi _{X,Y}](f) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\Phi _{X,Y}(\Psi _{X,Y}(f))\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\Phi _{X,Y}(\operatorname {\mathrm{Lan}}_{\chi _{X}}(f))\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\operatorname {\mathrm{Lan}}_{\chi _{X}}(f)\circ \chi _{X}\end{align*}

for each $f\in \mathsf{Sets}(X,Y)$. We now claim that

\[ \operatorname {\mathrm{Lan}}_{\chi _{X}}(f)\circ \chi _{X}=f \]

for each $f\in \mathsf{Sets}(X,Y)$. Indeed, we have

\begin{align*} [\operatorname {\mathrm{Lan}}_{\chi _{X}}(f)\circ \chi _{X}](x) & = \bigvee _{y\in \left\{ x\right\} }f(y)\\ & = f(x)\end{align*}

for each $x\in X$. This proves our claim. Since we have shown that

\[ [\Phi _{X,Y}\circ \Psi _{X,Y}](f)=f \]

for each $f\in \mathsf{Sets}(X,Y)$, it follows that $\Phi _{X,Y}\circ \Psi _{X,Y}$ must be equal to the identity map $\operatorname {\mathrm{id}}_{\mathsf{Sets}(X,Y)}$ of $\mathsf{Sets}(X,Y)$.

Naturality for $\Phi $, Part I
We need to show that, given a function $f\colon X\to X'$, the diagram
commutes. Indeed, we have

\begin{align*} [\Phi _{X,Y}\circ \mathcal{P}_{!}(f)^{*}](\xi ) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\Phi _{X,Y}(\mathcal{P}_{!}(f)^{*}(\xi ))\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\Phi _{X,Y}(\xi \circ f_{!})\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}(\xi \circ f_{!})\circ \chi _{X}\\ & = \xi \circ (f_{!}\circ \chi _{X})\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle (\dagger )}}{=}}}\xi \circ (\chi _{X'}\circ f)\\ & = (\xi \circ \chi _{X'})\circ f\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\Phi _{X',Y}(\xi )\circ f\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}f^{*}(\Phi _{X',Y}(\xi ))\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}[f^{*}\circ \Phi _{X',Y}](\xi ), \end{align*}

for each $\xi \in \mathsf{SupLat}((\mathcal{P}(X'),\subset ),(Y,\preceq ))$, where we have used Item 1 of Proposition 4.5.4.1.3 for the fifth equality above.

Naturality for $\Phi $, Part II
We need to show that, given a morphism of suplattices

\[ g\colon (Y,\preceq _{Y})\to (Y',\preceq _{Y'}), \]

the diagram

commutes. Indeed, we have

\begin{align*} [\Phi _{X,Y'}\circ g_{!}](\xi ) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\Phi _{X,Y'}(g_{!}(\xi ))\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\Phi _{X,Y'}(g\circ \xi )\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}(g\circ \xi )\circ \chi _{X}\\ & = g\circ (\xi \circ \chi _{X})\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}g\circ (\Phi _{X,Y}(\xi ))\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}g_{!}(\Phi _{X,Y}(\xi ))\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}[g_{!}\circ \Phi _{X,Y}](\xi ). \end{align*}

for each $\xi \in \mathsf{SupLat}((\mathcal{P}(X),\subset ),(Y,\preceq ))$.

Naturality for $\Psi $
Since $\Phi $ is natural in each argument and $\Phi $ is a componentwise inverse to $\Psi $ in each argument, it follows from Chapter 11: Categories, Item 2 of Proposition 11.9.7.1.2 that $\Psi $ is also natural in each argument.

Although the assignment $X\mapsto \mathcal{P}(X)$ is called the free cocompletion of $X$, it is not an idempotent operation, i.e. we have $\mathcal{P}(\mathcal{P}(X))\neq \mathcal{P}(X)$.


Noticed something off, or have any comments? Feel free to reach out!


You can also use the contact form below: