Exercises in Category Theory

Let $\ca{Pno}$ be the category of objects $(A, \alpha, a)$ where $A$ is a set, $\alpha : A \to A$ is a unary function, and $a \in A$ is a nominated element and morphisms $\arr{(A, \alpha, a)}{}{(B, \beta, b)}$ which are functions $f: A \to B$ preserving the structure such that $f \circ \alpha = \beta \circ f$ and $f(a) = b$ .

Verify that $\ca{Pno}$ is a category
1. For every $A \in \ca{Pno}$ there exists $\idarr{(A, \alpha, b)}$
  
  $\id$ on $A$ is indeed a function which preserves the structure ( $\id \circ \alpha = \alpha = \alpha \circ \id$ , $\id(a) = a$ ) and thus a morphism
2. There exists an associative partial binary operation $\circ$ on the arrows of $\ca{Pno}$
  
  Given three objects $(A, \alpha, a), (B, \beta, b), (C, \gamma, c)$ and two functions $g: A \to B$ and $f: B \to C$ the function $f \circ g: A \to C$ is an arrow in $\ca{Pno}$ , that is to say, it preserves structure: $(f \circ g) \circ \alpha = f \circ \beta \circ g = \gamma \circ (f \circ g)$ and $(f \circ g)(a) = f(b) = c$
Show that $(\N, \textrm{succ}, 0)$ is a $\ca{Pno}$ -object

$\N$ is indeed a Set, $\textrm{succ}$ is indeed an unary function and $0$ is indeed an element of $\N$ .
Show that for each $\ca{Pno}$ -object $(A, \alpha, a)$ there is an unique arrow $\arr{(\N, \textrm{succ}, 0)}{}{(A, \alpha, a)}$ and describe the behaviour of the carrying function.
We construct a carrying function recursively: $\begin{aligned} f : \N & \to A \\ 0 & \mapsto a \\ \textrm{succ}(x) & \mapsto \alpha(f(x)) \end{aligned}$ $f : \N \to A$ is indeed a morphism and thus an arrow.
Given two morphisms $f : \N \to A$ and $g : \N \to A$ we show that they are pointwise identical by induction over $\N$ :
- $f(0) = a = g(0)$
- Given $n \in \N$ : $(f \circ \mathrm{succ})(n) = (\alpha \circ f)(n) \overset{\text{ind.}}{=} (\alpha \circ g)(n) = (g \circ \mathrm{succ})(n)$
The morphism maps $\N$ to the transitive closure of $a$ under $\alpha$ .

Consider objects of form $(A, a)$ where $A$ is a set and $a \subseteq A$ . For two such objects a morphism $\arr{(A, a)}{f}{(B, b)}$ is a function $f : A \to B$ that respects the selected subsets: $\forall \alpha \in a \ldotp f(\alpha) \in b$

Show that such objects and morphisms form a category $\ca{SetD}$

For every $(A, a) \in \ca{SetD}$ there exists $\idarr{(A, a)}$

$\id$ on $A$ is indeed a function which respects the distinguished subset ( $\forall \alpha \in a \ldotp \id(\alpha) \in a$ ) and thus a morphism
There exists an associative partial binary operation $\circ$ on the arrows of $\ca{SetD}$

Given three objects $(A, a), (B, b), (C, c)$ and two functions $g: A \to B$ and $f: B \to C$ the function $f \circ g: A \to C$ is an arrow in $\ca{SetD}$ , that is to say, $\forall \alpha \in a$ : $(f \circ g)(\alpha) = f(b) = c$

Consider pairs $(A, \odot)$ where $A$ is a set and $\odot \subseteq A \times A$ is a binary relation on $A$ .

Show that these pairs are objects of a category finding a sensible notion of morphism.

For two such objects $(A, \odot), (B, \oplus)$ a morphism shall be a function $f : A \to B$ that respects the binary relation: $\forall a \odot a^\prime \ldotp f(a) \oplus f(a^\prime)$ We call the category comprised of such objects and arrows $\ca{RelH}$ .

For every $(A, \odot) \in \ca{RelH}$ there exists $\idarr{(A, \odot)}$

$\id$ on $A$ is indeed a function which respects the binary relation ( $\forall a \odot a^\prime \ldotp \id(a) \odot \id(a^\prime)$ ) and thus a morphism
There exists an associative partial binary operation $\circ$ on the arrows of $\ca{RelH}$
Given three objects $(A, \odot), (B, \oplus), (C, \otimes)$ and two functions $g: A \to B$ and $f: B \to C$ the function $f \circ g: A \to C$ is an arrow in $\ca{RelH}$ , that is to say, $\forall a \odot a^\prime$ : $a \odot a^\prime \implies g(a) \oplus g(a^\prime) \implies (g \circ f)(a) \otimes (g \circ f)(a^\prime)$

Topological spaces $(S, \mathcal{O}_S)$ , where $S$ is a Set and $\mathcal{O}_S \subseteq \powerset{S}$ , and continuous maps $f : S \to P$ , that is $\forall V \in \mathcal{O}_T \ldotp f^\leftarrow(V) \in \mathcal{O}_S$ , form a Category $\ca{Top}$ .

For every $(S, \mathcal{O}_S) \in \ca{Top}$ there exists $\idarr{(S, \mathcal{O}_S)}$

$\id$ on $S$ is indeed a continuous map and thus a morphism
There exists an associative partial binary operation $\circ$ on the arrows of $\ca{Top}$

Given three spaces $(S, \mathcal{O}_S), (T, \mathcal{O}_T), (U, \mathcal{O}_U)$ and two continuous maps $g : S \to T$ and $f : T \to U$ the map $f \circ g : S \to U$ is an arrow in $\ca{Top}$ , that is to say, it is contiuous: $V \in \mathcal{O}_U \implies g^\leftarrow(V) \in \mathcal{O}_T \implies (f \circ g)^\leftarrow(V) \in \mathcal{O}_S$

Show that $\End{\ca{C}}{A}$ is a monoid under composition, where $A$ is an object of a category $\ca{C}$ .

$\circ$ is associative and total on $\End{\ca{C}}{A}$ by the definition of category and $\End{\ca{C}}{A}$ is obviously closed under $\circ$ .

$\idarr{A}$ is required to exist by the definition of category and indeed an identity of $\circ$ on $\End{\ca{C}}{A}$ .

Each monoid $(M, \cdot)$ is a category (again).

We construct a category with exactly one object $\ast$ and associate to every element $m \in M$ an arrow $\arr{\ast}{m}{\ast}$ . We further define $m \circ n = m \cdot n$ .

Show that $\circ$ in $\ca{Pfn}$ is associative.

Consider the composition $g \circ f = \rest{g}{\bar{B}} \circ \rest{f}{\bar{\bar{A}}}$ of two partial functions $f : A \to B$ and $g : B \to C$ : $\begin{tikzcd} A \arrow[r, "f"] & B \arrow[r, "g"] & C \\ \bar{A} \arrow[u, hook] \arrow[ru, "\rest{f}{\bar{A}}" description] & \bar{B} \arrow[u, hook] \arrow[ru, "\rest{g}{\bar{B}}" description] & \\ \bar{\bar{A}} \arrow[u, hook] \arrow[ru, "\rest{f}{\bar{\bar{A}}}" description] & & \\ \end{tikzcd}$ where all restricted versions of $f$ , $g$ , and $h$ are total.

Extending the above to three partial functions $f : A \to B$ , $g : B \to C$ , and $h : C \to D$ : $\begin{aligned} (h \circ g) \circ f &= \rest{\left (\rest{h}{\bar{C}} \circ \rest{g}{\bar{\bar{B}}} \right )}{\bar{B}} \circ \rest{f}{\bar{\bar{A}}} \\ &= \rest{h}{\bar{C}} \circ \rest{g}{\bar{\bar{B}}} \circ \rest{f}{\bar{\bar{A}}} \\ &= \rest{h}{\bar{C}} \circ \rest{\left (\rest{g}{\bar{\bar{B}}} \circ \rest{f}{\bar{\bar{A}}} \right)}{\bar{\bar{A}}} \\ &= h \circ (g \circ f) \end{aligned}$

Consider the category $\ca{Set_\bot}$ of pointed sets.

Show that $\ca{Set_\bot}$ and $\ca{Pfn}$ are “essentially the same” category.

The idea is to identify the undefined parts of a partial functions image with $\bot$ : $\begin{aligned} \Phi : \ca{Pfn} & \to \ca{Set_\bot} \\ A & \mapsto A \cup \{ \bot_A \} \\ f\ \text{s.t.} \begin{tikzcd} A \arrow[r, "f"] & B \\ \bar{A} \arrow[u, hook] \arrow[ru, "\rest{f}{\bar{A}}" description] & \end{tikzcd} & \mapsto \begin{aligned} \Phi(f) : A \cup \{ \bot_A \} & \to B \cup \{ \bot_B \} \\ \bot_A & \mapsto \bot_B \\ a & \mapsto \begin{cases} f(a) & \quad x \in \bar{A} \\ \bot & \quad \text{else} \end{cases} \end{aligned} \\ \Phi^\leftarrow : \ca{Set_\bot} & \to \ca{Pfn} \\ A & \mapsto A - \{ \bot \} \\ \arr{A}{f}{B} & \mapsto \rest{f}{\left ( A - \{ \bot \} \right )} \end{aligned}$ where $\rest{f}{\bar{A}}$ is total.

Verify that for every monoid $R$ both $R\ca{Set}$ and $\ca{Set}R$ are categories of structured sets.

Since the two proofs are perfectly analogous we cover only the case $R\ca{Set}$ .

For every $R$ -Set $A \in R\ca{Set}$ there exists $\idarr{A}$

$\id$ on $A$ is indeed a structure preserving function ( $\forall a \in A, r \in R \ldotp \id(ra) = ra = r \id(a)$ ).
There exists an associative partial binary operation $\circ$ on the arrows of $R\ca{Set}$

Given three R-Sets $A$ , $B$ , and $C$ and two continuous maps $g : A \to B$ and $f : B \to C$ the map $f \circ g : A \to C$ is an arrow in $R\ca{Set}$ , that is to say $\forall a \in A, r \in R$ : $(f \circ g)(ra) = f(r g(a)) = r (f \circ g)(a)$

The format of the proof was chosen to demonstrate that $R\ca{Set}$ is indeed a structured set.

dirty-haskell.org: Exercises in Category Theory — 1.2

It's not crazy — it's having fun with types.