---
tags: logic, category theory, stone duality
---

$\newcommand{\op}{^{op}}$

# A Short Introduction to Stone Duality (Category Theory)

[up](https://hackmd.io/@alexhkurz/S1W8SC0Tc)

(under construction)

Our aim is to extend the duality between finite sets and finite Boolean algebras to all Boolean algebras. This will happen in the part on *Topological Duality*.

But before we go there, it makes sense to better understand the finite duality from the point of view of category theory, universal algebra, and logic.

The methods we learn on the way will also apply to the general case (and many other problems in mathematics), so this is a good opportunity.

## Category Theoretic Duality

I will only give some of the basic definitions and indicate how they fit into our story.

### Categories, Functors, Natural Transformations, Equivalence

A **category** $\cal A$ consists of a collection of 'objects' and for all objects $A,B\in \cal A$ a set $\cal A(A,B)$ of 'arrows'. We write $f:A\to B$ for $f\in\cal A(A,B)$. For all $A\in\cal A$ there is an 'identity' arrow $id_A:A\to A$ and for all $A,B,C$ there is a 'composition' operation $\circ_{ABC}:{\cal A}(B,C)\times {\cal A}(A,B)\to {\cal A}(A,C)$. We write $f\circ g=h$ for $\circ_{ABC}(f,g)=h$. The axioms are for all $h:A\to B$
\begin{gather*}
h\circ id_A = h = id_B\circ h
\end{gather*}
and for all $f:C\to D, g:B\to C$, $h:A\to B$
\begin{gather*}
(f\circ g)\circ h = f\circ (g\circ h)
\end{gather*}

**Remark:** Note that identity arrows are in one-to-one correspondence with objects. It should therefore be no surporse that instead of the above two-sorted definition (one sort for objects, another sort for arrows), one can also give an equivalent one-sorted definition in which there are only arrows and no objects. This is important to bring home the idea that in category theory it is all about arrows, not objects. On the other hand, the one-sorted definition is also somewhat misleading. The reason is that more often than not, a construction on a category is already determined by what it is doing on objects. In fact, much of the power of category theory comes from this. For an example of how to make this precise, see the proof of the Yoneda lemma below.

**Example:** The category $Set$ of sets and functions. The category $\sf BA$ of Boolean algebras. The category $Set_\omega$ of finite sets and the the category ${\sf BA}_\omega$ of finite Boolean algebras.

**Exercise:** Make a list of categories.

The **dual** $\mathcal C\op$ of the category $\mathcal C$ has the same objects as $\mathcal C$ and $\mathcal C\op(A,B)=\mathcal C(B,A)$. Given $f:A\to B$ in $\mathcal C$ we write $f\op$ to denote $f:B\to A$ in $\mathcal C\op$. Identities and composition in $\mathcal C\op$ are defined as in $\mathcal C$.

An arrow $f:X\to Y$ is an **isomorphism**, or **iso**, if there is $g:Y\to X$ such that $f\circ g = id_Y$ and $g\circ f = id_X$.

Let $\cal A, \cal B$ be two categories. A **functor** $F:\cal A\to\cal B$ is a function from the objects of $\cal A$ to the objects of $\cal B$ and, for each pair $A,A'$ of objects of $\cal A$ a function $F_{AA'}:{\cal A}(A,A')\to{\cal B}(FA,FA')$ that preserves identities and composition.

**Example:** There is category where the objects are the categories and the arrows are the functors.

A **contravariant functor** $\mathcal A\to \mathcal B$ is a functor $\mathcal A\op\to \mathcal B$ or, equivalently, a funtor $\mathcal A\to \mathcal B\op$.

**Exercise:** Show that the finite duality theorem gives rise to contravariant functors $P:Set_\omega\to\sf BA_\omega$ and $S:{\sf BA}_\omega\to Set_\omega$.

**Exercise:** Show that for all sets $X$ there is an iso $X\cong SPX$. Show that for all BAs $B$ there is an iso $B\cong PSB$.

We are now almost ready to reformulate our finite duality theorem by saying that the categories $Set\op_\omega$ and $\sf BA_\omega$ are *equivalent*. But we first need to define natural transformations.

Let $F,G:\cal A\to\cal B$. A **natural transformation** $\tau:F\to G$ is a family $\tau_A:FA\to GA$ satisfying $Gf\circ \tau_{A} = \tau_{A'}\circ Ff$ for all $f:A\to A'$.

To understand the notion of natural transformation, I put together some exercises in the next section.

**Example:** Given categories $\cal A, \cal B$, there is a category $[\cal A, \cal B]$ where the objects are the functors $A\to\cal B$ and the arrows are natural transformations. Categories $[\cal A, \cal B]$ are called **functor categories**.

A natural transformation is called a **natural isomorphism** if it is an iso in its functor category.

Two categories $\mathcal A,\mathcal B$ are **equivalent** if there are funtors $F:\mathcal A\to \mathcal B$ and $G:\mathcal B\to\mathcal A$ as well as natural isomorphisms $Id_\mathcal A\cong GF$ and $Id_\mathcal B\cong FG$.

**Example:** The categories $Set_\omega\op$ and $\sf BA_\omega$ are equivalent.

## Examples of Natural Transformations

A good way to understand how naturality works and why naturality is a powerful notion is to work through some exercises such as the following.

**Exercise:** Let $Id$ be the identity functor on $Set$. Show that there is only one natural transformation $Id\to Id$.

**Exercise:** Find a category other than $Set$ for which there are two distinct natural transformations $Id\to Id$.

**Exercise:** Describe all natural transformations $Id\times Id\times Id \to Id\times Id$, where $Id:Set\to Set$ is again the identity functor.

**Exercise:** Define a functor $Set\to Set$ that is defined on objects as $X\mapsto A\times X$. How many natural transformations $A\times X\to B\times X$ are there?

**Exercise:** Define a functor $Set\to Set$ that is defined on objects as $X\mapsto X^A$ where $X^A$ is the set of functions $A\to X$. How many natural transformations $X^B\to X^A$ are there?

## Yoneda Lemma

Category theory is sometimes used as a language to organize mathematical results from a wide range of areas. But category theory proper is the study of categories as mathematical objects in their own right. The first important result is the Yoneda lemma.

**Lemma:** Let $\mathcal C$ be a category and $F:\mathcal C\to Set$ a functor. Then natural transformations $\mathcal C(A,-)\to F$ are in bijective correspondence with elements of $FA$, which we also write as
$${\sf Nat}(\mathcal C(A,-), F)\cong FA$$

## Adjunctions on Preorders

A preorder is a reflexive and transitive relation $R\subseteq X\times X$ on a set $X$. Preorders can be understood as categories. Since in preorders "all diagrams commute", category theoretic notions simplify. We are going to define adjunctions first for preorders.

Let $\mathcal A$ and $\mathcal B$ be two preorders and $L:\mathcal A\to\mathcal B$ and $R:\mathcal B\to \mathcal A$ be two monotone functions. Then we say that $L$ is the **left-adjoint** of $R$ and $R$ is the **right-adjoint** of $L$ and write $L\dashv R$ iff
$$LA\le B \ \Leftrightarrow \ A\le RB$$
for all $A\in\mathcal A$ and all $B\in\mathcal B$.

All of the following will generalize from preorders to categories.

**Proposition:** $L:\mathcal A\to\mathcal B$ and $R:\mathcal B\to \mathcal A$ be two monotone functions
- $L\dashv R$ iff $A\le RLA$ and ($A\le RB\Rightarrow LA\le B$) for all $A\in\mathcal A$,$B\in\mathcal B$.
- $L\dashv R$ iff $LRB\le B$ and ($LA\le B\Rightarrow A\le RB$) for all $A\in\mathcal A$,$B\in\mathcal B$.
- $L\dashv R$ iff $A\le RLA$ and $LRB\le B$ for all $A\in\mathcal A$,$B\in\mathcal B$.
- $L\dashv R$ iff $LRL=L$ and $RLR=R$.
- $L\dashv R$ iff $LA=\bigwedge\{B\mid A\le RB\}$ for all $A\in\mathcal A$.
- $L\dashv R$ iff $RB=\bigvee\{A\mid LA\le B\}$ for all $B\in\mathcal B$.
- $L\dashv R$ only if $L$ preserves all joins and $R$ preserves all meets.
- $L$ has a right-adjoint iff $\mathcal A$ has and $L$ preserves all joins of the form $\bigvee\{A\mid LA\le B\}$.
- $R$ has a left-adjoint iff $\mathcal B$ has and $R$ preserves all meets of the form $\bigwedge\{B\mid A\le RB\}$.

In particular, if $\mathcal A$ and $\mathcal B$ are complete, that is, have all joins and meets, then preserving all joins is equivalent to having a right adjoint and preserving all meets is equivalent to having a left-adjoint.

**Corollary:** If $L$ is a left-adjoint of $R:\cal B\to \cal A$, then $L$ is uniquely determined up to iso. If $\cal B$ is a poset, then $L$ is uniquely determined.

Because of $L\dashv R\ \Rightarrow \ R\op\dashv L\op$ all statements about adjunctions dualize. For example, the dual of the corollary above is that right-adjoints are determined up to iso.

## Adjunctions on Categories

### Definitions

Let $\mathcal A$ and $\mathcal B$ be two categories and $L:\mathcal A\to\mathcal B$ and $R:\mathcal B\to \mathcal A$ be two functors. Then we say that $L$ is the **left-adjoint** of $R$ and $R$ is the **right-adjoint** of $L$ and write $L\dashv R$ if there is an isomorphism
$${\cal B}(LA, B) \ \cong \ {\cal A}(A, RB)$$
natural in $A\in\mathcal A$ and $B\in\mathcal B$.

**Theorem:** The data of an adjunction can be given equivalently in any of the following ways.
- For all $A\in\cal A$ an arrow $\eta_A:A\to RLA$, called the unit, such that for all $f:A\to RB$ there is a unique $f^\sharp:LA\to B$ such that $Rf^\sharp\circ\eta_A = f$.
- For all $B\in\cal B$ an arrow $\epsilon_B:LRB\to B$, called the counit, such that for all $g:LA\to B$ there is a unique $g^\flat:A\to RB$ such that $\epsilon_B\circ Lg^\flat = g$.
- Two natural transformations $\eta: Id\to RL$ (the unit) and $\epsilon:LR\to Id$ such that $\epsilon L\circ L\eta= Id$ and $R\epsilon\circ\eta R= Id$.

### Examples

**Example:** (For programmers who have written an interpreter for a simple programming language which has variables and arithmetic expressions.)
- $L$ is given by the context-free grammar defining the language of expressions: If $A$ is a set of variables, then $LA$ is the set of expressions that one can build from the variables and the rules of the grammar. $\cal A$ is the category of sets. [^L]
- $\cal B$ is the category of all algebras that are able to interpret the operations of the grammar. For example, if the grammar has $+,-,*,0,1$ then the following algebras are in $\cal B$.
- the natural numbers $\mathbb N$,
- the integers $\mathbb Z$,
- the rationals $\mathbb Q$,
- the real numbers $\mathbb R$.
- To continue this example let us take $B=\mathbb Z$.
- $f^\sharp:LA\to \mathbb Z$ evaluates expressions as numbers (given an interpretation $f$ of the variables).
- What is $R:\cal B\to\cal A$ doing? [^R]
- What is $\eta_A: A\to RLA$ doing? [^eta]
- In what sense is $LA$ an algebra? What are the operations on $LA$? [^LA]

[^L]:In this context, $LA$ is called the free algebra over $A$ and thte traditional notation is ten $F$ instead of $L$.

[^R]: $R$ is known as the forgetful functor or underlying functor and, in this context, usually denoted by $U$.

[^eta]: $\eta$ is often called the insertion of variables.

[^LA]: $LA$ is sometimes called the term algebra (with "term" here being synonym with "expression").

The important lesson from the previous example is that $f^\sharp$ is defined by recursion (=induction) with $f$ providing the base case. [^recursion]

[^recursion]: Recursion on what? In the example it is the grammar that defines the language of expressions. This can be formalized using category theory with the notion of an algebra for a functor and the notion of a free monad over an endofunctor. Maybe we do this some other time.

**Example:** (Similar example for mathematicians.) Let $\cal A$ be the category of sets and $\cal B$ be the category of rings (one can also take other algebraic structures such as monoids, groups, Boolean algebras, etc). Then $LA$ is known as the free ring over $A$. **Exercise:** Show that if $A$ is a one element set then $LA$ is $\mathbb Z$. **Exercise:** If $\cal B$ is the category of fields and $R:\cal B\to \cal A$ is the obvious forgetful functor, then $R$ does not have a left adjoint. [^fields]

[^fields]: The interesting question is here: Why does it work for rings but not for fields?

### Results

Here are some basic results on adjoints.

**Proposition:** Adjoints are determined up to unique isomorphism.

**Proposition:** Adjoints compose.

**More results:** (Not all of the terminology below has been explained in these notes.)
- Left adjoints preserve colimits (and, by duality, right adjoints preserve limits).
- A category that is both complete and cocomplete is a preorder.
- If $R$ preserves limits and is determined by a small subcategory, then $R$ is a right adjoint.
- Let $\cal A\to \cal B$ be fully faithful and have a left adjoint. Then $\cal A$ is complete/cocomplete if $\cal B$ is.