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"

# Preorders as categories

A preorder $(X,\leq)$ consists of a set $X$ and a binary relation. We can make from $(X,\leq)\in Ob(\textbf{PrO})$ a category $\mathcal{X}\in Ob(\textbf{Cat})$ as follows. Define $Ob(\mathcal{X})=X$ and for every two objects $x,y\in X$:

$$Hom_{\mathcal{X}}(x,y)=\begin{cases} \{"x\leq y"\}&x\leq y\\ \emptyset & x\not\leq y \end{cases}$$

"A preorder is a category in which every hom-set has either 0 or 1 element. A preorder morphism is just a functor between such categories."

# Natural transformations

"Naturality works like this: Using a function $f:X\rightarrow Y$ to convert a list of lists of $X$'s into a list of list of $Y$'s and then concatenating to get a simple list of $Y$'s does the same thing as first concatenating our list of lists of $X$'s into a simple list of $X$'s and then using our function $f$ to convert it into a list of $Y$'s***"***.

Example: Let $X=\{a,b,c\}$ and $Y=\{1,2,3\}$ and let $f:X\rightarrow Y$ assign $f(a)=1,f(b)=1,f(c)=2$. Our naturality condition says the following for any list of lists of $X$'s, in particular for $[[a,b],[a,c,a,b,c],[c]]$:

Keep these $\mu_X$ in mind in the following definition – they serve as the “components” of a natural transformation $List\circ List\rightarrow List$ of functors $\mathcal{C}\rightarrow\mathcal{D}$, where $\mathcal{C}=\mathcal{D}=\textbf{Set}$.

Example: Consider the categories $\mathcal{C}\cong[1]$ and $\mathcal{D}\cong[2]$ drawn below:

Consider the functors $F,G:[1]\rightarrow [2]$ where

$$F(0)=A,F(1)=B\\ G(0)=A,G(1)=C$$

Then the naturality square for $h$, the only morphism in $\mathcal{C}$, is

Of course it commutes.

The proof is quite self-evident…since the functors require to preserve associativity:

$$F(f_1\circ f_2)=F(f_1)\circ F(f_2)$$

# Vertical and horizontal composition

Proposition: Let $\mathcal{C}$ and $\mathcal{D}$ be categories. There exists a category, called the category of functors from $\mathcal{C}$ to $\mathcal{D}$ and denoted $Fun(\mathcal{C},\mathcal{D})$, whose objects are the functors $\mathcal{C}\rightarrow\mathcal{D}$ and whose morphisms are the natural transformations,

$$Hom_{Fun(\mathcal{C},\mathcal{D}))}(F,G)=\{\alpha:F\rightarrow G|\alpha\;is\;a\;natural\;transformation\}$$

We sometimes denote the category $Fun(\mathcal{C},\mathcal{D})$ by $\mathcal{D}^\mathcal{C}$.

Proof: First suppose that $\alpha$ is an isomorphism with inverse $\beta:G\rightarrow F$, and let $\beta_c:G(c)\rightarrow F(c)$ denote its $c$ component. We know that $\alpha\circ\beta=id_G$ and $\beta\circ\alpha=id_F$. So for every $c\in Ob(\mathcal{C})$, $\alpha_c\circ\beta_c=id_{G(c)}$ and $\beta_c\circ\alpha_c=id_{F(c)}$. So $\alpha_c$ is an isomorphism.

Second suppose that each $\alpha_c$ is an isomorphism with inverse $\beta_c$. We need to see that these components assemble into a natural transformation, i.e. the right square commutes:

We have

$$F(h)\circ \beta_c=\beta_{c'}\circ\alpha_{c'}\circ F(h)\circ\beta_c=\beta_{c'}\circ G(h)\circ\alpha_c\circ\beta_c=\beta_{c'}\circ G(h)$$

Qed.

---

Proof:

Page 158

# Database

# Basics

A database is a collection of tables, each table T of which consists of a set of columns and a set of rows.

The primary key column is tasked with uniquely identifying different rows, like the “ID” column in the left table.

The data columns house elementary data of a certain sort.

The foreign key columns link one table to another, creating a connection pattern between tables. Each foreign key column houses data that needs to be further unpacked. For example, the Source column is a foreign key to the supplier table.

What’s more, we could even say that data columns are specific kinds of foreign keys. That is, each data column constitutes a foreign key to some non-branching leaf table, which has no additional data.

# Schema

Consider the five tables following:

And the diagram:

The five tables from (3.13) and (3.15) are seen as five vertices.

The six foreign key columns from (3.13) and (3.15) are seen as six arrows, each points from a table to a foreign table.

The two rules below are seen as statements at the top of Display (3.16).

• Rule1. For every employee $e$, the manager of $e$ works in the same department that $e$ works in.
• Rule2. For every department $d$, the secretary of $d$ works in department $d$.

Think carefully about the diagram, then you can understand it quickly. Remember that there are only three types of columns: primary key column(ID), data columns (fist, last, name) and foreign key columns (manager, worksIn, secretary). And the element of foreign key columns is some table’s ID.

A congruence on $G$ is a relation $\simeq$ on $Path_G$ that has the following properties:

1. The relation $\simeq$ is an equivalence relation.
2. If $p\simeq q$ then $src(p)=src(q)$.
3. If $p\simeq q$ then $tgt(p)=tgt(q)$.
4. Suppose $p,q:b\rightarrow q$ are paths, and $m:a\rightarrow b$ is an arrow. If $p\simeq q$ then $mp\simeq mq$.
5. Suppose $p,q:a\rightarrow b$ are paths, and $n:b\rightarrow c$ is an arrow. If $p\simeq q$ then $pn\simeq qn$.

Any set of path equivalence declarations (PEDs) generates a congruence. We tend to elide the difference between a congruence and the set of PEDs that generates it.

Converting a schema $\mathcal{C}=(G,\simeq)$ into a table layout should be done as follows:

1. There should be a table for every vertex in $G$ and if the vertex is named, the table should have that name.
2. Each table should have a left-most column called ID, set apart from the other columns by a double vertical line.
3. To each arrow $a$ in $G$ having source vertex $s=src(a)$ and target vertex $t=tgt(a)$, there should be a foreign key column $a$ in table $s$, referring to table $t$; if the arrow $a$ is named column $a$ should have that name.

# Instances

# The category of instances on a database schema

# Categories and schemas are equivalent

Firstly, let’s think about Paths. Paths can be viewed as a functor $\textbf{Grph}\rightarrow\textbf{Grph}$ in that

$$Path(G)=(V,Path_G,\bar{src},\bar{tgt})\in Ob(\textbf{Grph})$$

and given a graph homomorphism $f:G\rightarrow G'$, every path in $G$ is sent under $f$ to a path in $G'$. So Paths is a functor.