Category Theory Cheat Post

After learning Haskell I finally decided to jump the train and start learning Category Theory with the help of the book Conceptual Mathematics – A first introduction to categories. I greatly encourage you to do the same, especially if you are a self-taught programmer.

The following is a simple cheat sheet that is meant to help me (and maybe you?) remember all those new words and constructs. Please poke me if you find any errors or have an improvement suggestion.

Basics

Associative

The order of operator application does not matter. $a * (b * c) = (a * b) *c$

.

Commutative

The order of the operands does not matter. $a * b = b * a$

.

Idempotent [idem + potence = (same + power)]

The endomorphism $A\xrightarrow{e}A$ is idempotent under composition if $e \circ e = e$

.

Involution

The automorphism $A\xrightarrow{\theta}A$ is an involution of A if $\theta \circ \theta = 1_A$

.

Category

What makes a Category?
– Objects
– Morphisms (maps)
– For each object in $A$ an identity map $1_A$  must exist.
– For each pair of maps $A\xrightarrow{f}B$ and $B\xrightarrow{g}C$ a composite map $A\xrightarrow{g \circ f}C$ must exist.

– Composition $\circ$ must follow the identity and associative laws: $1_B\circ f = f$ $f\circ 1_A = f$ $a\circ (b\circ c) = (a\circ b)\circ c$

.

Morphisms

Monomorphism (injective) [monos = one] – distinctive
It maps distinct objects onto distinct objects. The codomain is at least as large as the domain. $x \not= y\implies f(x) \not= f(y)$

– left cancellative $f\circ g_1 = f\circ g_2\implies g_1=g_2$ with $Z\xrightarrow{g_1, g_2} A\xrightarrow{f} B$

.

Split Monomorphism

A monomorphism $A\xrightarrow{f}B$ which has a left inverse $B\xrightarrow{r}A$ for which $r\circ f = 1_A$, i.e. a retraction. $A\xrightarrow{f}B\xrightarrow{r} A$

.

Epimorphism (surjective) [epis = against] – covering
All objects of the codomain are hit at least once. The domain is at least as large as the codomain. $\forall b\in B\exists a\in A (f(a)=b)$

– right cancellative $h_1\circ f = h_2\circ f\implies h_1=h_2$ with $A\xrightarrow{f} B\xrightarrow{h_1, h_2} C$

.

Split Epimorphism

An epimorphism $A\xrightarrow{f}B$ which has a right inverse $B\xrightarrow{s} A$ for which $f\circ s = 1_B$, i.e. a section. $B\xrightarrow{s}A\xrightarrow{f}B$

.

Isomorphism(bijective) [isos = equal]

– is a monomorphism and epimorphism $A\cong B$ domain and codomain have the ‘same size’
– distinctive
– invertible $A\xrightarrow{f}B\xrightarrow{f^{-1}}A$ with $f\circ f^{-1} = 1_B$ and $f^{-1}\circ f = 1_A$

.

Automorphism[auto = self]

– is an isomorphism $A\xrightarrow{f}A$
– also called permutation

.

Homomorphism [homos = same]

– structure preserving map
– if $(G, *)$ and $(H, *')$ are groups, then f is a homomorphism if $f(g * h) = f(g) *' f(h)$

.

Endomorphism [endos = inside]

– is a homomorphism $A\xrightarrow{f}A$

.

Constant map $\exists b\in B \forall a \in A(f(a) = b)$
A map $A\xrightarrow{f}B$ is called constant if all elements of A are send onto the same element of B.

.

Division of maps

Determination or extension $A\xrightarrow{f}B\xrightarrow{g?}C\xleftarrow{h = g\circ f}A$
If it has a solution g, we say h is ‘determined by’ f or h ‘depends only on’ f.

.

Retraction

Special case of the determination problem $A\xrightarrow{f}B\xrightarrow{r?}A\xleftarrow{1_A}A$ in which $h = 1_A$ and $r\circ f = 1_A$
– is an epimorphism
– left inverse of $f$

.

Choice or lifting $A\xrightarrow{f?}B\xrightarrow{g}C\xleftarrow{h = g\circ f}A$

.

Section

Special case of the choice problem $B\xrightarrow{s?}A\xrightarrow{f}B\xleftarrow{1_B}B$ in which $h = 1_B$ and $f\circ s = 1_B$
– is a monomorphism
– right inverse of $f$

.