Introduction to Categories and Categorical Logic

T

he aim of these notes is to provide a succinct, accessible introduction to some of the basic ideas of category theory and categorical logic. The notes are based on a lecture course given at Oxford over the past few years. They contain numerous exercises, and hopefully will prove useful for self-study by those seeking a first introduction to the subject, with fairly minimal prerequisites. The coverage is by no means comprehensive, but should provide a good basis for further study; a guide to further reading is included.

The main prerequisite is a basic familiarity with the elements of discrete mathematics: sets, relations and functions. An Appendix contains a summary of what we will need, and it may be useful to review this first. In addition, some prior exposure to abstract algebra — vector spaces and linear maps, or groups and group homomorphisms — would be helpful.

Why study categories — what are they good for? We can offer a range of answers for readers coming from different backgrounds:

For mathematicians: category theory organises your previous mathematical experience in a new and powerful way, revealing new connections and structure, and allows you to “think bigger thoughts”.

For computer scientists: category theory gives a precise handle on important notions such as compositionality, abstraction, representation-independence, genericity and more. Otherwise put, it provides the fundamental mathematical structures underpinning many key programming concepts.

For logicians: category theory gives a syntax-independent view of the fundamental structures of logic, and opens up new kinds of models and interpretations.

For philosophers: category theory opens up a fresh approach to structuralist foundations of mathematics and science; and an alternative to the traditional focus on set theory.

For physicists: category theory offers new ways of formulating physical theories in a structural form. There have inter alia been some striking recent applications to quantum information and computation.

Category theory can be seen as a “generalised theory of functions”, where the focus is shifted from the pointwise, set-theoretic view of functions, to an abstract view of functions as arrows.

Let us briefly recall the arrow notation for functions between sets.A review of basic ideas about sets, functions and relations, and some of the notation we will be using, is provided in Appendix A. A function $f$ with domain $X$ and codomain $Y$ is denoted by: $f:X\rightarrow Y$.

The fundamental operation on functions is composition: if $f:X\rightarrow Y$ and $g:Y\rightarrow Z$, then we can define $g\circ f:X\rightarrow Z$ by $g\circ f(x):=g(f(x))$.We shall use the notation “:=” for “is defined to be” throughout these notes. Note that, in order for the composition to be defined, the codomain of $f$ must be the same as the domain of $g$.

Moreover, for each set $X$ there is an identity function on $X$, which is denoted by:

These operations are governed by the associativity law and the unit laws. For $f:X\rightarrow Y$, $g:Y\rightarrow Z$, $h:Z\rightarrow W$:

Notice that these equations are formulated purely in terms of the algebraic operations on functions, without any reference to the elements of the sets $X$, $Y$, $Z$, $W$. We will refer to any concept pertaining to functions which can be defined purely in terms of composition and identities as arrow-theoretic. We will now take a first step towards learning to “think with arrows” by seeing how we can replace some familiar definitions couched in terms of elements by arrow-theoretic equivalents; this will lead us towards the notion of category.

We say that a function $f:X\longrightarrow Y$ is:

Note that injectivity and surjectivity are formulated in terms of elements, while epic and monic are arrow-theoretic.

Proof: We show 1. Suppose $f:X\rightarrow Y$ is injective, and that $f\circ g=f\circ h$, where $g,h:Z\rightarrow X$. Then, for all $z\in Z$:

Since $f$ is injective, this implies $g(z)=h(z)$. Hence we have shown that

and so we can conclude that $g=h$. So $f$ injective implies $f$ monic. For the converse, fix a one-element set $\boldsymbol{1}=\{\bullet\}$. Note that elements $x\in X$ are in 1–1 correspondence with functions $\bar{x}:\boldsymbol{1}\rightarrow X$, where $\bar{x}(\bullet):=x$. Moreover, if $f(x)=y$ then $\bar{y}=f\circ\bar{x}$ . Writing injectivity in these terms, it amounts to the following.

Thus we see that being injective is a special case of being monic. $\blacksquare$

Show that $f:X\rightarrow Y$ is surjective iff it is epic.

1.2 Categories Defined

A collection $\mathsf{Ob}(\mathcal{C})$ of objects. Objects are denoted by $A$, $B$, $C$, etc.

A collection $\mathsf{Ar}(\mathcal{C})$ of arrows (or morphisms). Arrows are denoted by $f$, $g$, $h$, etc.

Mappings $\mathsf{dom},\mathsf{cod}:\mathsf{Ar}(\mathcal{C})\rightarrow\mathsf{Ob}(\mathcal{C})$, which assign to each arrow $f$ its domain $\mathsf{dom}(f)$ and its codomain $\mathsf{cod}(f)$. An arrow $f$ with domain $A$ and codomain $B$ is written $f:A\rightarrow B$. For each pair of objects $A$, $B$, we define the set

We refer to $\mathcal{C}(A,B)$ as a hom-set. Note that distinct hom-sets are disjoint.

For any triple of objects $A$, $B$, $C$, a composition map

$c_{A,B,C}(f,g)$ is written $g\circ\!f$ (or sometimes $f;g$). Diagrammatically:

For each object $A$, an identity arrow $\mspace{1.5mu}\mathsf{id}_{A}:A\rightarrow A$.

The above must satisfy the following axioms.

whenever the domains and codomains of the arrows match appropriately so that the compositions are well-defined. $\blacktriangle$

1.3 Diagrams in Categories

Diagrammatic reasoning is an important tool in category theory. The basic cases are commuting triangles and squares. To say that the following triangle commutes

is exactly equivalent to asserting the equation $g\circ f=h$. Similarly, to say that the following square commutes

means exactly that $g\circ f=k\circ h$. For example, the equations

can be expressed by saying that the following diagrams commute.

As these examples illustrate, most of the diagrams we shall use will be “pasted together” from triangles and squares: the commutation of the diagram as a whole will then reduce to the commutation of the constituent triangles and squares.

We turn to the general case. The formal definition is slightly cumbersome; we give it anyway for reference.

We define a graph to be a collection of vertices and directed edges, where each edge $e:v\rightarrow w$ has a specified source vertex $v$ and target vertex $w$. Thus graphs are like categories without composition and identities.This would be a “multigraph” in normal parlance, since multiple edges between a given pair of vertices are allowed. A diagram in a category $\mathcal{C}$ is a graph whose vertices are labelled with objects of $\mathcal{C}$ and whose edges are labelled with arrows of $\mathcal{C}$, such that, if $e:v\rightarrow w$ is labelled with $f:A\rightarrow B$, then we must have $v$ labelled by $A$ and $w$ labelled by $B$. We say that such a diagram commutes if any two paths in it with common source and target, and at least one of which has length greater than 1, are equal. That is, given paths

To illustrate this definition, to say that the following diagram commutes

amounts to the assertion that $f\circ e=g\circ e$ ; it does not imply that $f=g$.

1.4 Examples

Before we proceed to our first examples of categories, we shall present some background material on partial orders, monoids and topologies, which will provide running examples throughout these notes.

A partial order is a structure $(P,\leq)$ where $P$ is a set and $\leq$ is a binary relation on $P$ satisfying:

$x\leq y\;\wedge y\leq x\;\;\Rightarrow\;\;x=y$ (Antisymmetry)

$x\leq y\;\wedge\;y\leq z\;\;\Rightarrow\;\;x\leq z$ (Transitivity)

If $P$, $Q$ are partial orders, a map $h:P\rightarrow Q$ is a partial order homomorphism (or monotone function) if:

Note that homomorphisms are closed under composition, and that identity maps are homomorphisms.

A monoid is a structure $(M,\cdot,1)$ where $M$ is a set,

is a binary operation, and $1\in M$, satisfying the following axioms.

If $M$, $N$ are monoids, a map $h:M\rightarrow N$ is a monoid homomorphism if

Suppose that $G$ and $H$ are groups (and hence monoids), and that $h:G\rightarrow H$ is a monoid homomorphism. Prove that $h$ is a group homomorphism.

A topological space is a pair $(X,T_{X})$ where $X$ is a set, and $T_{X}$ is a family of subsets of $X$ such that

if $U,V\in T_{X}$ then $U\cap V\in T_{X}$,

if $\{U_{i}\}_{i\in I}$ is any family in $T_{X}$, then $\bigcup_{i\in I}U_{i}\in T_{X}$ .

A continuous map $f:(X,T_{X})\rightarrow(Y,T_{Y})$ is a function $f:X\rightarrow Y$ such that, for all $U\in T_{Y}$, $f^{-1}(U)\in T_{X}$. Let us now see some first examples of categories.

Any kind of mathematical structure, together with structure preserving functions, forms a category. E.g.

$\text{{Vect}}_{k}$ (vector spaces over a field $k$, and linear maps)

Pos (partially ordered sets and monotone functions)

Top (topological spaces and continuous functions)

Rel: objects are sets, arrows $R:X\rightarrow Y$ are relations $R\subseteq X\times Y$. Relational composition:

Let $k$ be a field (for example, the real or complex numbers). Consider the following category $\text{{Mat}}_{k}$. The objects are natural numbers. A morphism $M:\mathbf{n}\rightarrow\mathbf{m}$ is an $\mathbf{n}\times\mathbf{m}$ matrix with entries in $k$. Composition is matrix multiplication, and the identity on $\mathbf{n}$ is the $\mathbf{n}\times\mathbf{n}$ diagonal matrix.

Monoids are one-object categories. Arrows correspond to the elements of the monoid, with the monoid operation being arrow-composition and the monoid unit being the identity arrow.

A category in which for each pair of objects $A$, $B$ there is at most one morphism from $A$ to $B$ is the same thing as a preorder, i.e. a reflexive and transitive relation.

Note that our first class of examples illustrate the idea of categories as mathematical contexts; settings in which various mathematical theories can be developed. Thus for example, Top is the context for general topology, Grp is the context for group theory, etc.

On the other hand, the last two examples illustrate that many important mathematical structures themselves appear as categories of particular kinds. The fact that two such different kinds of structures as monoids and posets should appear as extremal versions of categories is also rather striking.

This ability to capture mathematics both “in the large” and “in the small” is a first indication of the flexibility and power of categories.

Check that Mon, $\textbf{Vect}_{k}$, Pos and Top are indeed categories.

Check carefully that monoids correspond exactly to one-object categories. Make sure you understand the difference between such a category and Mon. (For example: how many objects does Mon have?)

Check carefully that preorders correspond exactly to categories in which each homset has at most one element. Make sure you understand the difference between such a category and Pos. (For example: how big can homsets in Pos be?)

1.5 First Notions

Many important mathematical notions can be expressed at the general level of categories.

Let $\mathcal{C}$ be a category. A morphism $f:X\rightarrow Y$ in $\mathcal{C}$ is: $\bullet$ monic (or a monomorphism) if $f\circ g=f\circ h\;\Longrightarrow\;g=h$ , $\bullet$ epic (or an epimorphism) if $g\circ f=h\circ f\;\Longrightarrow\;g=h$ . An isomorphism in $\mathcal{C}$ is an arrow $i:A\rightarrow B$ such that there exists an arrow $j:B\rightarrow A$ — the inverse of $i$ — satisfying

We denote isomorphisms by $i:A\xrightarrow{\cong}B$, and write $i^{-1}$ for the inverse of $i$. We say that $A$ and $B$ are isomorphic, $A\cong B$, if there exists some $i:A\xrightarrow{\cong}B$.

Show that the inverse, if it exists, is unique.

Show that $\cong$ is an equivalence relation on the objects of a category.

As we saw previously, in Set monics are injections and epics are surjections. On the other hand, isomorphisms in Set correspond exactly to bijections, in Grp to group isomorphisms, in Top to homeomorphisms, in Pos to order isomorphisms, etc.

Thus we have at one stroke captured the key notion of isomorphism in a form which applies to all mathematical contexts. This is a first taste of the level of generality which category theory naturally affords.

We have already identified monoids as one-object categories. We can now identify groups as exactly those one-object categories in which every arrow is an isomorphism. This also leads to a natural generalisation, of considerable importance in current mathematics: a groupoid is a category in which every morphism is an isomorphism.

The directionality of arrows within a category $\mathcal{C}$ can be reversed without breaking the conditions of being a category; this yields the notion of opposite category.

Given a category $\mathcal{C}$, the opposite category $\mathcal{C}^{\mathsf{op}}$ is given by taking the same objects as $\mathcal{C}$, and

Composition and identities are inherited from $\mathcal{C}$. $\blacktriangle$

in $\mathcal{C}^{\mathsf{op}}$, this means

in $\mathcal{C}$, so composition $g\circ f$ in $\mathcal{C}^{\mathsf{op}}$ is defined as $f\circ g$ in $\mathcal{C}$!

Consideration of opposite categories leads to a principle of duality: a statement $S$ is true about $\mathcal{C}$ if and only if its dual (i.e. the one obtained from $S$ by reversing all the arrows) is true about $\mathcal{C}^{\mathsf{op}}$. For example,

Indeed, $f$ is monic in $\mathcal{C}^{\mathsf{op}}$ iff for all $g,h:C\rightarrow B$ in $\mathcal{C}^{\mathsf{op}}$,

iff for all $g,h:B\rightarrow C$ in $\mathcal{C}$,

iff $f$ is epic in $\mathcal{C}$. We say that monic and epic are dual notions.

Another way to obtain new categories from old ones is by restricting their objects or arrows.

Let $\mathcal{C}$ be a category. Suppose that we are given collections

We say that $\mathcal{D}$ is a subcategory of $\mathcal{C}$ if

and hence $\mathcal{D}$ itself is a category. In particular, $\mathcal{D}$ is:

A full subcategory of $\mathcal{C}$ if for any $A,B\in\mathsf{Ob}(\mathcal{D})$, $\mathcal{D}(A,B)=\mathcal{C}(A,B)$.

A lluf subcategory of $\mathcal{C}$ if $\mathsf{Ob}(\mathcal{D})=\mathsf{Ob}(\mathcal{C})$. $\blacktriangle$

For example, Grp is a full subcategory of Mon (by Exercise 0.1.5), and Set is a lluf subcategory of Rel.

We close this section with some very basic examples of categories.

How many categories $\mathcal{C}$ with $\mathsf{Ob}(\mathcal{C})=\{\bullet\}$ are there? (Hint: what do such categories correspond to?)

1.6 Exercises

Consider the following properties of an arrow $f$ in a category $\mathcal{C}$.

$f$ is split monic if for some $g$, $g\circ f$ is an identity arrow.

$f$ is split epic if for some $g$, $f\circ g$ is an identity arrow.

Prove that if $f$ and $g$ are arrows such that $g\circ f$ is monic, then $f$ is monic.

Prove that, if $f$ is split epic then it is epic.

Prove that, if $f$ and $g\circ f$ are iso then $g$ is iso.

Prove that, if $f$ is monic and split epic then it is iso.

In the category $\mathbf{Mon}$ of monoids and monoid homomorphisms, consider the inclusion map

of natural numbers into the integers. Show that this arrow is both monic and epic. Is it an iso?

The Axiom of Choice in Set Theory states that, if $\{X_{i}\}_{i\in I}$ is a family of non-empty sets, we can form a set $X=\{x_{i}\mid i\in I\}$ where $x_{i}\in X_{i}$ for all $i\in I$.

Show that in $\mathbf{Set}$ an arrow which is epic is split epic. Explain why this needs the Axiom of Choice.

Is it always the case that an arrow which is epic is split epic? Either prove that it is, or give a counter-example.

Give a description of partial orders as categories of a special kind.

2 Some Basic Constructions

We shall now look at a number of basic constructions which appear throughout mathematics, and which acquire their proper general form in the language of categories.

A first such example is that of initial and terminal objects. While apparently trivial, they are actually both important and useful, as we shall see in the sequel.

An object $I$ in a category $\mathcal{C}$ is initial if, for every object $A$, there exists a unique arrow from $I$ to $A$, which we write $\iota_{A}:I\rightarrow A$. A terminal object in $\mathcal{C}$ is an object $T$ such that, for every object $A$, there exists a unique arrow from $A$ to $T$, which we write $\tau_{A}:A\rightarrow T$. $\blacktriangle$

Note that initial and terminal objects are dual notions: $T$ is terminal in $\mathcal{C}$ iff it is initial in $\mathcal{C}^{\mathsf{op}}$. We sometimes write $\mathbf{1}$ for the terminal object and $\mathbf{0}$ for the initial one. Note also the assertions of unique existence in the definitions. This is one of the leitmotifs of category theory; we shall encounter it again in a conceptually deeper form in section 0.5.

Let us examine initial and terminal objects in our standard example categories.

In Set, the empty set is an initial object while any one-element set $\{\bullet\}$ is terminal.

In Pos, the poset $(\varnothing,\varnothing)$ is an initial object while $(\{\bullet\},\{(\bullet,\bullet)\})$ is terminal.

In Top, the space $(\varnothing,\{\varnothing\})$ is an initial object while $(\{\bullet\},\{\varnothing,\{\bullet\}\})$ is terminal.

In $\text{{Vect}}_{k}$, the one-element space $\{0\}$ is both initial and terminal.

In a poset, seen as a category, an initial object is a least element, while a terminal object is a greatest element.

Verify these claims. In each case, identify the canonical arrows.

Identify the initial and terminal objects in Rel.

Suppose that a monoid, viewed as a category, has either an initial or a terminal object. What must the monoid be?

We shall now establish a fundamental fact: initial and terminal objects are unique up to (unique) isomorphism. As we shall see, this is characteristic of all such “universal” definitions. For example, the apparent arbitrariness in the fact that any singleton set is a terminal object in Set is answered by the fact that what counts is the property of being terminal; and this suffices to ensure that any two concrete objects having this property must be isomorphic to each other.

The proof of the proposition, while elementary, is a first example of distinctively categorical reasoning.

If $I$ and $I^{\prime}$ are initial objects in the category $\mathcal{C}$ then there exists a unique isomorphism $I\stackrel{{\scriptstyle\cong}}{{\longrightarrow}}I^{\prime}$.

Proof: Since $I$ is initial and $I^{\prime}$ is an object of $\mathcal{C}$, there is a unique arrow $\iota_{I^{\prime}}:I\rightarrow I^{\prime}$. We claim that $\iota_{I^{\prime}}$ is an isomorphism. Since $I^{\prime}$ is initial and $I$ is an object in $\mathcal{C}$, there is an arrow $\iota^{\prime}_{I}:I^{\prime}\rightarrow I$. Thus we obtain $\iota_{I^{\prime}};\iota^{\prime}_{I}:I\rightarrow I$, while we also have the identity morphism $\mspace{1.5mu}\mathsf{id}_{I}:I\rightarrow I$. But $I$ is initial and therefore there exists a unique arrow from $I$ to $I$, which means that $\iota_{I^{\prime}};\iota^{\prime}_{I}=\mspace{1.5mu}\mathsf{id}_{I}$. Similarly, $\iota^{\prime}_{I};\iota_{I^{\prime}}=\mspace{1.5mu}\mathsf{id}_{I^{\prime}}$, so $\iota_{I^{\prime}}$ is indeed an isomorphism. $\blacksquare$ Hence, initial objects are “unique up to (unique) isomorphism”, and we can (and do) speak of the initial object (if any such exists). Similarly for terminal objects.

Let $\mathcal{C}$ be a category with an initial object $\mathbf{0}$. For any object $A$, show the following.

If $A\cong\mathbf{0}$ then $A$ is an initial object.

If there exists a monomorphism $f:A\rightarrow\mathbf{0}$ then $f$ is an iso, and hence $A$ is initial.

2.2 Products and Coproducts

We now consider one of the most common constructions in mathematics: the formation of “direct products”. Once again, rather than giving a case-by-case construction of direct products in each mathematical context we encounter, we can express once and for all a general notion of product, meaningful in any category — and such that, if a product exists, it is characterised uniquely up to unique isomorphism, just as for initial and terminal objects. Given a particular mathematical context, i.e. a category, we can then verify whether on not the product exists in that category. The concrete construction appropriate to the context will enter only into the proof of existence; all of the useful properties of the product follow from the general definition. Moreover, the categorical notion of product has a normative force; we can test whether a concrete construction works as intended by verifying that it satisfies the general definition.

In set theory, the cartesian product is defined in terms of the ordered pair:

It turns out that ordered pairs can be defined in set theory, e.g. as

Note that in no sense is such a definition canonical. The essential properties of ordered pairs are:

We can retrieve the first and second components $x$, $y$ of the ordered pair $(x,y)$, allowing projection functions to be defined:

The information about first and second components completely determines the ordered pair:

The categorical definition expresses these properties in arrow-theoretic terms, meaningful in any category.

Let $A$, $B$ be objects in a category $\mathcal{C}$. An $A$,$B$–pairing is a triple $(P,p_{1},p_{2})$ where $P$ is an object, $p_{1}:P\rightarrow A$ and $p_{2}:P\rightarrow B$. A morphism of $A$,$B$–pairings

is a morphism $f:P\rightarrow Q$ in $\mathcal{C}$ such that $q_{1}\circ f=p_{1}$ and $q_{2}\circ f=p_{2}$ , i.e. the following diagram commutes.

The $A$,$B$–pairings form a category $\mathbf{Pair}(A,B)$. We say that $(A\times B,\pi_{1},\pi_{2})$ is a product of $A$ and $B$ if it is terminal in $\mathbf{Pair}(A,B)$. $\blacktriangle$

Verify that $\mathbf{Pair}(A,B)$ is a category.

Note that products are specified by triples $A\overset{\pi_{1}}{\longleftarrow}A\times B\overset{\pi_{2}}{\longrightarrow}B$, where $\pi_{i}$’s are called projections. For economy (and if projections are obvious) we may say that $A\times B$ is the product of $A$ and $B$. We say that $\mathcal{C}$ has (binary) products if each pair of objects $A,B$ has a product in $\mathcal{C}$. A direct consequence of the definition, by Proposition 0.2.5, is that if products exist, they are unique up to (unique) isomorphism.

Unpacking the uniqueness condition from $\mathbf{Pair}(A,B)$ back to $\mathcal{C}$ we obtain a more concise definition of products which we use in practice.

Let $A,B$ be objects in a category $\mathcal{C}$. A product of $A$ and $B$ is an object $A\times B$ together with a pair of arrows $A\overset{\pi_{1}}{\longleftarrow}A\times B\overset{\pi_{2}}{\longrightarrow}B$ such that for every triple $A\overset{f}{\longleftarrow}C\overset{g}{\longrightarrow}B$ there exists a unique morphism

such that the following diagram commutes.

We call $\langle f,g\rangle$ the pairing of $f$ and $g$.

Note that the above diagram features a dashed arrow. Our intention with such diagrams is always to express the following idea: if the undashed part of the diagram commutes, then there exists a unique arrow (the dashed one) such that the whole diagram commutes. In any case, we shall always spell out the intended statement explicitly.

We look at how this definition works in our standard example categories.

In Set, products are the usual cartesian products.

In Pos, products are cartesian products with the pointwise order.

In Top, products are cartesian products with the product topology.

In $\text{{Vect}}_{k}$, products are direct sums.

In a poset, seen as a category, products are greatest lower bounds.

The following proposition shows that the uniqueness of the pairing arrow can be specified purely equationally, by the equation:

For any triple $A\overset{\pi_{1}}{\longleftarrow}A\times B\overset{\pi_{2}}{\longrightarrow}B$ the following statements are equivalent.

For any triple $A\overset{f}{\longleftarrow}C\overset{g}{\longrightarrow}B$ there exists a unique morphism $\langle f,g\rangle:C\rightarrow A\times B$ such that $\pi_{1}\circ\langle f,g\rangle=f$ and $\pi_{2}\circ\langle f,g\rangle=g$.

For any triple $A\overset{f}{\longleftarrow}C\overset{g}{\longrightarrow}B$ there exists a morphism $\langle f,g\rangle:C\rightarrow A\times B$ such that $\pi_{1}\circ\langle f,g\rangle=f$ and $\pi_{2}\circ\langle f,g\rangle=g$, and moreover, for any $h:C\rightarrow A\times B$, $h=\langle\pi_{1}\circ h,\pi_{2}\circ h\rangle$.

Proof: For (I)$\Rightarrow$(II), take any $h:C\rightarrow A\times B$ ; we need to show $h=\langle\pi_{1}\circ h,\pi_{2}\circ h\rangle$. We have

and hence, by (I), there exists unique $k:C\rightarrow A\times B$ such that

Note now that ($*$) holds both for $k:=h$ and $k:=\langle\pi_{1}\circ h,\pi_{2}\circ h\rangle$, the latter because of (I). Hence, $h=\langle\pi_{1}\circ h,\pi_{2}\circ h\rangle$. For (II)$\Rightarrow$(I), take any triple $A\overset{f}{\longleftarrow}C\overset{g}{\longrightarrow}B$. By (II), we have that there exists an arrow $\langle f,g\rangle:C\rightarrow A\times B$ such that $\pi_{1}\circ\langle f,g\rangle=f$ and $\pi_{2}\circ\langle f,g\rangle=g$. We need to show it is the unique such. Let $k:C\rightarrow A\times B$ s.t.

as required. $\blacksquare$ In the following proposition we give some useful properties of products. First, let us introduce some notation for arrows: given $f_{1}:A_{1}\rightarrow B_{1}$, $f_{2}:A_{2}\rightarrow B_{2}$, define

For any $f:A\rightarrow B$, $g:A\rightarrow C$, $h:A^{\prime}\rightarrow A$, and any $p:B\rightarrow B^{\prime}$, $q:C\rightarrow C^{\prime}$,

$\langle f,g\rangle\circ h=\langle f\circ h,g\circ h\rangle$,

$(p\times q)\circ\langle f,g\rangle=\langle p\circ f,q\circ g\rangle.$

The notion of products can be generalised to arbitrary arities as follows. A product for a family of objects $\{A_{i}\}_{i\in I}$ in a category $\mathcal{C}$ is an object $P$ and morphisms

such that, for all objects $B$ and arrows

such that, for all $i\in I$, the following diagram commutes.

$\scriptstyle{g}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="1" displaystyle="false"><msub><mi>f</mi><mi>i</mi></msub></mstyle></mrow><annotation encoding="application/x-tex">\scriptstyle{f_{i}}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6222em;vertical-align:-0.1361em;"></span><span class="mord mtight sizing reset-size6 size3"><span class="mord mtight"><span class="mord mathnormal mtight" style="margin-right:0.1076em;">f</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3281em;"><span style="top:-2.357em;margin-left:-0.1076em;margin-right:0.0714em;"><span class="pstrut" style="height:2.5em;"></span><span class="sizing reset-size3 size1 mtight"><span class="mord mtight"><span class="mord mathnormal mtight">i</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.143em;"><span></span></span></span></span></span></span></span></span></span></span></span>\textstyle{P\ignorespaces\ignorespaces\ignorespaces\ignorespaces}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="1" displaystyle="false"><msub><mi>p</mi><mi>i</mi></msub></mstyle></mrow><annotation encoding="application/x-tex">\scriptstyle{p_{i}}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4375em;vertical-align:-0.1361em;"></span><span class="mord mtight sizing reset-size6 size3"><span class="mord mtight"><span class="mord mathnormal mtight">p</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3281em;"><span style="top:-2.357em;margin-left:0em;margin-right:0.0714em;"><span class="pstrut" style="height:2.5em;"></span><span class="sizing reset-size3 size1 mtight"><span class="mord mtight"><span class="mord mathnormal mtight">i</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.143em;"><span></span></span></span></span></span></span></span></span></span></span></span>\textstyle{A_{i}}$ As before, if such a product exists, it is unique up to (unique) isomorphism. We write $P=\prod_{i\in I}A_{i}$ for the product object, and $g=\langle f_{i}\mid i\in I\rangle$ for the unique morphism in the definition.

Show that if a category has binary and nullary products then it has all finite products.

We now investigate the dual notion to products: namely coproducts. Formally, coproducts in $\mathcal{C}$ are just products in $\mathcal{C}^{\mathsf{op}}$, interpreted back in $\mathcal{C}$ . We spell out the definition.

Let $A,B$ be objects in a category $\mathcal{C}$. A coproduct of $A$ and $B$ is an object $A+B$ together with a pair of arrows $A\overset{\mspace{1.5mu}\mathsf{in}_{1}}{\longrightarrow}A+B\overset{\mspace{1.5mu}\mathsf{in}_{2}}{\longleftarrow}B$ such that for every triple $A\overset{f}{\longrightarrow}C\overset{g}{\longleftarrow}B$ there exists a unique morphism

such that the following diagram commutes.

We call the $\mspace{1.5mu}\mathsf{in}_{i}$’s injections and $[f,g]$ the copairing of $f$ and $g$. As with pairings, uniqueness of copairings can be specified by an equation:

This is given by disjoint union of sets, which can be defined concretely e.g. by

Also, given functions $f:X\longrightarrow Z$ and $g:Y\longrightarrow Z$, we can define

Check that this construction does yield coproducts in Set.

Note that this example suggests that coproducts allow for definition by cases.

Let us examine coproducts for some of our other standard examples.

In Pos, disjoint unions (with the inherited orders) are coproducts.

In Top, topological disjoint unions are coproducts.

In $\text{{Vect}}_{k}$, direct sums are coproducts.

In a poset, least upper bounds are coproducts.

Dually to products, express coproducts as initial objects of a category $\mathbf{Copair}(A,B)$ of $A$,$B$–copairings.

2.3 Pullbacks and Equalisers

We shall consider two further constructions of interest: pullbacks and equalisers.

Consider a pair of morphisms $A\overset{f}{\longrightarrow}C\overset{g}{\longleftarrow}B$. The pull-back of $f$ along $g$ is a pair $A\overset{p}{\longleftarrow}D\overset{q}{\longrightarrow}B$ such that $f\circ p=g\circ q$ and, for any pair $A\overset{p^{\prime}}{\longleftarrow}D^{\prime}\overset{q^{\prime}}{\longrightarrow}B$ such that $f\circ p^{\prime}=g\circ q^{\prime}$, there exists a unique $h:D^{\prime}\rightarrow D$ such that $p^{\prime}=p\circ h$ and $q^{\prime}=q\circ h$. Diagrammatically,

\scriptstyle{h}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="1" displaystyle="false"><msup><mi>q</mi><mo mathvariant="normal" lspace="0em" rspace="0em">′</mo></msup></mstyle></mrow><annotation encoding="application/x-tex">\scriptstyle{q^{\prime}}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7156em;vertical-align:-0.1361em;"></span><span class="mord mtight sizing reset-size6 size3"><span class="mord mtight"><span class="mord mathnormal mtight" style="margin-right:0.0359em;">q</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8278em;"><span style="top:-2.931em;margin-right:0.0714em;"><span class="pstrut" style="height:2.5em;"></span><span class="sizing reset-size3 size1 mtight"><span class="mord mtight"><span class="mord mtight">′</span></span></span></span></span></span></span></span></span></span></span></span></span></span>\scriptstyle{p^{\prime}}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="0" displaystyle="false"><mrow><mi>D</mi><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle></mrow></mstyle></mrow><annotation encoding="application/x-tex">\textstyle{D\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.0278em;">D</span><span class="mord text" style="color:#cc0000;"><span class="mord" style="color:#cc0000;">\ignorespaces</span></span><span class="mord text" style="color:#cc0000;"><span class="mord" style="color:#cc0000;">\ignorespaces</span></span><span class="mord text" style="color:#cc0000;"><span class="mord" style="color:#cc0000;">\ignorespaces</span></span><span class="mord text" style="color:#cc0000;"><span class="mord" style="color:#cc0000;">\ignorespaces</span></span><span class="mord text" style="color:#cc0000;"><span class="mord" style="color:#cc0000;">\ignorespaces</span></span><span class="mord text" style="color:#cc0000;"><span class="mord" style="color:#cc0000;">\ignorespaces</span></span><span class="mord text" style="color:#cc0000;"><span class="mord" style="color:#cc0000;">\ignorespaces</span></span><span class="mord text" style="color:#cc0000;"><span class="mord" style="color:#cc0000;">\ignorespaces</span></span></span></span></span></span></span>\scriptstyle{q}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="1" displaystyle="false"><mi>p</mi></mstyle></mrow><annotation encoding="application/x-tex">\scriptstyle{p}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4375em;vertical-align:-0.1361em;"></span><span class="mord mtight sizing reset-size6 size3"><span class="mord mathnormal mtight">p</span></span></span></span></span></span>\textstyle{B\ignorespaces\ignorespaces\ignorespaces\ignorespaces}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="1" displaystyle="false"><mi>g</mi></mstyle></mrow><annotation encoding="application/x-tex">\scriptstyle{g}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4375em;vertical-align:-0.1361em;"></span><span class="mord mtight sizing reset-size6 size3"><span class="mord mathnormal mtight" style="margin-right:0.0359em;">g</span></span></span></span></span></span>\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="1" displaystyle="false"><mi>f</mi></mstyle></mrow><annotation encoding="application/x-tex">\scriptstyle{f}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6222em;vertical-align:-0.1361em;"></span><span class="mord mtight sizing reset-size6 size3"><span class="mord mathnormal mtight" style="margin-right:0.1076em;">f</span></span></span></span></span></span>\textstyle{C} $\blacktriangle$

In Set the pullback of $A\overset{f}{\longrightarrow}C\overset{g}{\longleftarrow}B$ is defined as a subset of the cartesian product:

For example, consider a category $\mathcal{C}$ with

Then the pullback of $\mathsf{dom}$ along $\mathsf{cod}$ is the set of composable morphisms, i.e. pairs of morphisms $(f,g)$ in $\mathcal{C}$ such that $f\circ g$ is well-defined.

In Set again, subsets (i.e. inclusion maps) pull back to subsets:

Let $\mathcal{C}$ be a category with a terminal object $\mathbf{1}$. Show that, for any $A,B\in Ob(\mathcal{C})$, the pullback of $A\xrightarrow{\tau_{A}}\mathbf{1}\xleftarrow{\tau_{B}}B$ is the product of $A$ and $B$, if it exists.

Just as for products, pullbacks can equivalently be described as terminal objects in suitable categories. Given a pair of morphisms $A\overset{f}{\longrightarrow}C\overset{g}{\longleftarrow}B$, we define an $(f,g)$–cone to be a triple $(D,p,q)$ such that the following diagram commutes.

A morphism of $(f,g)$–cones $h:(D_{1},p_{1},q_{1})\rightarrow(D_{2},p_{2},q_{2})$ is a morphism $h:D_{1}\rightarrow D_{2}$ such that the following diagram commutes.

We can thus form a category Cone$(f,g)$. A pull-back of $f$ along $g$, if it exists, is exactly a terminal object of Cone$(f,g)$. Once again, this shows the uniqueness of pullbacks up to unique isomorphism.

Consider a pair of parallel arrows $\textstyle{A\ \ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="1" displaystyle="false"><mi>g</mi></mstyle></mrow><annotation encoding="application/x-tex">\scriptstyle{g}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4375em;vertical-align:-0.1361em;"></span><span class="mord mtight sizing reset-size6 size3"><span class="mord mathnormal mtight" style="margin-right:0.0359em;">g</span></span></span></span></span></span>\scriptstyle{f}$$\textstyle{\ B}$. An equaliser of $(f,g)$ is an arrow $e:E\rightarrow A$ such that $f\circ e=g\circ e$ and, for any arrow $h:D\rightarrow A$ such that $f\circ h=g\circ h$, there is a unique $\hat{h}:D\rightarrow E$ so that $h=e\circ\hat{h}$. Diagrammatically,

\scriptstyle{e}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="0" displaystyle="false"><mrow><mi>A</mi><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle></mrow></mstyle></mrow><annotation encoding="application/x-tex">\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord"><span class="mord mathnormal">A</span><span class="mord text" style="color:#cc0000;"><span class="mord" style="color:#cc0000;">\ignorespaces</span></span><span class="mord text" style="color:#cc0000;"><span class="mord" style="color:#cc0000;">\ignorespaces</span></span><span class="mord text" style="color:#cc0000;"><span class="mord" style="color:#cc0000;">\ignorespaces</span></span><span class="mord text" style="color:#cc0000;"><span class="mord" style="color:#cc0000;">\ignorespaces</span></span><span class="mord text" style="color:#cc0000;"><span class="mord" style="color:#cc0000;">\ignorespaces</span></span><span class="mord text" style="color:#cc0000;"><span class="mord" style="color:#cc0000;">\ignorespaces</span></span><span class="mord text" style="color:#cc0000;"><span class="mord" style="color:#cc0000;">\ignorespaces</span></span><span class="mord text" style="color:#cc0000;"><span class="mord" style="color:#cc0000;">\ignorespaces</span></span></span></span></span></span></span>\scriptstyle{g}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="1" displaystyle="false"><mi>f</mi></mstyle></mrow><annotation encoding="application/x-tex">\scriptstyle{f}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6222em;vertical-align:-0.1361em;"></span><span class="mord mtight sizing reset-size6 size3"><span class="mord mathnormal mtight" style="margin-right:0.1076em;">f</span></span></span></span></span></span>\textstyle{B}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="0" displaystyle="false"><mrow><mi>D</mi><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle></mrow></mstyle></mrow><annotation encoding="application/x-tex">\textstyle{D\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.0278em;">D</span><span class="mord text" style="color:#cc0000;"><span class="mord" style="color:#cc0000;">\ignorespaces</span></span><span class="mord text" style="color:#cc0000;"><span class="mord" style="color:#cc0000;">\ignorespaces</span></span><span class="mord text" style="color:#cc0000;"><span class="mord" style="color:#cc0000;">\ignorespaces</span></span><span class="mord text" style="color:#cc0000;"><span class="mord" style="color:#cc0000;">\ignorespaces</span></span><span class="mord text" style="color:#cc0000;"><span class="mord" style="color:#cc0000;">\ignorespaces</span></span><span class="mord text" style="color:#cc0000;"><span class="mord" style="color:#cc0000;">\ignorespaces</span></span><span class="mord text" style="color:#cc0000;"><span class="mord" style="color:#cc0000;">\ignorespaces</span></span><span class="mord text" style="color:#cc0000;"><span class="mord" style="color:#cc0000;">\ignorespaces</span></span></span></span></span></span></span>\scriptstyle{h}$\scriptstyle{\hat{h}}$ $\blacktriangle$

As for products, uniqueness of the arrow from $D$ to $E$ can be expressed equationally:

Why is $\widehat{e\circ k}$ well-defined for any $k:D\rightarrow E$? Prove that the above equation is equivalent to the uniqueness requirement.

In Set, the equaliser of $f,g$ is given by the inclusion

2.4 Limits and Colimits

The notions we have introduced so far are all special cases of a general notion of limits in categories, and the dual notion of colimits.

An important aspect of studying any kind of mathematical structure is to see what limits and colimits the category of such structures has. We shall return to these ideas shortly.

2.5 Exercises

Give an example of a category where some pair of objects lacks a product or coproduct.

(Pullback lemma) Consider the following commutative diagram.

Given that the right hand square $BCEF$ and the outer square $ACDF$ are pullbacks, prove that the left hand square $ABDE$ is a pullback.

Consider $A\overset{f}{\longrightarrow}C\overset{g}{\longleftarrow}B$ with pullback $A\overset{p}{\longleftarrow}D\overset{q}{\longrightarrow}B$. For each $A\overset{p^{\prime}}{\longleftarrow}D^{\prime}\overset{q^{\prime}}{\longrightarrow}B^{\prime}$ with $f\circ p^{\prime}=g\circ q^{\prime}$, let $\phi(p^{\prime},q^{\prime}):D^{\prime}\rightarrow D$ be the arrow dictated by the pullback condition. Express uniqueness of $\phi(p^{\prime},q^{\prime})$ equationally.

3 Functors

Don’t just look at the objects; take the morphisms into account too.

A functor $F:\mathcal{C}\rightarrow\mathcal{D}$ is given by:

An object-map, assigning an object $FA$ of $\mathcal{D}$ to every object $A$ of $\mathcal{C}$.

An arrow-map, assigning an arrow $Ff:FA\rightarrow FB$ of $\mathcal{D}$ to every arrow $f:A\rightarrow B$ of $\mathcal{C}$, in such a way that composition and identities are preserved:

Note that we use the same symbol to denote the object- and arrow-maps; in practice, this never causes confusion. Since functors preserve domains and codomains of arrows, for each pair of objects $A$, $B$ of $\mathcal{C}$, there is a well-defined map

The conditions expressing preservation of composition and identities are called functoriality.

Let $(P,\leq)$, $(Q,\leq)$ be preorders (seen as categories). A functor $F:(P,\leq)\longrightarrow(Q,\leq)$ is specified by an object-map, say $F:P\rightarrow Q$, and an appropriate arrow-map. The arrow-map corresponds to the condition

i.e. to monotonicity of $F$. Moreover, the functoriality conditions are trivial since in the codomain $(Q,\leq)$ all hom-sets are singletons. Hence, a functor between preorders is just a monotone map.

Let $(M,\cdot,1)$, $(N,\cdot,1)$ be monoids. A functor $F:(M,\cdot,1)\longrightarrow(N,\cdot,1)$ is specified by a trivial object map (monoids are categories with a single object) and an arrow-map, say $F:M\rightarrow N$. The functoriality conditions correspond to

i.e. to $F$ being a monoid homomorphism. Hence, a functor between monoids is just a monoid homomorphism.

Inclusion of a sub-category, $\mathcal{C}\hookrightarrow\mathcal{D}$, is a functor (by taking the identity map for object- and arrow-map).

The covariant powerset functor $\mathcal{P}:\mathbf{Set}\rightarrow\mathbf{Set}$:

$U:\textbf{Mon}\rightarrow\textbf{Set}$ is the ‘forgetful’ or ‘underlying’ functor which sends a monoid to its set of elements, ‘forgetting’ the algebraic structure, and sends a homomorphism to the corresponding function between sets. There are similar forgetful functors for other categories of structured sets. Why are these trivial-looking functors useful? — We shall see!