Seven Sketches

We are currently reading “Seven Sketches in Compositionality: An Invitation to Applied Category Theory”Brendan Fong and David I Spivak, “Seven Sketches in Compositionality: An Invitation to Applied Category Theory,” 2018, http://arxiv.org/abs/1803.05316.

and I’ll write some comments here. (The numbering in the printed book is different, we refer to the arXiv PDF.)

Ch. 1: Generative Effects: Orders and Adjunctions

Adjoints of the powerset functor

Example 1.117 speaks about the adjoints of the powerset functor. Given a function $f: A \to B$ between sets, we get a monotone map $f^*: \PP(B) \to \PP(A)$ that is the preimage (you may know this also as $f^{-1}$):More about the notation.

$$ f^*(B') = \{a \in A\,|\,f(a) \in B'\} $$

The book now presents two adjoints to this:

$$\xymatrix{
\PP(A)\ar@/_1.33pc/[d]_{f_!}\ar@/^1.33pc/[d]^{f_*}\\
\PP(B)\ar[u]|{\dashv \,f^*\, \dashv}
}$$

given by

$$\begin{aligned}
f_!(A') := &\, \{ b \,|\, \exists a \in A'. f(a) = b \}\\
f_*(A') := &\, \{ b \,|\, \forall a \in A. f(a) = b \implies a \in A' \}
\end{aligned}$$

We can imagine $f_!$say: $f$ lower shriek

as the function that returns all $b$ that occur in the image $f(A')$, and $f_*$ as the function that returns all $b$ that only occur in the image $f(A')$.

The preimage $f^*$ is called a pullback in the text:

$$\xymatrix{
f^*(B')\ \lhook\mkern-7mu \ar[r] \ar[d]_{\phi} & A \ar[d]^f \\
B'\ \lhook\mkern-7mu \ar[r] & B\\
}$$

Here $\phi$ is the restriction of $f$ to the subset $f^*(B')$.

Closure operators

Exercise 1.119:

$p \le (f \seq g)(p)$ follows directly from the definition of an adjunction.Remember, $f$ left adjoint to $g$ $\iff p\le g(f(p))$ and $f(g(q)) \le q$

Theorem: $( f \seq g \seq f \seq g )(p) \cong ( f \seq g )(p)$.
Proof:From https://en.wikipedia.org/wiki/Galois_connection#Properties

First, we show $(f\seq g\seq f)(p) = f(p)$ for all $p$: since the Galois connection yields $p \le (f\seq g)(p)$ and $f$ is monotonic, we get $f(p) \le (f\seq g\seq f)(p)$; but since $(g \seq f)(q) \le q$, we also get $(f\seq g\seq f)(p) \le f(p)$, thus $(f\seq g\seq f)(p) \cong f(p)$. Now applying $g$ on both sides yields the result.

Ch. 3: Functors, Natural Transformations, and Databases

We review the definition of a natural transformation $\alpha$:

$$\xymatrix{\mathscr{C}\ar@/^/[r]^{F}\ar@/_/[r]_{G}\ar@{}[r]|{\Downarrow\mathrlap{\alpha}} & \mathscr{D}}.$$

Definition 3.49: Let $\mathscr{C}$ and $\mathscr{D}$ be categories, and let $F, G : \mathscr{C} \to \mathscr{D}$ be functors. To specify a natural transformation $\alpha : F \Rightarrow G$, for each object $c \in \mathscr{C}$, one specifies a morphism $\alpha_c : F(c) \to G(c)$ in , called the $c$-component of $\alpha$.

These components must satisfy the following naturality condition: for every morphism $f : c \to d$ in $\cat{C}$, the following equation must hold:

$$F(f) \seq \alpha_d = \alpha_c \seq G(f).$$

Or, as a commutative diagram:

$$\xymatrix{
F(c) \ar[d]_{F(f)} \ar[r]^{\alpha_c} & G(c) \ar[d]^{G(f)} \\
F(d)               \ar[r]_{\alpha_d} & G(d)
}$$

So what happens is that a morphism $f \in \cat{C}$ is mapped to morphisms $F(f), G(f) \in \cat{D}$.