Warning 4.4.6.1.3 (01JS): Free Completion Is Not an Idempotent Operation

4.4.6 Powersets as Free Completions

Let $X$ be a set.

Proposition 4.4.6.1.1 ▶ Powersets as Free Completions: Universal Property

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

•
The powerset of $X$ together with reverse inclusion $\mathcal{P}(X)^{\mathsf{op}}=(\mathcal{P}(X),\supset )$ 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:

(★)

•
An inflattice $(Y,\preceq )$;
•
A function $f\colon X\to Y$;

\[ (\mathcal{P}(X),\supset )\overset {\exists !}{\to }(Y,\preceq ) \]

Proof of Proposition 4.4.6.1.1.

This is a rephrasing of Proposition 4.4.6.1.2, which we prove below.¹

¹Here we only remark that the unique morphism of inflattices in the statement is given by the right Kan extension $\operatorname {\mathrm{Ran}}_{\chi _{X}}(f)$ of $f$ along $\chi _{X}$.

Proposition 4.4.6.1.2 ▶ Powersets as Free Completions: Adjointness

We have an adjunction

witnessed by a bijection

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

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

•
The category $\mathsf{InfLat}$ is the category of inflattices of .
•
The map

\[ \chi ^{*}_{X} \colon \mathsf{InfLat}((\mathcal{P}(X),\supset ),(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 inflattices $f\colon \mathcal{P}(X)^{\mathsf{op}}\to Y$ to the composition

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

\[ \operatorname {\mathrm{Ran}}_{\chi _{X}} \colon \mathsf{Sets}(X,Y) \to \mathsf{InfLat}((\mathcal{P}(X),\supset ),(Y,\preceq )) \]

witnessing the above bijection is given by sending a function $f\colon X\to Y$ to its right 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{Ran}}_{\chi _{X}}(f)$ can be explicitly computed by

\begin{align*} [\operatorname {\mathrm{Ran}}_{\chi _{X}}(f)](U) & = \int _{x\in X}\chi _{\mathcal{P}(X)^{\mathsf{op}}}(\chi _{x},U)\pitchfork f(x)\\ & = \int _{x\in X}\chi _{\mathcal{P}(X)}(U,\chi _{x})\pitchfork f(x)\\ & = \int _{x\in X}\chi _{U}(x)\pitchfork f(x)\\ & = \bigwedge _{x\in X}\chi _{U}(x)\pitchfork f(x)\\ & = \left(\bigwedge _{x\in U}\chi _{U}(x)\pitchfork f(x)\right)\wedge \left(\bigwedge _{x\in U^{\textsf{c}}}\chi _{U}(x)\pitchfork f(x)\right)\\ & = \left(\bigwedge _{x\in U}f(x)\right)\wedge \left(\bigwedge _{x\in U^{\textsf{c}}}\infty _{Y}\right)\\ & = \left(\bigwedge _{x\in U}f(x)\right)\wedge \infty _{Y}\\ & = \bigwedge _{x\in U}f(x) \end{align*}

for each $U\in \mathcal{P}(X)$, where:
- •
  We have used for the first equality.
- •
  We have used Proposition 4.5.5.1.1 for the second equality.
- •
  We have used for the third equality.
- •
  The symbol $\bigwedge $ denotes the meet in $(Y,\preceq )$.
- •
  The symbol $\pitchfork $ denotes the cotensor of an element of $Y$ by a truth value as in . In particular, we have
  
  \begin{align*} \mathsf{true}\pitchfork f(x) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}f(x),\\ \mathsf{false}\pitchfork f(x) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\infty _{Y}, \end{align*}
  
  where $\infty _{Y}$ is the top element of $(Y,\preceq )$.
In particular, when $(Y,\preceq _{Y})=(\mathcal{P}(B),\subset )$ for some set $B$, the Kan extension $\operatorname {\mathrm{Ran}}_{\chi _{X}}(f)$ is given by

\begin{align*} [\operatorname {\mathrm{Ran}}_{\chi _{X}}(f)](U) & = \bigwedge _{x\in U}f(x)\\ & = \bigcap _{x\in U}f(x) \end{align*}

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

Proof of Proposition 4.4.5.1.2.

Map I

We define a map

\[ \Phi _{X,Y}\colon \mathsf{InfLat}((\mathcal{P}(X),\supset ),(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{InfLat}((\mathcal{P}(X),\supset ),(Y,\preceq ))$.

Map II

We define a map

\[ \Psi _{X,Y}\colon \mathsf{Sets}(X,Y)\to \mathsf{InfLat}((\mathcal{P}(X),\supset ),(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{InfLat}((\mathcal{P}(X),\supset ),(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{Ran}}_{\chi _{X}}(f\circ \chi _{X})\\ \end{align*}

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

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

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

\begin{align*} \left[\operatorname {\mathrm{Ran}}_{\chi _{X}}(f\circ \chi _{X})\right](U) & = \bigwedge _{x\in U}f(\chi _{X}(x))\\ & = f\left(\bigwedge _{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 inflattices and hence preserves meets in $(\mathcal{P}(X),\supset )$ (i.e. joins in $(\mathcal{P}(X),\subset )$) 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{InfLat}((\mathcal{P}(X),\supset ),(Y,\preceq ))$, it follows that $\Psi _{X,Y}\circ \Phi _{X,Y}$ must be equal to the identity map $\operatorname {\mathrm{id}}_{\mathsf{InfLat}((\mathcal{P}(X),\supset ),(Y,\preceq ))}$ of $\mathsf{InfLat}((\mathcal{P}(X),\supset ),(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{Ran}}_{\chi _{X}}(f))\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\operatorname {\mathrm{Ran}}_{\chi _{X}}(f)\circ \chi _{X}\end{align*}

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

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

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

\begin{align*} [\operatorname {\mathrm{Ran}}_{\chi _{X}}(f)\circ \chi _{X}](x) & = \bigwedge _{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{InfLat}((\mathcal{P}(X'),\supset ),(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 cocontinuous morphism of posets

\[ 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{InfLat}((\mathcal{P}(X),\supset ),(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.

ゴ

Warning 4.4.6.1.3 ▶ Free Completion Is Not an Idempotent Operation

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

ゴ

Statistics Cite

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

•Email
•Discord

You can also use the contact form below: