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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
|
---
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 an associative 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 an associative 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 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)$$
</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 an associative 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>
<div class="exercise">
Show that $\circ$ in $\ca{Pfn}$ is associative.
<div class="proof">
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}
$$
</div>
</div>
<div class="exercise">
Consider the category $\ca{Set_\bot}$ of pointed sets.
Show that $\ca{Set_\bot}$ and $\ca{Pfn}$ are "essentially the same" category.
<div class="proof">
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 \} \\
f & \mapsto \rest{f}{\left ( A - \{ \bot \} \right )}
\end{aligned}
$$
where $\rest{f}{\bar{A}}$ is total.
</div>
</div>
|
