Category Theory [.1cm] Midlands Graduate School 2023 [.5cm] Exercise 1 (2 April)

Definition 1 (category). A category C consists of:

a collection C₀ of objects, written X,Y,Z,…
for any two objects X and Y , a collection C(X,Y ) of morphisms, written f,g,h,…
a composition operation: for f ∈ C(X,Y ) and g ∈ C(Y,Z), we have g ∘ f ∈C(X,Z)
for any object X, the identity morphism id_X ∈C(X,X)

such that:

Every identity morphism is left- and right-neutral. This means that, for f ∈C(X,Y ), we have f ∘ id_X = f and id_Y ∘ f = f.
Composition is associative, i.e. (h ∘ g) ∘ f = h ∘ (g ∘ f).

Definition 2 (initial and terminal object). An object X in a category C is initial if, for every object Y , there is exactly one morphism from X to Y . This means that C(X,Y ) is the one-element set. An object Z is terminal if, for every object Y , there is exactly one morphism from Y to Z, i.e., C(Y,Z) is the one-element set.

Definition 3 (isomorphism). A morphism f ∈C(X,Y ) is an isomorphism if there is a morphism g ∈C(Y,X) such that g ∘ f = id_X and f ∘ g = id_Y.

Exercise 1: The free category on a directed multigraph

Note that the edges are directed, i.e., E(a,b) is not necessarily the same as E(b,a), and many parallel edges are allowed.

Let G = (V,E) be a directed multigraph. The free category on G, (here) written F_G, has V as objects and a morphism F_G(X,Y ) is a sequence of consecutive edges, starting in X and ending in Y .

For which G does F_G have an initial object? And when does F_G have a terminal object?

Exercise 2: The category REL

The objects of the category REL are sets. For sets X and Y , an element of REL(X,Y ) is a relation between X and Y , i.e., a subset R ⊆ (X × Y ). The composition of relations R ⊆ (X × Y ) and S ⊆ (Y × Z) is given by

Bonus Exercise: The (almost-)category SPAN

The objects of SPAN are sets. A morphism between sets X and Y consists of a set Z together with a function f : Z → X and a function g : Z → Y .

The composition operation works in a similar way as for REL, but we don’t need an existential quantifier this time. Can you make this operation precise?

Can you prove associativity? Can you define identities and prove that SPAN is a category? What works or fails? (Hint: It only almost works. SPAN is a structure that is slightly weaker than a category, namely a bicategory.)

CATEGORY THEORY
MIDLANDS GRADUATE SCHOOL 2023

EXERCISE 1 (2 APRIL)

Reminder

Exercise 1: The free category on a directed multigraph

Exercise 2: The category REL

Bonus Exercise: The (almost-)category SPAN

CATEGORY THEORY MIDLANDS GRADUATE SCHOOL 2023 EXERCISE 1 (2 APRIL)

Reminder

Exercise 1: The free category on a directed multigraph

Exercise 2: The category REL

Bonus Exercise: The (almost-)category SPAN

CATEGORY THEORY
MIDLANDS GRADUATE SCHOOL 2023

EXERCISE 1 (2 APRIL)