1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
---
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>
|
