---
title: Exercises in Category Theory — 1.2
published: 2016-02-02
tags: Category Theory
---

<div class="exercise">
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$.

 a) Verify that $\ca{Pno}$ is a category
 
     1. For every $A \in \ca{Pno}$ there exists $\idarr{(A, \alpha, b)}$
        <div class="proof">
        $\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
        </div>
        
     2. There exists a partial binary operation $\circ$ on the arrows of $\ca{Pno}$
        <div class="proof">
        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$$
        </div>
 
 b) Show that $(\N, \textrm{succ}, 0)$ is a $\ca{Pno}$-object
 
    <div class="proof">
    $\N$ is indeed a Set, $\textrm{succ}$ is indeed an unary function and $0$ is indeed an element of $\N$.
    </div>
    
 c) 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.
    
    <div class="proof">
    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$.
    </div>
</div>

<div class="exercise">
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}$

 1. For every $(A, a) \in \ca{SetD}$ there exists $\idarr{(A, a)}$
    <div class="proof">
    $\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
    </div>
    
 2. There exists a partial binary operation $\circ$ on the arrows of $\ca{SetD}$
    <div class="proof">
    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$$
    </div>
</div>

<div class="exercise">
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.

<div class="proof">
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}$.

 1. 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
    
 2. There exists a 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)$$
</div>
</div>

<div class="exercise">
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}$.

 1. For every $(S, \mathcal{O}_S) \in \ca{Top}$ there exists $\idarr{(S, \mathcal{O}_S)}$
    <div class="proof">
    $\id$ on $S$ is indeed a continuous map and thus a morphism
    </div>
    
 2. There exists a partial binary operation $\circ$ on the arrows of $\ca{Top}$
    <div class="proof">
    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$$
    </div>
</div>

<div class="exercise">
Show that $\End{\ca{C}}{A}$ is a monoid under composition, where $A$ is an object of a category $\ca{C}$.

<div class="proof">
$\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}$.
</div>

<div class="corollary">
Each monoid $(M, \cdot)$ is a category ([again](./1.1.md)).

<div class="proof">
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 m = m \ast m$.
</div>
</div>
</div>