CAT Theory，meow~

# The category of sets

# Isomorphism

# Commutative diagrams

We say this is a diagram of sets if each of $A,B,C$ is a set and each of $f,g,h$ is a function. We say this diagram commutes if $g\circ f=h$.

In this case we refer to it as a commutative triangle of sets. However, the statement here is not precise enough to be a definition.

If $g\circ f = i\circ h$, then we refer to it as a commutative square of sets.

To say that the diagram commutes would say that every approach gives the same result. (Each approach is a combination of functions).

# Ologs

Example:

We represent each type as a box containing a singular indefinite noun phrase…

The text in the box should:

• begin with the word “a” or “an”.
• refer to a distinction made and recognizable by the olog’s author.
• refer to a distinction for which instances can be documented.
• declare all variables in a compound structure.

---

We consider aspects as functions. for example:

we can say “a woman has an aspect of being a person”, and “a molecule has an aspect (where we call mass usually) of a positive real number.”

However, “a person has a child” is not a valid aspect, since there exists people who don’t have children.

Remark: since a father can have many children, so we write $a\; child\stackrel{has}{\rightarrow}a\;father$ instead of $a\;father\stackrel{has}{\rightarrow} a\;child$.

---

A path in an olog is a head-to-tail sequence of arrows. The number of arrows is the length of the path.

We all know that “the woman in parents is called mother” and “mother is the woman in parents” (though it sounds weird), so the two paths are equivalent, the triangle is commutative. And the checker-mark √ in the region is bounded by the two paths.

The following diagram does NOT commute:

# Products and coproducts

Now we can construct more examples of non-commutative diagrams:

We may write the unique function as $\langle f,g\rangle:A\rightarrow X\times Y$. And obviously, $\langle f,g\rangle(a)=(f(a),g(a))$.

Example:

$$\{a,b\}\sqcup \{a,c\}=\{i_1a,b,i_2a,c\}$$

We may write the unique functions as

$$\begin{cases}f\\g\end{cases}:X\sqcup Y\rightarrow A\\ \begin{cases}f\\g\end{cases}(m)=\begin{cases}f(x)&if\;m=i_1x\\g(y)&if\;m=i_2y\end{cases}$$

# Finite limits in Set

Proposition: Consider the diagram below:

where $B'\cong B\times_C C'$ is a pullback. Then there is an isomorphism $A\times_B B'\cong A\times_C C'$. Said another way,

$$A\times_B(B\times_C C')\cong A\times_C C'$$

Exercise: Consider the diagram on the left below, where both squares commute.

Let $W=X\times_Z Y$ and $W'=X'\times_Z Y'$, and form the diagram to the right. Use the universal property of fiber products to construct a map $W\rightarrow W'$ such that all squares commute.

Solution:

---

Let’s look at a example of span, which may be a little confusing but reveals the relationship between matrix plus and span.

Let $A$ and $B$ be sets and let $A\leftarrow R\rightarrow B$ be a span. By the universal property of products, we have a unique map $R\stackrel{p}{\rightarrow} A\times B$.

We make a matrix of natural numbers out of this data as follows. The set of rows is $A$, the set of columns is $B$. For elements $a\in A$ and $b\in B$, the $(a,b)$-entry is the cardinality of its preimage, $|p^{-1}(a,b)|$, i.e. the number of elements in $R$ that are sent by $p$ to $(a,b)$. For example, if $R=\{(1,1),(1,2),(2,1),(2,2)\}$ and $p(a,b)=(a,b)$, then we can make the matrix $\begin{pmatrix}1&1\\1&1\end{pmatrix}$.

Given two spans $A\leftarrow R\rightarrow B$ and $A\leftarrow R'\rightarrow B$, by the universal property of coproducts we have a unique span $A\leftarrow R\sqcup R'\rightarrow B$ making the diagram commute. The matrix corresponding to this new span will be the sum of the two matrices corresponding to span $R$ and $R'$.

---

# Finite colimits in Set

Example: $W=\{1,2\},X=\{0,1,2,3\},Y=\{0,1,2,3,4\}$ and $f(x)=x+1,g(x)=x$. Then

$$W\sqcup X\sqcup Y = \{1_W,2_W,0_X,1_X,2_X,3_X,0_Y,1_Y,2_Y,3_Y,4_Y\}$$

since we have

$$2_X=f(1_W)\sim 1_W\sim g(1_W)=1_Y\\ 3_X=f(2_W)\sim 2_W\sim g(2_W)=2_Y$$

So the fiber sum is:

$$(X\sqcup W\sqcup Y)/\sim\\ =\{\\ \{0_X\}\\ \{1_X\}\\ \{1_W,2_X,1_Y\}\\ \{2_W,3_X,2_Y\}\\ \{0_Y\}\\ \{3_Y\}\\ \{4_Y\}\\ \}$$

# Other notions

Notation: Sometimes we use $B^A:=Hom_{Set}(A,B)$ to denote the set of functions from $A$ to $B$.

Proposition(Currying). Let $A$ denote a set. For any sets $X,Y$ there is a bijection:

$$\phi:Hom_{Set}(X\times A,Y)\stackrel{\cong}{\rightarrow}Hom_{Set}(X,Y^A)$$

Proof: Suppose given $f:X\times A\rightarrow Y$, Define $\phi(f):X\rightarrow Y^A$ as follows:

• for any $x\in X$, let $\phi(f)(x):A\rightarrow Y$ as follows:
  • for any $a\in A$, let $\phi(f)(x)(a):=f(x,a)$.

we now construct inverse, $\psi:Hom_{Set}(X,Y^A)\rightarrow Hom_{Set}(X\times A,Y)$. Suppose given $g:X\rightarrow Y^A$. Define $\psi(g):X\times A\rightarrow Y$ as follows:

• for any pair $(x,a)\in X\times A$ let $\psi(g)(x,a):=g(x)(a)$.

Then $\psi\circ\phi:Hom_{Set}(X\times A,Y)\rightarrow Hom_{Set}(X\times A,Y)$.

$$(\psi\circ\phi)(f)(x,a)=\psi(\phi(f))(x,a)=\psi(g)(x,a)\\ =g(x)(a)=\phi(f)(x)(a)=f(x,a)\\ (\phi\circ\psi)(g)(x)(a)=\phi(\psi(g))(x)(a)=\psi(g)(x,a)=g(x)(a)$$

So

$$(\psi\circ\phi)(f)=f\\ (\phi\circ\psi)(g)=g$$

---

Proposition: Let’s denote $A\sqcup B$ with $A+B$. Then:

$$A+\underline{0}\cong A\\ A+B\cong B+A\\ (A+B)+C\cong A+(B+C)\\ A\times\underline{0}\cong \underline{0}\\ A\times\underline{1}\cong A\\ A\times B\cong B\times A\\ (A\times B)\times C\cong A\times(B\times C)\\ A\times(B+C)\cong(A\times B)+(A\times C)\\ A^{\underline{0}}\cong 1\\ A^{\underline{1}}\cong A\\ \underline{0}^A\cong\underline{0}\\ \underline{1}^A\cong\underline{1}\\ A^{B+C}\cong A^B\times A^C\\ (A^B)^C\cong A^{B\times C}$$

Special case: $\underline{0}^{\underline{0}}= Hom_{Set}(\emptyset,\emptyset)=\emptyset$.

Example: For any sets $A,B$, let’s consider the function $ev:B^A\times A\rightarrow B$. $ev(f,a)=f(a)$.

specially, $ev:\underline{5}^{\underline{3}}\times\underline{3}\rightarrow\underline{5}$. Since it’s not an isomorphism, so the corresponding arithmetic expression is not equality. However, $\underline{575}\rightarrow\underline{5}$ seems weird and meaningless.

---

A simplicial complex is a pair $(V,X)$ where $V$ is a set and $X\subseteq\mathbb{P}(V)$ is a downward-closed subset that contains all atoms. The elements of $X$ are called simplices. We have a function $X\rightarrow\mathbb{N}$ sending each simplex to its cardinality. The set of simplices with cardinality $n+1$ is denoted as $X_n$. Since $X$ contains all atoms, so $X_0\cong V$. Sometimes we call 0-simplices vertices and 1-simplices edges.

Example: let $n$ be a natural number and $V=\underline{n+1}$. Define the n-simplex denoted $\Delta^n$ to be $(V,\mathbb{P}(V))$, obviously $\mathbb{P}(V)$ is downward-closed and contains all atoms.

We can draw $\Delta^0,\Delta^1,\Delta^2,\Delta^3$ as follows:

Proposition: Let $B$ be a set. There is an isomorphism

$$\phi:Hom_{Set}(B,\Omega)\stackrel{\cong}{\rightarrow}\mathbb{P}(B)$$

Proof:

$$\phi:Hom_{Set}(B,\Omega)\rightarrow\mathbb{P}(B)\\ \psi:\mathbb{P}(B)\rightarrow Hom_{Set}(B,\Omega)\\ \phi(f)=\{b|f(b)=True,b\in B\}\\ \psi(B')(b)=\begin{cases}True&b\in B'\\False&b\notin B'\end{cases}$$

---

Proposition: Let $f:X\rightarrow Y$ be a function. Then $f$ is injective if and only if it is a monomorphism; $f$ is surjective if and only if it is an epimorphism.

Proposition: Let $f:X\rightarrow Y$ be a monomorphism. Then for any function $g:A\rightarrow Y$, the top map $f':X\times_Y A\rightarrow A$ in the diagram

is a monomorphism.

Proof: Consider the diagram:

B is an arbitrary set and we have

$$f'\circ m=f'\circ n$$

we need to prove that $m=n$. Firstly we construct two morphism

$$q=g'\circ m\\ r=g'\circ n$$

Then

$$f\circ q = f\circ g'\circ m=g\circ f'\circ m=g\circ f'\circ n = f\circ g'\circ n=f\circ r$$

since $f$ is a monomorphism, so $q=r$. Due to the universal property of pullback, there is a unique morphism $B\rightarrow X\times_Y A$. So $m=n$.

Remark: if the morphism from $B$ to $A$ and from $B$ to $X$ is unique ($f'\circ m=f'\circ n$ and $q=r$) then the morphism from $B$ to $X\times_Y A$ is unique.

Corollary: Let $i:A\rightarrow X$ be a monomorphism. Then there is a fiber product square of the form:

emmm… it’s quite self-evident if you think carefully. The behavior of $f$ and $f'$ is obvious.

---

Example: $E=\{1,2,3,4,5\}$, $B=\{a,b,c\}$ ,

$$\pi(1)=a,\pi(2)=a\\ \pi(3)=b\\ \pi(4)=c,\pi(5)=c$$

then it is somehow representing multiset $\{a,a,b,c,c\}$.

Suppose that $X=(E,B,\pi)$ and $X'=(E',B',\pi')$ are multisets. A mapping from $X$ to $Y$, denoted $f:X\rightarrow Y$, consists of a pair $(f_1,f_0)$ such that $f_1:E\rightarrow E'$ and $f_0:B\rightarrow B'$ are functions and such that the following diagram commutes:

We can understand it as “the map preserves the instance-name mapping”.

---

# Categories and functors

# Monoids

Example (Trivial monoid) There is a monoid with only one element, $M=(\{e\},e,*)$ where $*:(e,e)\rightarrow e$. We call this monoid the trivial monoid and sometimes denoted it $\underline{1}$/

Given two lists $L=(n,f),L'=(n',f')$, the concatenation of $L$ and $L'$ is denoted $L++L'=(n+n',f++f')$. The behavior of $f++f':\underline{n+n'}\rightarrow X$ is natural:

$$(f++f')(i):=\begin{cases}f(i)&i\leq n\\f'(i-n)&i\geq n+1\end{cases}$$

Example: Let $G=\{a,b,c,d\}$ representing four buttons that can be pressed. The free monoid $List(G)$ is the set of all ways of pressing buttons, like $[a,a,c,c,d]$ means you push button $a$, then $a$, then $c$, then $c$, then $d$.

But when you notice that you press $[a,a,c]$ is always equivalent to $[d,d]$, and you press $[a,c,a,c]$ is actually doing nothing. So we can have relation:

$$([a,a,c],[d,d]),([a,c,a,c],[])$$

So we can have the equivalent relation in Presented monoid:

$$[b,c,b,d,d,a,c,a,a,c,d]=[b,c,b,a,a,c,a,c,a,a,c,d]=\\ [b,c,b,a,a,a,c,d]=[b,c,b,a,d,d,d]$$

Example: Consider the monoid where $G=\{a\}$ and the relation is empty. We get the additive monoid of natural numbers now since $[a,a]++[a]=[a,a,a]$. With the really strong relation $[a]\sim []$ we would get the trivial monoid having only one element $[]$.

# Monoid actions

Remark: To be pedantic, we may rewrite $\circlearrowleft$ as $\alpha$:

• $\alpha(e,s)=s$
• $\alpha(m,\alpha(n,s))=\alpha(m*n,s)$

Example: let $S=\{0,1,2,...,11\}$ and $N=(\mathbb{N},0,+)$ be the additive monoid of natural numbers. We define a function $\circlearrowleft$:

$$n\circlearrowleft s = (n+s)\%12$$

the function is an action on $S$.

Example: Let $f:\mathbb{R}\rightarrow\mathbb{R}$ be a differentiable function of which we want to find roots. Let $x_0$ be a starting point, consider the Newton’s method:

$$x_{n+1}=g(x_n)=x_n-\frac{f(x_n)}{f'(x_n)}$$

This is a monoid $M=(\mathbb{N},+,0)$ acting on a set $\mathbb{R}$. and function:

$$n\circlearrowleft x=g^n(x)$$

Example: Consider a monoid $M$ generated by the set $\{u,d,r\}$ standing for “up,down,right” and subject to the relations:

$$[u,d]\sim[]\quad[d,u]\sim[]\quad[u,r]\sim [r,u]\quad[d,r]\sim[r,d]$$

We may think the monoid acts on the set of positions. so “a list of movements + a position = a position” is the action.

---

Proposition: Let $\Sigma,S$ be finite non-empty sets. Giving a function $\delta:\Sigma\times S\rightarrow S$ is equivalent to giving an action of the free monoid $List(\Sigma)$ on $S$.

Proof: As matter of fact, we just need to prove that:

$$Hom_{Set}(List(\Sigma)\times S,S)\stackrel{\cong}{\rightarrow}Hom_{Set}(\Sigma\times S,S)$$

Let’s define:

$$\psi:Hom_{Set}(\Sigma\times S,S)\rightarrow Hom_{Set}(List(\Sigma)\times S,S)\\ \psi(f):List(\Sigma)\times S\rightarrow S\\ \psi(f)(L,q)=\begin{cases} q&L=[]\\ \psi(f)(L',f(a,q))& L=a::L' \end{cases}\\ \phi:Hom_{Set}(List(\Sigma)\times S,S)\rightarrow Hom_{Set}(\Sigma\times S,S)\\ \phi(g):\Sigma\times S\rightarrow S\\ \phi(g)(a,q)=g([a],q)$$

Obviously we have $\psi\circ \phi=id$ and $\phi\circ\psi=id$.

So:

"A finite state machine is an action of a free monoid on a finite set."

# Monoid homomorphism

Example: Given any monoid $\mathcal{M}$ there is a unique monoid homomorphism from $\mathcal{M}$ to the trivial monoid $\underline{1}$. There is also a unique homomorphism $\underline{1}\rightarrow\mathcal{M}$. These facts together have an upshot: we can always construct a homomorphism:

$$\mathcal{M}\stackrel{!}{\rightarrow}\underline{1}\stackrel{!}{\rightarrow }\mathcal{M}'$$

which we call the trivial homomorphism.

Proposition: Let $\mathcal{M}=(\mathbb{Z},0,+)$ and $\mathcal{M'}=(\mathbb{N},0,+)$. The only monoid homomorphism $f:\mathcal{M}\rightarrow\mathcal{M}'$ sends every element $m\in\mathbb{Z}$ to $0\in\mathbb{N}$.

Proof:

$$0=f(0)=f(1+(-1))=f(1)+f(-1)\\ \because f(1),f(-1)\in\mathbb{N},f(1)+f(-1)=0\\ \therefore f(1)=f(-1)=0$$

Similarly, $f(x)\equiv 0$.

---

Proposition: Let $G$ be a set, let $F(G)=(List(G),[],++)$ be the free monoid on $G$, and let $\mathcal{M}=(M,e,*)$ be any monoid. There is a natural bijection:

$$Hom_{Mon}(F(G),\mathcal{M})\stackrel{\cong}{\rightarrow}Hom_{Set}(G,M)$$

Proof: We construct

$$\phi:Hom_{Mon}(F(G),\mathcal{M})\rightarrow Hom_{Set}(G,M)\\ \phi(f)(g)=f([g])\\ \psi:Hom_{Set}(G,M)\rightarrow Hom_{Mon}(F(G),\mathcal{M})\\ \psi(p)([g_1,...,g_n])=p(g_1)*...*p(g_n)\\ \psi(p)([])=e$$

Then

$$\psi(\phi(f))(L)=(\phi(f)(g_1)*...*\phi(f)(g_n))=f([g_1])*...*f([g_n])\\ =f([g_1]++...++[g_n])=f(L)\\$$

vice versa.

---

Proposition: Let $\mathcal{M}=(M,e,*)$ and $\mathcal{M}'=(M',e',*')$ be monoids, $f:\mathcal{M}\rightarrow\mathcal{M}'$ a monoid homomorphism, $S$ a set, and suppose that $\alpha:M'\times S\rightarrow S$ is an action of $\mathcal{M}'$ on $S$. Then $\Delta_f(\alpha):M\times S\rightarrow S$, defined as:

$$\Delta_f(\alpha)(m,s)=\alpha(f(m),s)\in S$$

is a $\mathcal{M}$-monoid action on $S$.

Proof: as easy as a pie.

# Groups

Proposition: The inverse element is unique.

# Graphs

# Orders

# Category theory

# categories and functors

Remark: Although we say $Ob(\mathcal{C})$ is a collection of objects(that’s because sometimes we want to talk about set category, where all objects are sets), at the beginning of study, we still consider $Ob(\mathcal{C})$ as a set.

Example: Inside the category Set is a subcategory Fin$\subseteq$Set, called the category of finite sets. Whereas an object $S\in Ob(\textbf{Set})$ is a set that can have arbitrary cardinality, we define Fin such that its objects include all the sets $S$ with finitely many elements, i.e. $|S|=n$ for some natural number $n$. Every object of Fin is an object of Set, but not vice versa. The morphisms are the same:

$$Hom_{\textbf{Fin}}(S,S')=Hom_{\textbf{Set}}(S,S')$$

Example(The category Mon of monoids): objects are monoids, and morphisms are the homomorphisms in monoids.

Example(The category Grp of groups): objects are groups, and morphisms are the homomorphisms in groups.

Example(The category PrO of preorders): objects are preorders, and morphisms are the homomorphisms in preorders.

Example(The category Grph of graphs): objects are graphs, and morphisms are the graph homomorphisms. Notice that since the left rectangular and the right rectangular commute, the whole diagram commutes.

So the associativity is ensured.

---

Let’s consider another definition of category:

---

Example: Consider the functor:

$$U:\textbf{Mon}\rightarrow\textbf{Set}$$

Which means every monoid has a underlying set, and every homomorphisms between monoids has a corresponding function between sets.

Proposition: Let PrO be the category of preorders and Grph be the category of graphs. There is function $P:\textbf{PrO}\rightarrow\textbf{Grph}$ such that for any preorder $\mathcal{X}=(X,\leq)$, the graph $P(\mathcal{X})$ has vertices $X$.

Proposition: There exists a category, called the category of small categories and denoted Cat, in which the objects are the small categories and the morphisms are the functors:

$$Hom_{Cat}(\mathcal{C},\mathcal{D})=\{F:\mathcal{C}\rightarrow\mathcal{D}|F\;is\;a\;functor\}$$

# Categories and functors commonly arising in mathematics

# Monoids as categories

Let $(M,e,*)$ be a monoid. We consider it as a category $\mathcal{M}$ with one object, $Ob(\mathcal{M})=\{\Delta\}$, and

$$Hom_{\mathcal{M}}(\Delta,\Delta)=M$$

The identity morphism $id_{\Delta}$ serves as the monoid identity $e$, and the composition formula

$$\circ:Hom_{\mathcal{M}}(\Delta,\Delta)\times Hom_{\mathcal{M}}(\Delta,\Delta)\rightarrow Hom_{\mathcal{M}}(\Delta,\Delta)$$

is given by $*:M\times M\rightarrow M$. The associativity and identity laws for the monoid match precisely with the associativity and identity for categories.

The homomorphism between two monoids can be interpreted as the functor between two one-object categories.

"A monoid is a category with one object. A monoid homomorphism is just a functor between one-object categories."

Example: Let $\mathcal{C}$ be a category and $x\in Ob(\mathcal{C})$ an object. Let $M=Hom_{\mathcal{C}}(x,x)$. Note that for any two elements $f,g\in m$ we have $f\circ g\in M$. Let $\mathcal{M}=(M,id_x,\circ)$. It is easy to check that $\mathcal{M}$ is a monoid; it is called the endomorphism monoid of $x$ in $\mathcal{C}$.

# Groups as categories

"A group is a category with one object, such that every morphism is an isomorphism. A group homomorphism is just a functor between such categories"