---

title: Chapter_3_Category_Functors
tags: Category, Functors
description: Category and Functors
type: pdf
slideOptions:
theme: white

---

###### tags: `Category` `Functors`

<br/>
<br/>

# **<div align="center">Chapter Three: Category and Functors</div>**

<div class="alert alert-info">Example text highlighted in blue background.</div>

<br/>
<br/>

### **3.1 Category**

<div class="alert alert-info">In chapter one, we defined the preorder as a **Ralation** on a pair of elements in a set. So the relation was defined inside a **set**. What about if we have objects that is not necessarily inside a set? Then we need a more abstract idea of **Relation**, we will call it **Morphism** from now on, because we are going to investigate more abstract ideas beyond the **set**, named **Category**</div>

<br/>

> **Definiton (Category)**
>> To specify a category C,
>> a). one specifies a collection of object, namely $OB(C)$;
>> b). for each two objects c,d, one specifies a set C(c,d), elements of which are called morphisms from c to d. We use expression $c\mapsto d$ as well.
>> c). for every object c, one specifies a morphism $id_c \in C(c, c)$, called the identity morphism on c;
>> d). for every three objects c, d, e, and morphisms $f\in C(c,d)\ and\ g\in C(d,e)$, one specifies a morphism $g\circ f\in C(c,e)$, called the composited morphism
>> All four constituents need to satisfy two conditions follows
>> (i). Unitality: any morphism $f\in C(c,d)$ composing with identity of c or d does nothing, i.e. $f\circ id_c = f = id_d\circ f$
>> (ii). Associativity: for any three morphisms f, g, and h, we have $h\circ (g\circ f) = (h\circ g)\circ f$

<br/>

The better way to understand the above definition is to compare it to the comcept of preorders we have learnt. we use the following table:

| Concept-Transfor | Category | Preorder |
| ----------------------- | -------------------- | ------------------------ |
| a). object | object in $OB(C)$ | Elements in set S |
| b). set of morphism | element in C(c,d) | Relations in $S\times S$ |
| c). Identity mophism | $id_c \in C(c,c)$ | Reflexity $x\le x$ |
| d). Composited morphism | $g\circ f\in C(c,e)$ | Transitivity |

The requirement of Unitality and Associativity is **similar** to a Monoid but **not the same**. The only difference is that for Monoid, the unit e is unique of the set in M; where as the identity morphisms in a C have many, i.e. for each object c in C, we will have a identity morphism $id_c$. But everything comes to fit if we only have one object, we say that **a Monoid is a Category with single object**.

<br/>

So we can see that a preorder is a special category. Suppose (P, ≤) is a preorder. The objects of P are precisely the elements of P; that is, Ob(P) = P. As for morphisms, P has **exactly one morphism** $p \mapsto q$ if p ≤ q and no morphisms p → q if $p \nleq q$. The fact that ≤ is reflexive ensures that every object has an identity, and the fact that ≤ is transitive ensures that morphisms can be composed. We call P the category corresponding to the preorder (P, ≤).

But the definition of Category is abstruct beyond the preorder, as it might have many morphisms between any two object, also, the structure of morphisms are similar to a monoid, where as the operation between preorders are meaningless in preorders.

We can also construct Category from Graph. For any graph G = (V, A, s, t), we can define a category Free(G), called the **free category** on G, whose objects are the vertices V and whose morphisms from c to d are the paths from c to d. The identity morphism on an object c is simply the trivial path at c. Composition is given by concatenation of paths. We call it **Free** as it does not have any restriction on whether any two parallel paths have to be same.

We will use the following digram to show that Preorders and Free Categoris are two ends of a spectrum.


<br/>

**Example 3.1.1**: Numbers represented by Free Categories

For 2, it has two objects v 1 and v 2 , and three morphisms: $id_{v1} : v_1 → v_1 , f_1 : v_1 → v_2 ,\ and\ id_{v2} : v_2 → v_2$ .
For 3, it has three objects and six morphisms, which are they?
We can also represent the set of Natural numbers as a single graph:

<br/>

**Example 3.1.2**: The category of set, denote **Set**.
> (i). Ob(**Set**) is the collection of all sets.
> (ii). **Set**(S, T) = $\{ f : S → T | f\ is\ a\ function\}$
> (iii). For each set S, the identity morphism is the function $id_S : S → S$ given by
$id_S(s) := s$ for each s ∈ S.
> (iv). The composition of morphisms is just the composition of functions
> The above constructions satisfy the Unitality and Associativity condition, so **Set** is indeed a category. If the sets are finite, then we have a category **FinSet** induced.

<br/>

**Example 3.1.3**: **Bool**-categories are categories, but **Cost**-categories are not, why?

<br/>

**Example 3.1.4**: The Category of Preorders. This is different from **a preorder as a Category**, this means **a category with all preorders as objects**, we denote it **PrO**. So what can specify $id_c$ as identity map for each preorder c; and the morphisms be the **monotone maps** between any two preorders. Clearly, composition of Monotonic maps are monotonic. This is indeed a category.

<br/>

**Example 3.1.5**

We can also construct a category of Graph, but we need to define a Graph Homomorphisms at the first stage

<br/>

> **Definiton (Graph Homomorphism)**
>> Let $G= (V, A, s, t)\ and\ G_{1} (V_1, A_1, s_1, t_1)$ be graphs. A graph homomorphism f from G to G_1, consists of two functions $f_0 : V \mapsto V_1\ and\ f_1 : A \mapsto A_1$ such that the two diagrams below commute:

> i.e. $s_1 \circ f_1 = f_0\circ s$ and $t_1\circ f_1 = f_0\circ t$

<br/>

Now we can construct a Category of Graphs, denote **Grph**:
>a). Objects are graphs
>b). morphisms are Graph Homomorphisms
>c). $Id_g$ are simply identity mappings for both V and A sets;
>d). Composition can be show as the diagram below, as two inner-diagram commute, thus the outer one also commute.


<br/>

**Example 3.1.6**: Let C be a category. Its opposite, denoted $C^{op}$ , is the category with the same objects, and for any two objects $c, d ∈ Ob(C)$, one has $C^{op}(c, d) := C(d, c)$. Identities and composition are as in C.

<br/>

In the next section, we will introduce the map between categories, namely **Functor**.

<br/>

> **Exercises 3.1**
>1. When we say 3 as a Free Category, what are the 6 morphisms there?
>2. For any Natural number n, treated as a Free Category as in example, identify number of morphisms in the Category with specific n.
>3. Check that Bool-Category is indeed a Category, but Cost-Category is not.
>4. For **PrO**, check that composition of two monotone maps is a morphism in **PrO**, i.e. monotonic.
>5. Prove that composition of Graph Homomorphism is indeed a Graph Homomophism, without using commutative diagram.

<br/>
<br/>

----

<br/>
<br/>

### **3.2 Functors and Natural Transformation**

<br/>
<br/>

Just like there are morphisms between sets, preorders, there is also a mapping between categories. it send object to object and morphisms to morphisms, all while preserving Identity and Composition

> **Definiton (Functors)**
>> Let C, D be categories. To define a functor $F: C\mapsto D$, one specify:
>> (i). for every object c, one specifies an object $F(c)$ in D;
>> (ii). for every morphism $f\in C(c,c_1)$, one specifies a morphism $F(f): D(F(c), F(c_1))$ in D.
>> The above constituents satisfy two properties:
>> (a). for each object c, $F(id_c) = id_{F(c)}$, i.e. preserving identities;
>> (b). for every three objects $c_1, c_2, c_3$, and two morphisms $f\in C(c_1, c_2),\ g\in C(c_2,c_3)$, we have $F(g\circ f) = F(g)\circ F(f)$, i.e. preserving composition

<br/>

We use a straightforward example below to start, with category **2** and **3** for Natural numbers:

**Example 3.2.1**


In the left-hand diagram, F sends every path to the trivial path, i.e. the identity on $n_1$; In the middle diagram $F(f_1) = g_1$ and the objects as labelled; in the right diagram, $F(f_1) = g_2\circ g_1$

<br/>

**Example 3.2.2**: Set-valued functors:
> Let C be a category, A functor $F: C\mapsto Set$ is known as a set-valued functor on C. For example $F: 1\mapsto Set$, this is a functor that maps a single-object category to **Set**. So for any set S, there is a functor $F_S : 1\mapsto Set$ such that $F_S(1) = S$

<br/>

**Example 3.2.3**: Another example of Set-valued functor
> Consider Category with one object z but two morphisms, i.e. identity mapping and another morphism called s with $s\circ s = s$. We can think of some example of data that would **fit** this Functor.
> (a). Z is the set of US citizens, and S sends each citizen to her or his president. The
president’s president is her- or him-self.
> (b). Z can also be a vector space, and S is a projection
> (c ). Recall from Chapter one that the Closure Operator $g\circ f$ composed by a pair of Galois Connection. Then Z can be any preorder, and s be the Closure operator.

<br/>

**Example 3.2.4**: **Mon** $\mapsto$ **Mon**

>We know previously that a Monoid is a category with single element. To be more precise, let's say $X = (M,e,\times)$ is a monoid, then a category C equipped with one object $\star$ and morphisms $C(\star,\star) = M$, $id_{\star} = e$, and $\times$ for composition in C. If there is another monoid Y form a category D, then monoid homomorphism from X to Y is a functor from C to D. For instance let $X = (\Bbb{Z},1,\times)$ and $Y=(\Bbb{B},True,AND)$.

<br/>

**Example 3.2.5**: Identity Functor
> Given any category C, we may define the identity functor $id_C : C → C$. we simply pick the identity mapping for both objects and morphisms. In particular, this choice of mappings preserves composition and identity in C.

<br/>

**Example 3.2.6**: The Category of Categories, **Cat**
> (i). Obj in **Cat** are category;
> (ii). Morphisms in **Cat** are functors;
> (iii). identity functor as shown in Example 3.2.5;
> (iv). It is easy to show that Composition of functors perserve identity and composition, thus it is a functor
> (v). Having all above construction, to show that **Cat** is indeed a category, one need to show the unitality and associativity of functor(i.e. morphism), which is also an exercise.

<br/>

**Example 3.2.7**: Graph Indexing Category

> Then a functor $G: GrIn\mapsto Set$ is the same thing as two sets G(Ar)), G(Ve) and two functions $G(src): G(Ar) \mapsto G(Ve)$ and $G(tgt): G(Ar) \mapsto G(Ve)$. This is precisely what is needed for a graph.

<br/>

<div class="alert alert-info">The **mage** of a functor have two component, object and morphisms. It is natually to think if there is any map between two functors that have some good mathematical feature. Here we will introduce so called **Natual Transformation**</div>

<br/>

> **Definiton (Natural Transformation)**
>> Let C, D be categories. and $F, G: C\mapsto D$ be two functors. We define a natural transformation $\alpha : F \Rightarrow G$ with one component and one underlying condition
>> Component: for each object c, one specify a morphism $\alpha_{c}: = D(F(c),G(c))$
>> naturality condition: for each morphism $C(c,c_1)$, we have $$\alpha_{c_1}\circ F(C(c,c_1)) = G(C(c, c_1))\circ \alpha_c$$. The Natural Condition can also be expressed as a commute digram below


<br/>

**Example 3.2.8**: Basic Intuition


Above digram demonstrate two functors $F,G: [1]\mapsto [2]$. We can see that $\alpha_0 = id_a$ and $\alpha_1 = y\circ x$ that make F(0) and G(1) commute, i.e. $\alpha_1\circ F(i) = G(i)\circ \alpha_0$

<br/>

**Lemma 3.1**
Let C, D be categories. and $F, G: C\mapsto D$ be two functors. For every object c, $\alpha_c: F(c)\mapsto G(c)$ is a morphism in D. Suppose we have a path from $c_0$ to $c_n$ equiped with morphism $f_1$ to $f_n$, and we have $\alpha_{c_i}\circ F(f_i) = G(f_i)\circ \alpha_{c_{i-1}}$ for every $1\le i\le n$, then the naturality square for the composition $f_n\circ \dots \circ f_1: c_0\mapsto c_n$ also commute.

**Proof**: see Example 3.1.5 $\blacksquare$

<br/>

With natural transformation, we can now level-up our abstraction a bit. We will be able to define a category of functors.

<br/>

> **Definiton (functor Category)**
>> Let C, D be categories. We denote by $D^C$ the category whose objects are functors $F : C\mapsto D$ and whose morphisms $D^C(F,G)$ are natural transformations $\alpha :F\mapsto G$. This category is called the functor category.

To check that this is exactly a category, we need to verify two things, a). There is an identity morphism for each functor F that **do nothing** when compose with other morphism; b).There is a composition of morphisms that preserve associativity. But wait, from the logic here, we need to firstly show composition and associativity firstly, in order to show unitality. Let's do that.

> b). Composition.
> - suppose we have $\alpha$ and $\beta$ be two natural transformation between two functors F and G, then for each object c, we define $(\beta \circ \alpha)_c = \beta_c\circ \alpha_c$. This is indeed a natural transformation by lemma 3.1. The associativity also follows from lemma 3.1.
>
> a). Unitality
> - Now for each functor F, define natual tansformation $id_F$, wich each c as object, have $(id_F)_c:= id_{F(c)} \in D(F(c),F(c))$, so for any morphism $f:c\mapsto c_1$, we have $id_{F(c_1)}\circ F(f) = F(f)\circ id_{F(c)}$, thus it is indeed a natural transformation. To show unitality, we only show the left-composition (or post-composing from other books). Suppose we have another natural tansformation $\beta$, then $\beta_c \circ (id_F)_c = \beta_c \circ id_{F(c)} =\beta_c$, as identity morphism of $F(c)$ follows by a morphism $F(c)\mapsto G(c)$ is exactly what the later morphism.

<br/>

<div class="alert alert-info">Recall that we have introduced Join and Meet in the first chapter. We will introduce generalised join and meet for Category in the next section. </div>

<br/>
<br/>

> **Exercises 3.2**
>1. From Example 3.2.1 draw all other Functors and show morphisms' mapping for each functor;
>2. From Example 3.2.4, show that monoid homomorphism between $X = (\Bbb{Z},1,\times)$ and $Y=(\Bbb{B},True,AND)$, by mapping odd numbers to True, is a Functor.
>3. From Example 3.2.5, show that identity functor indeed preserve identity and composition
>4. From Example 3.2.6, show that Composition of functors perserve identity and composition, thus it is a functor.
>5. From Example 3.2.6, show Unitality and Associativity of **Cat**.

<br/>
<br/>
____

<br/>
<br/>

### **3.3 Product, Coproduct, Limit and colimit**

<br/>

<div class="alert alert-info">We will firstly introduce product and coproduct through ideas of span and cospan.</div>

<br/>

> **Definiton (Product & Co-product)**
>> - Let C be category, and X, Y be objects in C. A **span** on X and Y consists of three constituents $(Z, p, q)$, where Z is an object in C, $p: Z\mapsto X$ and $q:Z\mapsto Y$ are morphisms.
>> a **product** of X and Y is $(X\times Y, \pi_X, \pi_Y)$, and for any other span (Z,p,q), there exist a unique morphism $t_{p,q}: Z\mapsto X\times Y$ such that, $\pi_X\circ t_{p,q} = p$ and $\pi_Y\circ t{p,q}=q$
>> - A **co-span** on X and Y consists of three constituents $(Z, i, j)$, where Z is an object in C, $i: X\mapsto Z$ and $j:Y\mapsto Z$ are morphisms.
>> a **co-product** of X and Y is a co-span $(X\sqcup Y, l_X, l_Y)$, and for any other co-span (Z,i,j), there exist a unique morphism $s_{i,j}: X\sqcup Y\mapsto Z$ such that, $s_{i,j} \circ l_X= i$ and $s_{i,j} \circ l_Y= j$

<br/>

Let's see some example!

**Example 3.3.1**
Considering two graph $G_1 = (V_1, A_1, s_1, t_1)$ and $G_2 = (V_2, A_2, s_2, t_2)$

- The product and co-product

<iframe class="quiver-embed" src="https://q.uiver.app/?q=WzAsMzAsWzAsMSwiR18xID0gIl0sWzEsMCwidiJdLFsxLDEsInciXSxbMSwyLCJ4Il0sWzMsMSwiR18yID0gIl0sWzQsMCwicSJdLFs0LDEsInIiXSxbNCwyLCJzIl0sWzQsMywidCJdLFswLDQsIkdfMSBcXHRpbWVzIEdfMiA9ICJdLFsxLDQsIih2LHEpIl0sWzIsNCwiKHYscikiXSxbMyw0LCIodixzKSJdLFs0LDQsIih2LHQpIl0sWzEsNSwiKHcscSkiXSxbMiw1LCIodyxyKSJdLFszLDUsIih3LHMpIl0sWzQsNSwiKHcsdCkiXSxbMSw2LCIoeCxxKSJdLFsyLDYsIih4LHIpIl0sWzMsNiwiKHgscykiXSxbNCw2LCIoeCx0KSJdLFswLDgsIkdfMSBcXHNxY3VwIEdfMiA9ICJdLFsxLDgsInYiXSxbMSw5LCJ3Il0sWzEsMTAsIngiXSxbMyw4LCJxIl0sWzMsOSwiciJdLFszLDEwLCJzIl0sWzMsMTEsInQiXSxbMSwyLCJmIiwyXSxbMiwzLCJnIiwyLHsiY3VydmUiOjF9XSxbMiwzLCJoIiwwLHsiY3VydmUiOi0xfV0sWzUsNiwiaSIsMl0sWzYsNywiaiIsMix7ImN1cnZlIjoxfV0sWzcsNiwiayIsMix7ImN1cnZlIjoxfV0sWzcsOCwibCIsMl0sWzEwLDE1LCIoZixpKSJdLFsxMSwxNl0sWzEyLDE1XSxbMTIsMTddLFsxNCwxOSwiIiwwLHsiY3VydmUiOjF9XSxbMTQsMTksIiIsMix7ImN1cnZlIjotMX1dLFsxNSwyMCwiIiwyLHsiY3VydmUiOjF9XSxbMTUsMjAsIiIsMix7ImN1cnZlIjotMX1dLFsxNiwxOSwiIiwyLHsiY3VydmUiOjF9XSxbMTYsMTksIiIsMix7ImN1cnZlIjotMX1dLFsxNiwyMSwiIiwwLHsiY3VydmUiOjF9XSxbMTYsMjEsIiIsMCx7ImN1cnZlIjotMX1dLFsyMywyNCwiZiIsMl0sWzI0LDI1LCJnIiwyLHsiY3VydmUiOjF9XSxbMjQsMjUsImgiLDAseyJjdXJ2ZSI6LTF9XSxbMjYsMjcsImkiLDJdLFsyNywyOCwiaiIsMix7ImN1cnZlIjoxfV0sWzI4LDI3LCJrIiwyLHsiY3VydmUiOjF9XSxbMjgsMjksImwiLDJdXQ==&embed" width="818" height="1584" style="border-radius: 8px; border: none; scale: 0.7; headwidth: 1"></iframe>

<br/>

**Example 3.3.2** : Product and coproduct in a preorder

If $P=(P,\le)$ is a preorder, what are products and co-products in P? For two element a and b:

- A product will be $a \ge a\times b \le b$, for any other $a \ge z \le b$ we have $z\le a\times b$, so a product in a preorder is exactly the meet.
- A co-product will be $a \le a\times b \ge b$, for any other $a\le z \ge b$ we have $a\times b \le z$, so a co-product in a preorder is exactly the join.

<div class="alert alert-info">So just like join and meet in a preorder, product and co-product of two objects in a category might not exist, or not unique, but if there are many, they are isomorphic.</div>

<br/>

**Example 3.3.3** : Arithmetics of Product and Co-product

We some time use $+$ to denote co-product, which pairing with $\times$ for some arithmetic understanding. We will have isomorphisms as below for categories:

- $\Bbb{A} + \Bbb{0} \cong \Bbb{A}$ and $\Bbb{A} \times \Bbb{0} \cong \Bbb{0}$
- $\Bbb{A} + \Bbb{B} \cong \Bbb{B} + \Bbb{A}$ and $\Bbb{A} \times \Bbb{B} \cong \Bbb{B} \times \Bbb{A}$
- $(\Bbb{A} + \Bbb{B}) + \Bbb{C} \cong \Bbb{A} + (\Bbb{B} + \Bbb{C})$ and $(\Bbb{A} \times \Bbb{B}) \times \Bbb{C} \cong \Bbb{A} \times (\Bbb{B} \times \Bbb{C})$
- $\Bbb{A} \times \Bbb{1} \cong \Bbb{A}$
- $\Bbb{A} \times (\Bbb{B} + \Bbb{C}) \cong \Bbb{A}\times \Bbb{B} + \Bbb{A}\times \Bbb{C}$

The prove for above isomorphism is beyond the scope of this note. How ever, one can check them with the $Bool$ preorder with $\times$ as **AND** , $+$ as **OR**. We will only show the last one here. Recall that the preorder in Bool is implication, so let $A, B, C \in \{True, False\}$, then we have
>>A AND (B OR C) = (A AND B) OR (A AND C)

<br/>
<br/>

<div class="alert alert-info">Now we move up a bit to more interesting concepts, left cone and right cone.</div>

<br/>

> **Definiton (Left & Right cone)**
>> Let I be category,
>> - The left-cone of I, denote $I^{\triangleleft}$, is defined as:
>>> $Ob(I^{\triangleleft}):= \{-\infty\} \sqcup Ob(I)$
>>> $Mor_{I^{\triangleleft}}(a,b) :=
>>> \begin{cases}
Mor_{I}(a,b) & if\ a,b\in Ob(I) \\
-\infty\mapsto b & if\ a=-\infty,\ b\in Ob(I) \\
id_{-\infty} & if\ a=b=-\infty \\
\phi & if\ a\in Ob(I), b=-\infty
\end{cases}$
>> - The right-cone of I, denote $I^{\triangleright}$, is defined as:
>>> $Ob(I^{\triangleright}):= \{\infty\} \sqcup Ob(I)$
>>> $Mor_{I^{\triangleright}}(a,b) :=
>>> \begin{cases}
Mor_{I}(a,b) & if\ a,b\in Ob(I) \\
b\mapsto \infty & if\ b=\infty,\ a\in Ob(I) \\
id_{\infty} & if\ a=b=\infty \\
\phi & if\ b\in Ob(I), a=\infty
\end{cases}$

<br/>

**Example 3.3.4** : n-leaf star schema

For a natural number $n\in \Bbb{N}$, we define n-leaf star schema to be a category $n^{\triangleleft}$, where n is the discrete category on n objects. $Star_0,\ Star_1,\ and\ Star_2$ can be drawn as:

<iframe class="quiver-embed" src="https://q.uiver.app/?q=WzAsOSxbMCwwLCJTdGFyXzAiXSxbMCwxLCItXFxpbmZ0eSJdLFsyLDAsIlN0YXJfMSJdLFsyLDEsIi1cXGluZnR5Il0sWzIsMiwiMSJdLFs0LDAsIlN0YXJfMiJdLFs0LDEsIi1cXGluZnR5Il0sWzMsMiwiMSJdLFs1LDIsIjIiXSxbMyw0LCJzXzEiLDJdLFs2LDcsInNfMSIsMl0sWzYsOCwic18yIl1d&embed" width="846" height="432" style="border-radius: 8px; border: none; scale: 0.7"></iframe>

<br/>

We can see that the object $-\infty \in Ob(I^{\triangleleft})$ is kind of special than other object, not because that it has morphism to all other object, but also those morphisms are unique per object! This is kind of Universal property in a category, we will formally define.

<br/>

> **Definiton (initial & terminal)**
>> Let C be category. An object $a\in Ob(C)$ is called **initial** if for all other object c, there exist an unique morphism $a \mapsto c$; An object $z\in Ob(C)$ is called **terminal** if for all other object c, there exist an unique morphism $c \mapsto z$.

**Example 3.3.5** : Now we can say that $-\infty$ is an initial in $I^{\triangleleft}$, where as $\infty$ is a terminal in $I^{\triangleright}$.

<br/>

The lemma below is kind of trivial

**Lemma 3.2** Two distinct initial(or terminal) are isomorphic.

**Proof**: Exercise.

<br/>

**Example 3.3.6** : For the category **Set**, the initial object is the empty set $\phi$, as there is only one morphism from $\phi \mapsto s$ for any $s \in Ob(Set)$; the terminal objects are those sets with only one element. And indeed all terminal objects in **Set** are isomorphic.

<br/>

**Example 3.3.7** : For the category **Mon**, the initial and terminal object is $\Bbb{1}$, i.e. the 1-object category with only identity morphism.

<br/>

<div class="alert alert-info">A careful reader might already realise the implicit connection between span, product, terminal and left-cone. We know that a product is a span, and it is also a terminal, but wait! If we are going to say that a span is a terminal, we must show that a span is an object of a category of spans! So firstly, can spans form a category? They are indeed connected by a conception called limit, which is the most famous mathematical idea in Analysis. We will finally define the conception of Limit and Co-limit for this section. However, to avoid unfriendly Mathematical abstract, we will start by using a example</div>

<br/>

#### Construction of Limit

Thinking of a category C demonstrated below:

<iframe class="quiver-embed" src="https://q.uiver.app/?q=WzAsNixbMSwxLCJCIl0sWzAsMSwiQSJdLFsyLDAsIlgiXSxbMiwyLCJZIl0sWzMsMSwiQyJdLFs0LDEsIkQiXSxbMSwyLCJhIiwwLHsiY3VydmUiOi0xfV0sWzAsMSwiZiIsMl0sWzAsMiwiYl8xIiwyXSxbMCwzLCJiXzIiXSxbNCwyLCJjXzEiXSxbNCwzLCJjXzIiLDJdLFs0LDUsImciXSxbNSwyLCJkXzEiLDIseyJjdXJ2ZSI6MX1dLFs1LDMsImRfMiIsMCx7ImN1cnZlIjotMX1dXQ==&embed" width="688" height="432" style="border-radius: 8px; border: none; scale: 0.7"></iframe>

We can see that for $X, Y \in Ob(C)$, there are three spans $(B,b_1,b_2),\ (C,c_1,c_2),\ and\ (D,d_1,d_2)$, Can these three spans form a category? Yes! They are all **Functors**, denote $C_{/S\circ i}$, where objects are functors $S: Star_2 \mapsto C$,(recall from Example 3.3.4 that Star_2 is a image of $\Bbb{2}^{\triangleleft}$ from a inclusion functor i). The identity Functor is trivial, we only need to show that g is a natrual transformation, but the diagram already show that they are commute!

Now if we remove B and its underlying morphisms, the category of spans only have two objects. In this case, D is the product of X and Y, and $(D,d_1,d_2)$ is the terminal object of $C_{/X}$.

<br/>

Now we formally give a definition of Limit as well as Co-limit.

<br/>

> **Definiton (Limit & Co-limit)**
>> Let C be category, I be a indexing category with left-cone
>> - I be a indexing category with left-cone $I^{\triangleleft}$ from a inclusion functor $i:I\mapsto I^{\triangleleft}$, then a spans category denote $C_{S\circ i/}$ whose objects and morphisms are:
>> a). $Ob(C_{/S\circ i}):= \{S: I^{\triangleleft}\mapsto C \}$
>> b). $Mor(S,S^1) :=\{\alpha : S\mapsto S^1 |\ \alpha \circ i = S\circ i\}$
>> The limit of $S\circ i$ is the terminal object in $C_{/S\circ i}$

>> - I be a indexing category with right-cone $I^{\triangleright}$ from a inclusion functor $i:I\mapsto I^{\triangleright}$, then a cospans category denote $C_{/S\circ i}$ whose objects and morphisms are:
>> a). $Ob(C_{S\circ i/}):= \{S: I^{\triangleright}\mapsto C \}$
>> b). $Mor(S,S^1) :=\{\alpha : S\mapsto S^1 |\ \alpha \circ i = S\circ i\}$
>> The colimit of $S\circ i$ is the initial object in $C_{S\circ i/}$

<br/>

**Example 3.3.8** : Terminal objects are limits where the indexing category is empty. Products are limit where the indexing category consist of two object with no arrows in between. Product with more than two objects, says n, the left-cone of indexing category would be $Star_n$.

**Example 3.3.9: Pullback**

Considering in Discrete Category **Set** with three object $A=\{1,2,3,4\}$, $B=\{a,b,c,d,e,f\}$, and $C=\{red, blue, black\}$, two morphisms $f:A\mapsto C$ and $g:B\mapsto C$ assign elements of two sets to different colors. So $A\rightarrow C \leftarrow B$ form a cospan. Its limit is known as a **pullback** $A\times_C B$, which directly assign cartisian product of $A \times B$ to the underlying color that agree with f and g. An illustration can be shown below:


> **Exercises 3.3**
>1. From Example 3.3.1 we only labeled one morphism of product, labelling the rest.
>2. From Example 3.3.3, Using preorder **Bool** as a category, verify all arithmetic properties.
>3. From Example 3.3.4, show $Star_3,\ Star_4,\ and\ Star_5$;
>4. Prove lemma 3.2;
>5. Prove that the Product of two objects are limit of $Star_2$

<br/>
<br/>

____

<br/>
<br/>

### **3.4 Ajunction**

<br/>
<br/>

We will close this chapter with the formalized **Galois Connection** that we learnt from the Chapter one. We will firstly recall the definition of Galois Connection:

> **Definiton (Galois connection)**
>> A Galois connection between preorders P and Q is a pair of monotone maps f : P → Q and g : Q → P such that $$f(p) \le q\ \ if\ and\ only\ if\ p \le g(q)$$
>> We say that f is the left adjoint and g is the right adjoint of the Galois connection

<br/>

Here are some steps we need to do to formalise this concept and level-up our abstraction

1. Change the Preorders P and Q to categories P and Q. As we discussed at the beginning of this chapter, this replacement should be trivial now.
2. The monotone map would be replaced by a functor between P and Q.(?why are we allowed to do this replacement? i.e. Is a monotone map satisfy the definition of a functor?);
3. The order $\le$ will be replaced simply by a **morphism**;
4. The "if and only if" would be replaced by a sign of isomorphism;
5. Finally we will call this **Adjunction**

<br/>

> **Definiton (Ajunction)**
>> An ajunction between two categories P and Q is a pair of functors F : P → Q and G : Q → P such that $$\Bbb{Q}(F(p),q\ )\ \cong\ \Bbb{P}(p, G(q))$$
>> We say that F is the left adjoint to G and G is the right adjoint to F.

<br/>

**Example 3.4.1: Galois Connection would be a natural example**

<br/>

**Example 3.4.2: Free Monoid and Set**

We can construct a special type of monoid, called **Free Monoid**, by having a set, with empty set as identity element and string concatanation as binary operation. One can check that this is a Monoid that satisfy both identity and associativety. Then we would have an adjunction as below

We will call the functor from Free Monoid to Set **forgetful** simply as it forget the construction from set to it; the same reasoning for the naming of the **Free** functor.

<br/>

**Example 3.4.3: Currying** (After the logician Haskell Curry)

Fix $B \in Ob(Set)$, define Adjuction $- \times B$ and $(-)^B$, where $-$ is a placeholder for any set. Then we have $$Set(A\times B, C)\cong Set(A, C^B)$$

Recall that $C^B$ denote for functors from B to C, for sets, it is simply functions. We can use an example with leting $A=B=C= \Bbb{R}$ to demonstrate the idea:

Once A morphism $\Bbb{R}\times \Bbb{R} \to \Bbb{R}$ defines a **Surface** in $\Bbb{R}^3$, any slice on A-axis defines a **Curve**, which is a function $B\to C$

<br/>

<div class="alert alert-info">We will continue to connect the idea of adjunction and Galois Connection. Recall that monotonic maps are composible, would functors be conposible? The answer is positive. One can check that composition of functors are indeed functor. (omitted as exercise.)

Then we have the following remark that would be matching the **Proposition 1.4**

</div>

<br/>

**Remark 3.1**

Given A, B, C are categories, with adjunctions $F: A\to B$, $G: B\to A$, and $F_1: B\to C$, $G_1: C\to B$. One has $$C(F_1F(a),c)\cong B(F(a),G_1(c))\cong A(a,GG_1(c))$$

<br/>

To Be finished ....

<br/>
<br/>