Category Basics

It seems inevitable that, after one learned Haskell, there’s a good possibility she will become a victim of category theory. This is a series(hopefully) of notes about category theory.

Category Theory is the theory using formal method to study the semantics of cats a language that is spoken by mathematicians, just like Design Pattern is a language spoken by senior software engineers. Of course, the latter one reads less exotic and sometimes harmful.

Definition of Category

A category $C$ consists of:

• A collection of objects, $\text{Ob}(C)$;

• A collection of morphisms(arrows), $\text{Mor}(C)$;
  • For each morphism(arrow) $f$, a domain object $A$ and a codomain object $B$. $f:A\to B$ and $dom(f)=A,cod(f)=B$.
  • The collection of morphisms(arrows) between two objects: domain $A$ and codomain $B$, is denoted as $\text{Hom}(A,B)$.
• A binary operator $\circ$ called composition, satisfying:
  • For any pair of arrows $f:A\to B$ and $g:B\to C$, an arrow $g\circ f:A\to C$.
  • (Associativity) For any $f:A\to B,g:B\to C,h:C\to D$, we have $h\circ (g\circ f)=(h\circ g)\circ f$.
  • (Identity) For each object $A$, an identity arrow $i{d}_A$, such that for any arrow $f$, $i{d}_A\circ f=f=f\circ i{d}_A$.

Examples of Category

1. $$\mathbf{\text{Set}}$$

   • Objects: sets, $A$.

   • Arrows: total functions, $f:A\to B$.
   • Composition: function composition.
2. $$\mathbf{\text{Poset}}$$
   • Objects: partially-ordered sets, $(P,\le )$.
     • $P$ is a set.
     • $\le$ is a reflexive, transitive, antisymmetric relation on $P$.
   • Arrows: total order-preserving functions, $f:P\to Q$, such that $\mathrm{\forall }p,p^{\prime }\in P.p{\le }_P{p}^{\prime }\to f(p){\le }_{Q}f(p^{\prime })$.
   • Composition: function composition.
3. $$\mathbf{\text{Mon}}$$
   • Objects: monoids, $(M,\cdot )$.
     • $M$ is a set.
     • $\cdot$ is an associative binary operator on $M$.
     • an identity element $e\in M$ such that $\mathrm{\forall }m\in M.e\cdot m=m=m\cdot e$.
   • Arrows: monoid homomorphisms, $f:M\to N$, such that $\mathrm{\forall }m,m^{\prime }\in M.m{\cdot }_M{m}^{\prime }=f(m){\cdot }_{N}f(m^{\prime })$ and $f(e_M)=e_N$.
   • Composition: homomorphism composition.
4. $$\mathbf{\text{Grp}}$$
   • Objects: group, $(G,\cdot )$
     • $G$ is a set.
     • $\cdot$ is an associative binary operator.
     • an identity element $e\in G$ such that $\mathrm{\forall }g\in G.g\cdot e=g=e\cdot g$.
     • inverse: $\mathrm{\forall }g\in G.\mathrm{\exists }{g}^{-1}\in G.g\cdot g^{-1}=e=g^{-1}\cdot g$.
   • Arrows: group homomorphisms, $f:G\to H$, such that $\mathrm{\forall }g,g^{\prime }\in G.g{\cdot }_G{g}^{\prime }=f(g){\cdot }_{H}f(g^{\prime })$, $f(e_M)=e_N$
   • Composition: homomorphism composition.
5. $$\mathbf{\text{Ω-Alg}}$$
   • Objects: Ω-Algebras, $(|A|,a)$.
     • $|A|$ is a set called carrier.
     • $a:\sum _{\omega \in \mathrm{\Omega }}|A{|}^{ar(\omega )}\to |A|$ is an interpretation.
       • $\mathrm{\Omega }$ is a set of operator (signature).
       • $ar(\omega )$ is the arity of $\omega$.
   • Arrows: $\mathrm{\Omega }$-homomorphisms, $h:|A|\to |B|$, such that $\mathrm{\forall }\omega \in \mathrm{\Omega }.h(a(x_1,...,x_{ar(\omega )}))=b(h(x_1),...,h(x_{ar(\omega )}))$.
   • Composition: homomorphism composition.

More examples:

• Categorical Logic

  • Objects: formulas, $A$.

  • Arrows: proofs, $f:A\to B$.

  • Composition: transitivity of implication. $\begin{array}{c}\begin{array}{ccc}f:A\to B& & g:B\to C\end{array}\\ g\circ f:A\to C\end{array}$

• Functional Programming Language
  • Objects: types, $T$.
  • Arrows: functions, $f:T\to U$
  • Composition: function composition
• Dual Category ${\mathbf{\text{C}}}^{\mathbf{\text{op}}}$ of $\mathbf{\text{C}}$
  • Objects: $\text{Ob}(\mathbf{\text{C}})$
  • Arrows: opposite of arrows in $\mathbf{\text{C}}$.
    • $\mathrm{\forall }f:A\to B$ from $\mathbf{\text{C}}$, we have $f^{op}:B\to A$ in ${\mathbf{\text{C}}}^{\mathbf{\text{op}}}$
  • Composition: trivial.
• Product category $\mathbf{\text{C}}\times \mathbf{\text{D}}$
  • Objects: objects pairs $(A,B)$ where $A$ is a $\mathbf{\text{C}}$-object and $B$ is a $\mathbf{\text{D}}$-object.
  • Arrows: arrows pairs $(f,g)$ where $f$ is a $\mathbf{\text{C}}$-arrow and $g$ is an $\mathbf{\text{D}}$-arrow.
  • Composition: pairwise composition, $(f,g)\circ (h,i)=(f\circ h,g\circ i)$.
• Subcategory $\mathbf{\text{B}}$ of $\mathbf{\text{C}}$
  • Objects: each $\mathbf{\text{B}}$-object in is a $\mathbf{\text{C}}$-object
  • Arrows: for all $\mathbf{\text{B}}$-objects $B$ and $B^{\prime }$, ${\text{Hom}}_B(B,B^{\prime })\subseteq {\text{Hom}}_C(B,B^{\prime })$
  • Composition: same as $\mathbf{\text{C}}$

Commutative Diagrams

Definition

A diagram in a category $\mathbf{\text{C}}$ is a collection of vertices and directed edges, consistently labeled with objects and arrows of $\mathbf{\text{C}}$.

A diagram is said to commute if for every pair of objects $X,Y$, all the paths from $X$ to $Y$ are equal.

Example

This diagram commutes:

• In the inner left squre: $m\circ g=G\circ l$
• In the inner right squre: $r\circ h=H\circ m$
• In the outer rectangle: $r\circ h\circ g=H\circ G\circ l$