CAT Theory,meow~

# The category of sets

# Isomorphism

Definition(Isomorphism)

Let XX and YY be sets. A function f:XYf:X\rightarrow Y is called an isomorphism, denoted XYX\stackrel{\cong}{\rightarrow}Y, if there exists a function g:YXg:Y\rightarrow X such that gf=idXg\circ f=id_X and fg=idYf\circ g=id_Y.

We also say that ff is invertible and we say that gg is the inverse of ff. If there exists an isomorphism XYX\stackrel{\cong}{\rightarrow} Y we say that XX and YY are isomorphic sets and may write XYX\cong Y.

Lemma:

  • A,AA\forall A,A\cong A.
  • A,B,ABBA\forall A,B,A\cong B\Leftrightarrow B\cong A.
  • A,B,C,(ABBC)AC\forall A,B,C,(A\cong B\wedge B\cong C)\Rightarrow A\cong C.
  • A,B,ABA=B\forall A,B,A\cong B\Rightarrow |A|=|B|.

# Commutative diagrams

1

We say this is a diagram of sets if each of A,B,CA,B,C is a set and each of f,g,hf,g,h is a function. We say this diagram commutes if gf=hg\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.

2

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

3

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

# Ologs

Example:

4

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:

5

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  childhasa  fathera\; child\stackrel{has}{\rightarrow}a\;father instead of a  fatherhasa  childa\;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.

6

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:

7

# Products and coproducts

Definition(products)

Let XX and YY be sets. The product of XX and YY, denoted X×YX\times Y, is defined as

X×Y={(x,y)xX,yY}X\times Y =\{(x,y)|x\in X,y\in Y\}

There are two natural project functions π1:X×YX\pi_1:X\times Y\rightarrow X and π2:X×YY\pi_2:X\times Y\rightarrow Y.

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

8

Lemma(Universal property for product)

Let XX and YY be sets. For any set AA and functions f:AXf:A\rightarrow X and g:AYg:A\rightarrow Y, there exists a unique function AX×YA\rightarrow X\times Y such that the following diagram commutes.

9

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

Definition(coproducts)

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

There are two natural project functions i1:XXYi_1:X\rightarrow X\sqcup Y and i2:YXYi_2:Y \rightarrow X\sqcup Y.

10

Example:

{a,b}{a,c}={i1a,b,i2a,c}\{a,b\}\sqcup \{a,c\}=\{i_1a,b,i_2a,c\}

Lemma(Universal property for coproduct)

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

11

We may write the unique functions as

{fg:XYA{fg(m)={f(x)if  m=i1xg(y)if  m=i2y\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:
12

Its fiber product is the set

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

There are obvious projections π1:X×ZYX\pi_1:X\times_Z Y\rightarrow X and π2:X×ZYY\pi_2:X\times_Z Y\rightarrow Y. Note that if W=X×ZYW=X\times_Z Y then the diagram

13

commutes. So given the setup diagram we define the pullback of XX and YY over ZZ to be any set WW for which we have an isomorphism WX×ZYW\stackrel{\cong}{\rightarrow} X\times_Z Y.

The corner symbol \lrcorner indicates that WW is the pullback.

Lemma(Universal property for pullback)

Suppose given the diagram as below:

14

For any set AA and commutative solid arrow diagram as below (i.e. tf=ugt\circ f=u\circ g)

15

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

Definition(Preimage)

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

Proposition: Consider the diagram below:

16

where BB×CCB'\cong B\times_C C' is a pullback. Then there is an isomorphism A×BBA×CCA\times_B B'\cong A\times_C C'. Said another way,

A×B(B×CC)A×CCA\times_B(B\times_C C')\cong A\times_C C'

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

17

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

Solution:

18


Definition

Given sets AA and BB, a span on AA and BB is a set RR together with functions f:RAf:R\rightarrow A and g:RBg:R\rightarrow B.

19

Definition

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

20

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

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

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

Given two spans ARBA\leftarrow R\rightarrow B and ARBA\leftarrow R'\rightarrow B, by the universal property of coproducts we have a unique span ARRBA\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 RR and RR'.


Definition

Suppose given two parallel arrows:

21

The equalizer of ff and gg is the commutative diagram as to the right shown above, where we define

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

and where pp is the canonical inclusion.

# Finite colimits in Set

Definition(Pullout)

Suppose given the diagram of sets and functions below:

22

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

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

where wW,wf(w)\forall w\in W,w\sim f(w) and wg(w)w\sim g(w).

There are obvious inclusions i1:XXWYi_1:X\rightarrow X\sqcup_W Y and i2:XXWYi_2:X\rightarrow X\sqcup_W Y. The following diagram commutes:

23

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

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

WXY={1W,2W,0X,1X,2X,3X,0Y,1Y,2Y,3Y,4Y}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

2X=f(1W)1Wg(1W)=1Y3X=f(2W)2Wg(2W)=2Y2_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:

(XWY)/={{0X}{1X}{1W,2X,1Y}{2W,3X,2Y}{0Y}{3Y}{4Y}}(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:

24

For any set AA and commutative solid arrow diagram as below (i.e. ft=guf\circ t=g\circ u)

25

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

Definition

Suppose given two parallel arrows:

26

The coequalizer of ff and gg is the commutative diagram as to the right figure, where we define

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

# Other notions

Definition(Retractions)

Suppose we have a function f:XYf:X\rightarrow Y and a function g:YXg:Y\rightarrow X such that gf=idXg\circ f=id_X. In this case we call ff a retract section and we call gg a retract projection.

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

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

ϕ:HomSet(X×A,Y)HomSet(X,YA)\phi:Hom_{Set}(X\times A,Y)\stackrel{\cong}{\rightarrow}Hom_{Set}(X,Y^A)

Proof: Suppose given f:X×AYf:X\times A\rightarrow Y, Define ϕ(f):XYA\phi(f):X\rightarrow Y^A as follows:

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

we now construct inverse, ψ:HomSet(X,YA)HomSet(X×A,Y)\psi:Hom_{Set}(X,Y^A)\rightarrow Hom_{Set}(X\times A,Y). Suppose given g:XYAg:X\rightarrow Y^A. Define ψ(g):X×AY\psi(g):X\times A\rightarrow Y as follows:

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

Then ψϕ:HomSet(X×A,Y)HomSet(X×A,Y)\psi\circ\phi:Hom_{Set}(X\times A,Y)\rightarrow Hom_{Set}(X\times A,Y).

(ψϕ)(f)(x,a)=ψ(ϕ(f))(x,a)=ψ(g)(x,a)=g(x)(a)=ϕ(f)(x)(a)=f(x,a)(ϕψ)(g)(x)(a)=ϕ(ψ(g))(x)(a)=ψ(g)(x,a)=g(x)(a)(\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

(ψϕ)(f)=f(ϕψ)(g)=g(\psi\circ\phi)(f)=f\\ (\phi\circ\psi)(g)=g


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

A+0AA+BB+A(A+B)+CA+(B+C)A×00A×1AA×BB×A(A×B)×CA×(B×C)A×(B+C)(A×B)+(A×C)A01A1A0A01A1AB+CAB×AC(AB)CAB×CA+\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: 00=HomSet(,)=\underline{0}^{\underline{0}}= Hom_{Set}(\emptyset,\emptyset)=\emptyset.

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

specially, ev:53×35ev:\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, 5755\underline{575}\rightarrow\underline{5} seems weird and meaningless.


Definition

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

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

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

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

27

Definition

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

Proposition: Let BB be a set. There is an isomorphism

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

Proof:

ϕ:HomSet(B,Ω)P(B)ψ:P(B)HomSet(B,Ω)ϕ(f)={bf(b)=True,bB}ψ(B)(b)={TruebBFalsebB\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:XYf:X\rightarrow Y be a function. We say that ff is surjective if, for all yYy\in Y there exists some xXx\in X such that f(x)=yf(x)=y. We say that ff is injective if, for all xXx\in X and all xXx'\in X with f(x)=f(x)f(x)=f(x') we have x=xx=x'.

Definition

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

28

if fg=fgf\circ g=f\circ g' then g=gg=g'.

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

29

if hf=hfh\circ f=h\circ f' then h=hh=h'.

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

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

30

is a monomorphism.

Proof: Consider the diagram:

31

B is an arbitrary set and we have

fm=fnf'\circ m=f'\circ n

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

q=gmr=gnq=g'\circ m\\ r=g'\circ n

Then

fq=fgm=gfm=gfn=fgn=frf\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 ff is a monomorphism, so q=rq=r. Due to the universal property of pullback, there is a unique morphism BX×YAB\rightarrow X\times_Y A. So m=nm=n.

Remark: if the morphism from BB to AA and from BB to XX is unique (fm=fnf'\circ m=f'\circ n and q=rq=r) then the morphism from BB to X×YAX\times_Y A is unique.

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

32

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


Definition

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

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

π(1)=a,π(2)=aπ(3)=bπ(4)=c,π(5)=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}\{a,a,b,c,c\}.

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

33

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


Definition(Relative set)

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

34

Definition(Indexed set)

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

(fa)aA:(Sa)aA(Sa)aA(f_a)_{a\in A}:(S_a)_{a\in A}\rightarrow (S_a')_{a\in A}

is a collection of functions fa:SaSaf_a:S_a\rightarrow S_a', one for each element aAa\in A.

# Categories and functors

# Monoids

Definition(Monoid)

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

  • me=mm*e=m
  • em=me*m=m
  • (mn)p=m(np)(m*n)*p=m*(n*p)

We refer to ee 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,)M=(\{e\},e,*) where :(e,e)e*:(e,e)\rightarrow e. We call this monoid the trivial monoid and sometimes denoted it 1\underline{1}/

Definition

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

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

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

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

Definition(Free monoid)

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

Definition(Presented monoid)

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

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

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

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

([a,a,c],[d,d]),([a,c,a,c],[])([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][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|G|=1.

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

# Monoid actions

Definition (Monoid action)

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

:M×SS\circlearrowleft:M\times S\rightarrow S

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

  • es=se\circlearrowleft s = s

  • m(ns)=(mn)sm\circlearrowleft(n\circlearrowleft s)=(m*n)\circlearrowleft s

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

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

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

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

the function is an action on SS.

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

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

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

nx=gn(x)n\circlearrowleft x=g^n(x)

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

[u,d][][d,u][][u,r][r,u][d,r][r,d][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 Σ,S\Sigma,S be finite non-empty sets. Giving a function δ:Σ×SS\delta:\Sigma\times S\rightarrow S is equivalent to giving an action of the free monoid List(Σ)List(\Sigma) on SS.

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

HomSet(List(Σ)×S,S)HomSet(Σ×S,S)Hom_{Set}(List(\Sigma)\times S,S)\stackrel{\cong}{\rightarrow}Hom_{Set}(\Sigma\times S,S)

Let’s define:

ψ:HomSet(Σ×S,S)HomSet(List(Σ)×S,S)ψ(f):List(Σ)×SSψ(f)(L,q)={qL=[]ψ(f)(L,f(a,q))L=a::Lϕ:HomSet(List(Σ)×S,S)HomSet(Σ×S,S)ϕ(g):Σ×SSϕ(g)(a,q)=g([a],q)\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 ψϕ=id\psi\circ \phi=id and ϕψ=id\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 M=(M,e,)\mathcal{M}=(M,e,*) and M=(M,e,)\mathcal{M}'=(M',e',*') be monoids. A monoid homomorphism ff from M\mathcal{M} to M\mathcal{M}', denoted f:MMf:\mathcal{M}\rightarrow\mathcal{M}', is a function f:MMf:M\rightarrow M', satisfying:

  • f(e)=ef(e)=e'
  • f(m1m2)=f(m1)f(m2)f(m_1*m_2)=f(m_1)*'f(m_2)

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

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

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

which we call the trivial homomorphism.

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

Proof:

0=f(0)=f(1+(1))=f(1)+f(1)f(1),f(1)N,f(1)+f(1)=0f(1)=f(1)=00=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)0f(x)\equiv 0.


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

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

Proof: We construct

ϕ:HomMon(F(G),M)HomSet(G,M)ϕ(f)(g)=f([g])ψ:HomSet(G,M)HomMon(F(G),M)ψ(p)([g1,...,gn])=p(g1)...p(gn)ψ(p)([])=e\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

ψ(ϕ(f))(L)=(ϕ(f)(g1)...ϕ(f)(gn))=f([g1])...f([gn])=f([g1]++...++[gn])=f(L)\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 M=(M,e,)\mathcal{M}=(M,e,*) and M=(M,e,)\mathcal{M}'=(M',e',*') be monoids, f:MMf:\mathcal{M}\rightarrow\mathcal{M}' a monoid homomorphism, SS a set, and suppose that α:M×SS\alpha:M'\times S\rightarrow S is an action of M\mathcal{M}' on SS. Then Δf(α):M×SS\Delta_f(\alpha):M\times S\rightarrow S, defined as:

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

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

Proof: as easy as a pie.

# Groups

Definition (Group)

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

Proposition: The inverse element is unique.

Definition (Group action)

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

:G×SS\circlearrowleft:G\times S\rightarrow S

such that for all sSs\in S and g,gGg,g'\in G, we have

  • es=se\circlearrowleft s=s
  • g(gs)=(gg)sg\circlearrowleft(g'\circlearrowleft s)=(g*g')\circlearrowleft s.

Definition(orbit)

Let GG be a group acting on a set XX. For any point xXx\in X, the orbit of xx, denoted GxGx, is the set

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

Definition

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

# Graphs

Definition(Graph)

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

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

Definition(Path)

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

p=(v0a1v1a2v2a3...anvn)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 GG, which we denote by v0a1a2...anv_0a_1a_2...a_n. In particular we have canonical isomorphism PathG(1)APath^{(1)}_G\cong A and PathG(0)VPath^{(0)}_G\cong V. And

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

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

srcˉ,tgtˉ:PathGV\bar{src},\bar{tgt}:Path_G\rightarrow V

Definition

Let G=(V,A,src,tgt)G=(V,A,src,tgt) and G=(V,A,src,tgt)G'=(V',A',src',tgt') be graphs. A graph homomorphism ff from GG to GG', denoted f:GGf:G\rightarrow G', consists of two functions f0:VVf_0:V\rightarrow V' and f1:AAf_1:A\rightarrow A' such that the two diagrams below commute:

35

# Orders

Definition(Order)

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

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

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

  • If sss\leq s' and sss'\leq s then s=ss=s'

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

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

Definition(clique)

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

Definition(meet, join)

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

  • wsw\leq s and wtw\leq t
  • for any xSx\in S, if xsx\leq s and xtx\leq t then xwx\leq w

We write as wstw\cong s\wedge t.

A join of ss and tt is an element wSw\in S satisfying

  • sws\leq w and twt\leq w
  • for any xSx\in S, if sxs\leq x and txt\leq x then wxw\leq x

We write as wstw\cong s\vee t.

Definition(opposite order)

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

Definition(opposite order)

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

# Category theory

# categories and functors

Definition

A category C\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(C)Ob(\mathcal{C}), elements of which are called objects.

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

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

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

    :HomC(y,z)×HomC(x,y)HomC(x,z)\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,yOb(C)x,y\in Ob(\mathcal{C}), we can denote a morphism fHomC(x,y)f\in Hom_{\mathcal{C}}(x,y) by f:xyf:x\rightarrow y; we say that xx is the domain of ff and that yy is the codomain of ff. Given also g:yzg:y\rightarrow z, the composition formula is written using infix notation, so gf:xzg\circ f:x\rightarrow z means (g,f)HomC(x,z)\circ(g,f)\in Hom_{\mathcal{C}}(x,z).

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

fidx=fidyf=ff\circ id_x = f\quad id_y\circ f = f

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

(hg)f=h(gf)(h\circ g)\circ f=h\circ (g\circ f)

Remark: Although we say Ob(C)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(C)Ob(\mathcal{C}) as a set.

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

HomFin(S,S)=HomSet(S,S)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.

36

So the associativity is ensured.


Definition(isomorphism)

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

gf=idX,fg=idYg\circ f=id_X,f\circ g = id_Y

In this case we say that the morphism ff is invertible and that gg is the inverse of ff. We may also say that the objects XX and YY are isomorphic.

Lemma

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

Let’s consider another definition of category:

Definition

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

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

37


Definition(functors)

Let C\mathcal{C} and C\mathcal{C}' be categories. A functor FF from C\mathcal{C} to C\mathcal{C}', denoted F:CCF:\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(C)Ob(C)Ob(F):Ob(\mathcal{C})\rightarrow Ob(\mathcal{C}') which we sometimes denote simply by F:Ob(C)Ob(C)F:Ob(\mathcal{C})\rightarrow Ob(\mathcal{C}')

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

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

    which we sometimes denote simply by F:HomC(c,d)HomC(F(c),F(d))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 FF:

    F(idc)=idF(c)F(id_c)=id_{F(c)}

  2. Composition is preserved by FF:

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

Example: Consider the functor:

U:MonSetU:\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:PrOGrphP:\textbf{PrO}\rightarrow\textbf{Grph} such that for any preorder X=(X,)\mathcal{X}=(X,\leq), the graph P(X)P(\mathcal{X}) has vertices XX.

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:

HomCat(C,D)={F:CDF  is  a  functor}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,)(M,e,*) be a monoid. We consider it as a category M\mathcal{M} with one object, Ob(M)={Δ}Ob(\mathcal{M})=\{\Delta\}, and

HomM(Δ,Δ)=MHom_{\mathcal{M}}(\Delta,\Delta)=M

The identity morphism idΔid_{\Delta} serves as the monoid identity ee, and the composition formula

:HomM(Δ,Δ)×HomM(Δ,Δ)HomM(Δ,Δ)\circ:Hom_{\mathcal{M}}(\Delta,\Delta)\times Hom_{\mathcal{M}}(\Delta,\Delta)\rightarrow Hom_{\mathcal{M}}(\Delta,\Delta)

is given by :M×MM*: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:MonCati:\textbf{Mon}\rightarrow\textbf{Cat} with the following properties:

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

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

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

    induced by the functor ii, is a bijection.

Example: Let C\mathcal{C} be a category and xOb(C)x\in Ob(\mathcal{C}) an object. Let M=HomC(x,x)M=Hom_{\mathcal{C}}(x,x). Note that for any two elements f,gmf,g\in m we have fgMf\circ g\in M. Let M=(M,idx,)\mathcal{M}=(M,id_x,\circ). It is easy to check that M\mathcal{M} is a monoid; it is called the endomorphism monoid of xx in C\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:GrpCati:\textbf{Grp}\rightarrow\textbf{Cat} with the following properties

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

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

    HomGrp(G,G)HomCat(i(G),i