CAT Theory，meow~

# # The category of sets

## # Isomorphism

Definition(Isomorphism)

Let $X$ and $Y$ be sets. A function $f:X\rightarrow Y$ is called an isomorphism, denoted $X\stackrel{\cong}{\rightarrow}Y$, if there exists a function $g:Y\rightarrow X$ such that $g\circ f=id_X$ and $f\circ g=id_Y$.

We also say that $f$ is invertible and we say that $g$ is the inverse of $f$. If there exists an isomorphism $X\stackrel{\cong}{\rightarrow} Y$ we say that $X$ and $Y$ are isomorphic sets and may write $X\cong Y$.

Lemma:

• $\forall A,A\cong A$.
• $\forall A,B,A\cong B\Leftrightarrow B\cong A$.
• $\forall A,B,C,(A\cong B\wedge B\cong C)\Rightarrow A\cong C$.
• $\forall A,B,A\cong B\Rightarrow |A|=|B|$.

## # 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

Definition(products)

Let $X$ and $Y$ be sets. The product of $X$ and $Y$, denoted $X\times Y$, is defined as

$X\times Y =\{(x,y)|x\in X,y\in Y\}$

There are two natural project functions $\pi_1:X\times Y\rightarrow X$ and $\pi_2:X\times Y\rightarrow Y$.

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

Lemma(Universal property for product)

Let $X$ and $Y$ be sets. For any set $A$ and functions $f:A\rightarrow X$ and $g:A\rightarrow Y$, there exists a unique function $A\rightarrow X\times Y$ such that the following diagram commutes.

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))$.

Definition(coproducts)

Let $X$ and $Y$ be sets. The coproduct of $X$ and $Y$, denoted $X\sqcup Y$, is defined as the “disjoint union” of $X$ and $Y$. If an element is both in $X$ and $Y$, then we need to copy it in $X\sqcup Y$ so we can distinguish where each of it comes from.

There are two natural project functions $i_1:X\rightarrow X\sqcup Y$ and $i_2:Y \rightarrow X\sqcup Y$.

Example:

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

Lemma(Universal property for coproduct)

Let $X$ and $Y$ be sets. For any set $A$ and functions $f:X\rightarrow A$ and $g:Y\rightarrow A$, there exists a unique function $X\sqcup Y\rightarrow A$ such that the following diagram commutes.

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

Definition(Pullback)

Suppose given the diagram of sets and functions below:

Its fiber product is the set

$X\times_Z Y:=\{(x,w,y)|f(x)=w=g(y)\}$

There are obvious projections $\pi_1:X\times_Z Y\rightarrow X$ and $\pi_2:X\times_Z Y\rightarrow Y$. Note that if $W=X\times_Z Y$ then the diagram

commutes. So given the setup diagram we define the pullback of $X$ and $Y$ over $Z$ to be any set $W$ for which we have an isomorphism $W\stackrel{\cong}{\rightarrow} X\times_Z Y$.

The corner symbol $\lrcorner$ indicates that $W$ is the pullback.

Lemma(Universal property for pullback)

Suppose given the diagram as below:

For any set $A$ and commutative solid arrow diagram as below (i.e. $t\circ f=u\circ g$)

there exists a unique arrow $\langle f,f\rangle_Z:A\rightarrow X\times_Z Y$ making everything commute.

Definition(Preimage)

Let $f:X\rightarrow Y$ be a function and $y\in Y$ an element. The preimage of $y$ under $f$, denoted $f^{-1}(y)$, is the subset $f^{-1}(y):=\{x\in X|f(x)=y\}$. If $Y'\subseteq Y$ is any subset, the preimage of $Y'$ under $f$, denoted $f^{-1}(Y')$, is the subset $f^{-1}(Y')=\{x\in X|f(x)\in Y'\}$.

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:

Definition

Given sets $A$ and $B$, a span on $A$ and $B$ is a set $R$ together with functions $f:R\rightarrow A$ and $g:R\rightarrow B$.

Definition

Let $A,B$ and $C$ be sets, and let $A\stackrel{f}{\leftarrow} R\stackrel{g}{\rightarrow}C$ and $B\stackrel{f'}{\leftarrow} R'\stackrel{g'}{\rightarrow}C$ be spans. Their composite span is given by the fiber product $R\times_B R'$ as in the diagram below:

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'$.

Definition

Suppose given two parallel arrows:

The equalizer of $f$ and $g$ is the commutative diagram as to the right shown above, where we define

$Eq(f,g):=\{x\in X|f(x)=g(x)\}$

and where $p$ is the canonical inclusion.

## # Finite colimits in Set

Definition(Pullout)

Suppose given the diagram of sets and functions below:

Its fiber sum, denoted $X\sqcup_W Y$, is defined as the quotient of $X\sqcup W\sqcup Y$ by the equivalence relation $\sim$ generated by $w\sim f(w)$ and $w\sim g(w)$ for all $w\in W$.

$X\sqcup_W Y:=(X\sqcup W\sqcup Y)/\sim$

where $\forall w\in W,w\sim f(w)$ and $w\sim g(w)$.

There are obvious inclusions $i_1:X\rightarrow X\sqcup_W Y$ and $i_2:X\rightarrow X\sqcup_W Y$. The following diagram commutes:

We define the pushout of $X$ and $Y$ over $W$ to be any set $Z$ for which we have an isomorphism $Z\stackrel{\cong}{\rightarrow} X\sqcup_W Y$. The corner symbol $\ulcorner$ indicates that $Z$ is the pushout.

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\}\\ \}$

Lemma(Universal property for pushout)

Suppose given the diagram as below:

For any set $A$ and commutative solid arrow diagram as below (i.e. $f\circ t=g\circ u$)

there exists a unique arrow $\begin{cases}f\\g\end{cases}:X\sqcup_WY\rightarrow A$ makes everything commute.

Definition

Suppose given two parallel arrows:

The coequalizer of $f$ and $g$ is the commutative diagram as to the right figure, where we define

$Coeq(f,g):=Y/f(x)\sim g(x)$

## # Other notions

Definition(Retractions)

Suppose we have a function $f:X\rightarrow Y$ and a function $g:Y\rightarrow X$ such that $g\circ f=id_X$. In this case we call $f$ a retract section and we call $g$ a retract projection.

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.

Definition

Let $V$ be a set and let $\mathbb{P}(V)$ be its powerset. A subset $X\subseteq\mathbb{P}(V)$ is called downward-closed if, for every $u\in X$ and every $u'\subseteq u$, we have $u'\in X$. We say that $X$ contains all atoms if for every $v\in V$ the singleton set $\{v\}$ is an element of $X$.

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:

Definition

Define the subobject classifier for Set, denoted $\Omega$, to be the set $\Omega:=\{True,False\}$, together with the function $\{\heartsuit\}\rightarrow\Omega$ sending the unique element to True.

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}$

Definition

Let $f:X\rightarrow Y$ be a function. We say that $f$ is surjective if, for all $y\in Y$ there exists some $x\in X$ such that $f(x)=y$. We say that $f$ is injective if, for all $x\in X$ and all $x'\in X$ with $f(x)=f(x')$ we have $x=x'$.

Definition

Let $f:X\rightarrow Y$ be a function. We say that $f$ is a monomorphism if for all sets $A$ and pairs of functions $g$, $g':A\rightarrow X$,

if $f\circ g=f\circ g'$ then $g=g'$.

We say that $f$ is an epimorphism if for all sets $B$ and pairs of functions $h,h':Y\rightarrow B$,

if $h\circ f=h\circ f'$ then $h=h'$.

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.

Definition

A multiset is a sequence $X:=(E,B,\pi)$ where $E$ and $B$ are sets and $\pi:E\rightarrow B$ is a surjective function. We refer to $E$ as the set of element instances of $X$, we refer to b as the set of element names of $X$ and we refer to $\pi$ as the naming function for $X$. Given an element name $x\in B$, let $\pi^{-1}(x)\subseteq E$ be the preimage; the number of elements in $\pi^{-1}(x)$ is called the multiplicity of $x$.

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”.

Definition(Relative set)

Let $B$ be a set. A relative set over $B$, or simply a set over $B$, is a pair $(E,\pi)$ such that $E$ is a set and $\pi:E\rightarrow B$ is a function. A mapping of relative sets over $B$, denoted $f:(E,B)\rightarrow(E',B')$, is a function $f:E\rightarrow E'$ such that the triangle below commutes, i.e. $\pi=\pi'\circ f$.

Definition(Indexed set)

Let $A$ be a set. An $A$-indexed set is a collection of sets $S_a$, one for each element $a\in A$; for now we denote this by $(S_a)_{a\in A}$. If $(S_a')_{a\in A}$ is another $A$-indexed set, a mapping of $A$-indexed sets from $(S_a)_{a\in A}$ to $(S_a')_{a\in A}$, denoted

$(f_a)_{a\in A}:(S_a)_{a\in A}\rightarrow (S_a')_{a\in A}$

is a collection of functions $f_a:S_a\rightarrow S_a'$, one for each element $a\in A$.

# # Categories and functors

## # Monoids

Definition(Monoid)

A monoid is a sequence $(M,e,*)$, where $M$ is a set, $e\in m$ is an element, and $*:M\times M\rightarrow M$ is a function, such that the following conditions hold for all $m,n,p\in M$:

• $m*e=m$
• $e*m=m$
• $(m*n)*p=m*(n*p)$

We refer to $e$ as the identity element and to $*$ as the multiplication formula for the monoid. We call the first two rules identity laws and the third rule the associativity law for 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}$/

Definition

Let $X$ be a set. A list in $X$ is a pair $(n,f)$ where $n\in\mathbb{N}$ is a natural number (called the length of the list) and $f:\underline{n}\rightarrow X$ is a function. We may denote such a list by

$(n,f)=[f(1),f(2),...,f(n)]$

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}$

Definition(Free monoid)

Let $X$ be a set. The free monoid generated by $X$ is the sequence $M:=(List(X),[],++)$, where $List(X)$ is the set of lists of elements in $X$. We refer to $X$ as the set of generators for the monoid $M$.

Definition(Presented monoid)

Let $G$ be a finite set, and $n$ be a natural number, and for each $1\leq i\leq n$, let $m_i$ and $m_i'$ be elements of $List(G)$. The monoid presented by generators $G$ and relations $\{(m_i,m_i')|1\leq i\leq n\}$ is the monoid $\mathcal{M}=(M,e,*)$ defined as follows:

• Let $\sim$ denote the equivalence relation on $List(G)$ generated by \
• define $M=List(G)/\sim$
• $e=[]$
• $*$ is concatenating lists.

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]$

Definition

A monoid is called cyclic if it has a representation involving only one generator, In other words, $|G|=1$.

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

Definition (Monoid action)

Let $(M,e,*)$ be a monoid and let $S$ be a set. An action of $(M,e,*)$ on $S$, or simply an action of $M$ on $S$ or an $M$-action on $S$, is a function

$\circlearrowleft:M\times S\rightarrow S$

such that the following conditions hold for all $m,n\in M$ and all $s\in S$:

• $e\circlearrowleft s = s$

• $m\circlearrowleft(n\circlearrowleft s)=(m*n)\circlearrowleft s$

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

Definition (Monoid homomorphism)

Let $\mathcal{M}=(M,e,*)$ and $\mathcal{M}'=(M',e',*')$ be monoids. A monoid homomorphism $f$ from $\mathcal{M}$ to $\mathcal{M}'$, denoted $f:\mathcal{M}\rightarrow\mathcal{M}'$, is a function $f:M\rightarrow M'$, satisfying:

• $f(e)=e'$
• $f(m_1*m_2)=f(m_1)*'f(m_2)$

The set of monoid homomorphisms from $\mathcal{M}$ to $\mathcal{M}'$ is denoted $Hom_{Mon}(\mathcal{M},\mathcal{M}')$.

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

Definition (Group)

Let $(M,e,*)$ be a monoid. An element $m\in M$ is said to have an inverse if there exists an $m'\in M$ such that $mm'=e$ and $m'm=e$. A group is a monoid in which every element $m\in M$ has an inverse.

Proposition: The inverse element is unique.

Definition (Group action)

Let $(G,e,*)$ be a group and $S$ a set. An action of $G$ on $S$ is a function:

$\circlearrowleft:G\times S\rightarrow S$

such that for all $s\in S$ and $g,g'\in G$, we have

• $e\circlearrowleft s=s$
• $g\circlearrowleft(g'\circlearrowleft s)=(g*g')\circlearrowleft s$.

Definition(orbit)

Let $G$ be a group acting on a set $X$. For any point $x\in X$, the orbit of $x$, denoted $Gx$, is the set

$Gx:=\{x'\in X|\exists g\in G,g\circlearrowleft x=x'\}$

Definition

Let $G$ and $G'$ be groups. A group homomorphism $f:G\rightarrow G'$ is defined to be a monoid homomorphism.

## # Graphs

Definition(Graph)

A graph consists of a sequence $G=(V,A,src,tgt)$:

• $V$ is a set, called the set of vertices.
• $A$ is a set, called the set of arrows.
• $src:A\rightarrow V$ is a function, called the source function.
• $tgt:A\rightarrow V$ is a function, called the target function.

Definition(Path)

Let $G=(V,A,src,tgt)$ be a graph. A path of length $n$ in $G$, denoted $p\in Path^{(n)}_G$ is a head-to-tail sequence

$p=(v_0\stackrel{a_1}{\rightarrow}v_1\stackrel{a_2}{\rightarrow}v_2\stackrel{a_3}{\rightarrow}...\stackrel{a_n}{\rightarrow}v_n)$

of arrows in $G$, which we denote by $v_0a_1a_2...a_n$. In particular we have canonical isomorphism $Path^{(1)}_G\cong A$ and $Path^{(0)}_G\cong V$. And

$Path_G=\bigcup_{n\in\mathbb{N}}Path^{(n)}_G$

we denote the source and the target vertex of a path by

$\bar{src},\bar{tgt}:Path_G\rightarrow V$

Definition

Let $G=(V,A,src,tgt)$ and $G'=(V',A',src',tgt')$ be graphs. A graph homomorphism $f$ from $G$ to $G'$, denoted $f:G\rightarrow G'$, consists of two functions $f_0:V\rightarrow V'$ and $f_1:A\rightarrow A'$ such that the two diagrams below commute:

## # Orders

Definition(Order)

Let $S$ be a set and $R\subseteq S\times S$ a binary relation on $S$; if $(s,s')\in R$ we will write $s\leq s'$, then we say that $R$ is a preorder if, for all $s,s',s''\in S$ we have

• $s\leq s$
• if $s\leq s'$ and $s'\leq s''$ then $s\leq s''$

If we want it to be a partial order, then we need to add

• If $s\leq s'$ and $s'\leq s$ then $s=s'$

If we want it to be a linear order, then we need to add

• Either $s\leq s'$ or $s'\leq s$.

Definition(clique)

Let $(S,\leq)$ be a preorder. A clique is a subset $S'\subseteq S$ such that for each $a,b\in S'$ one has $a\leq b$.

Definition(meet, join)

Let $(S,\leq)$ be a preorder and let $s,t\in S$ be elements. A meet of $s$ and $t$ is an element $w\in S$ satisfying

• $w\leq s$ and $w\leq t$
• for any $x\in S$, if $x\leq s$ and $x\leq t$ then $x\leq w$

We write as $w\cong s\wedge t$.

A join of $s$ and $t$ is an element $w\in S$ satisfying

• $s\leq w$ and $t\leq w$
• for any $x\in S$, if $s\leq x$ and $t\leq x$ then $w\leq x$

We write as $w\cong s\vee t$.

Definition(opposite order)

Let $\mathcal{S}=(S,\leq)$ be a preorder. The opposite preorder, denoted $\mathcal{S}^{op}$ is the preorder $(S,\leq^{op})$ having the same set of elements but where $s\leq^{op}s'$ iff $s'\leq s$.

Definition(opposite order)

Let $\mathcal{S}=(S,\leq)$ and $\mathcal{S}'=(S',\leq')$ be preorders, A morphism of preorders denoted $f:\mathcal{S}\rightarrow\mathcal{S}'$ is a function $f:S\rightarrow S'$ such that, for every pair of elements $s_1,s_2\in S$, if $s_1\leq s_2$ then $f(s_1)\leq'f(s_2)$.

# # Category theory

## # categories and functors

Definition

A category $\mathcal{C}$ is defined as follows: One announces some constituents (objects, morphisms, identities, compositions) and asserts (identity law, associativity law) that they conform to some laws. Specifically, one announces:

1. a collection $Ob(\mathcal{C})$, elements of which are called objects.

2. for every pair $x,y\in Ob(\mathcal{C})$, a set $Hom_{\mathcal{C}}(x,y)$. It is called the hom-set from $x$ to $y$; its elements are called morphisms from $x$ to $y$.

3. for every object $x\in Ob(\mathcal{C})$, a specified morphism denoted $id_x\in Hom_{\mathcal{C}}(x,x)$ called the identity morphism on $x$.

4. for every three objects $x,y,z\in Ob(\mathcal{C})$, a function

$\circ:Hom_{\mathcal{C}(y,z)}\times Hom_{\mathcal{C}}(x,y)\rightarrow Hom_{\mathcal{C}}(x,z)$

called the composition formula.

Given objects $x,y\in Ob(\mathcal{C})$, we can denote a morphism $f\in Hom_{\mathcal{C}}(x,y)$ by $f:x\rightarrow y$; we say that $x$ is the domain of $f$ and that $y$ is the codomain of $f$. Given also $g:y\rightarrow z$, the composition formula is written using infix notation, so $g\circ f:x\rightarrow z$ means $\circ(g,f)\in Hom_{\mathcal{C}}(x,z)$.

1. for every $x,y\in Ob(\mathcal{C})$ and every morphism $f:x\rightarrow y$, we have

$f\circ id_x = f\quad id_y\circ f = f$

1. if $w,x,y,z,\in Ob(\mathcal{C})$ are any objects and $f:w\rightarrow x,g:x\rightarrow y$ and $h:y\rightarrow z$ are any morphisms, then the two ways to compose are the same:

$(h\circ g)\circ f=h\circ (g\circ f)$

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.

Definition(isomorphism)

Let $\mathcal{C}$ be a category and let $X,Y\in Ob(\mathcal{C})$ be objects. An isomorphism $f$ from $X$ to $Y$ is a morphism $f:X\rightarrow Y$ in $\mathcal{C}$, such that there exists a morphism $g:Y\rightarrow X$ in $\mathcal{C}$ such that

$g\circ f=id_X,f\circ g = id_Y$

In this case we say that the morphism $f$ is invertible and that $g$ is the inverse of $f$. We may also say that the objects $X$ and $Y$ are isomorphic.

Lemma

Let $\mathcal{C}$ be a category and let $\sim$ be the relation on $Ob(\mathcal{C})$ given by saying $X\sim Y$ iff $X$ and $Y$ are isomorphic. Then $\sim$ is an equivalence relation.

Let’s consider another definition of category:

Definition

A category $\mathcal{C}$ consists of a sequence $(Ob(\mathcal{C}),Hom_{\mathcal{C}},dom,cod,ids,\circ)$ where

1. $Ob(\mathcal{C})$ is a set
2. $Hom_{\mathcal{C}}$ is a set, and $dom,cod:Hom_\mathcal{C}\rightarrow Ob(\mathcal{C})$ are functions
3. $ids:Ob(\mathcal{C})\rightarrow Hom_{\mathcal{C}}$ is a function
4. $\circ$ is a function as depicted in the commutative diagram below

Definition(functors)

Let $\mathcal{C}$ and $\mathcal{C}'$ be categories. A functor $F$ from $\mathcal{C}$ to $\mathcal{C}'$, denoted $F:\mathcal{C}\rightarrow\mathcal{C}'$, is defined as follows: One announces some constituents and asserts that they conform to some laws. Specifically, one announces

1. a function $Ob(F):Ob(\mathcal{C})\rightarrow Ob(\mathcal{C}')$ which we sometimes denote simply by $F:Ob(\mathcal{C})\rightarrow Ob(\mathcal{C}')$

2. for every pair of objects $c,d\in Ob(\mathcal{C})$, a function

$Hom_F(c,d):Hom_{\mathcal{C}}(c,d)\rightarrow Hom_{\mathcal{C}'}(F(c),F(d))$

which we sometimes denote simply by $F:Hom_{\mathcal{C}}(c,d)\rightarrow Hom_{\mathcal{C}'}(F(c),F(d))$.

One asserts that the following laws hold:

1. Identities are preserved by $F$:

$F(id_c)=id_{F(c)}$

2. Composition is preserved by $F$:

$F(h\circ g)=F(h)\circ F(g)$

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."

Theorem:

There is a functor $i:\textbf{Mon}\rightarrow\textbf{Cat}$ with the following properties:

• for every monoid $\mathcal{M}\in Ob(\textbf{Mon})$, the category $i(\mathcal{M})\in Ob(\textbf{Cat})$ itself has exactly one object.

• for every pair of monoids $\mathcal{M},\mathcal{M'}\in Ob(\textbf{Mon})$ the function

$Hom_{\textbf{Mon}}(\mathcal{M},\mathcal{M}')\stackrel{\cong}{\rightarrow}Hom_{\textbf{Cat}}(i(\mathcal{M}),i(\mathcal{M}'))$

induced by the functor $i$, is a bijection.

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"

Theorem:

There is a functor $i:\textbf{Grp}\rightarrow\textbf{Cat}$ with the following properties

• for every group $\mathcal{G}\in Ob(\textbf{Grp})$, the category $i(\mathcal{G})\in Ob(\textbf{Cat})$ itself has exactly one object, and every morphism in $i(\mathcal{G})$ is an isomorphism

• for every pair of groups $\mathcal{G,G}'\in Ob(\textbf{Grp})$ the function

$Ho{m}_{\mathbf{\text{Grp}}}\left(\mathcal{G},{\mathcal{G}}^{\mathrm{\prime }}\right)\stackrel{\cong }{\to }Ho{m}_{\mathbf{\text{Cat}}}\left(i\left(\mathcal{G}\right),i$