Fun Stuff · Mathematics

Category Theory Cheat Post

paul

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

.

Advertisements

Published by paul

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. ( Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s