Brandon Ling

More on categories

September 09, 2020category theory

Tl;dr We look at some important concepts and examples of categories that will come up over and over again.

As a quick review, a category is a collection of objects with morphisms between them that can be composed together. Check out my previous post introducing categories if you need a refresher.


Preorders are categories in which there is at most one morphism between any two objects. In our pictures of categories, this means there is at most one arrow from one object to another (there might be one going from xx to yy and one from yy to xx though).

Another way to think about preorders is that all parallel paths are equal. By a path we mean any sequence of arrows where the target of one arrow is the source of the next (so they can be composed together). By parallel paths we mean all the paths have the same initial sources and the same final targets. By all parallel paths are equal we specifically mean that the compositions of all the morphisms in each path are equal to each other.

A preorder with parallel paths between objects A and B. Since f is the same as the other two parallel paths, we usually don’t even draw it.
A preorder with parallel paths between objects A and B. Since f is the same as the other two parallel paths, we usually don’t even draw it.

For preorders, we often denote that there is a morphism from an object xx to an object yy by writing xyx ≤ y.

The definition of a category implies that for any object xx we have x  xx ≤ x, and for any three objects x,y,zx, y, z, if xyx ≤ y and yzy ≤ z, then x  zx ≤ z.

I like to think of preorders as generalized hierarchies, as the examples below hopefully illustrate.

Examples of preorders


One of the simplest preorders is the booleans Bool = {false, true}. We get a preorder by setting false true.

Natural numbers

The natural numbers N\mathbb{N} = {0, 1, 2 } form a preorder with the usual ordering (e.g. 5 ≤ 9).

The booleans and natural numbers form preorders.
The booleans and natural numbers form preorders.

Resource theories

At a basic level, a resource theory is simply a collection of objects, or resources, a way to combine resources together as a single resource1, and a way to convert resources to other resources, which corresponds to morphisms between resources.

We can think of resource theories as preorders if we set xyx ≤ y if there is at least one morphism from xx to yy.

An example is the set of all collections of atoms and molecules Mat (for materials). In Mat we denote combining materials by +, and a preorder structure is given by setting xyx ≤ y if there is a chemical reaction that converts xx to yy, which we usually write as xyx \to y (note \to is used instead of ≤ in this context).

Here’s a concrete example in Mat if the above doesn’t quite make sense:

2H2+O22H2O.2\text{H}_2 + \text{O}_2 \to 2\text{H}_2\text{O}.

This describes the chemical reaction creating water from hydrogen and oxygen.

Power sets

Given a set SS, we can consider its power set P(S),P(S), which is the set of all subsets of SS. For example, if S={a,b,c},S = \{a, b, c\}, then

P(S)={{},{a},{b},{c},{a,b},{b,c},{a,c},{a,b,c}},P(S) = \{\{\}, \{a\}, \{b\}, \{c\}, \{a, b\}, \{b, c\}, \{a, c\}, \{a, b, c\}\},

where {}\{\} is the empty set.

We can turn P(S)P(S) into a preorder as follows: if XX and YY are subsets of SS (and thus elements of P(S)P(S)) we say XYX ≤ Y if XX is a subset of YY, which following standard mathematical notation we write as XYX \subseteq Y.

Partial orders

Power sets are also examples of partially ordered sets, often abbreviated as posets. A poset is a preorder that has the additional property that if xyx ≤ y and y xy ≤ x, then x=yx = y. In other words, you can’t have arrows that form loops like the following diagram:

You can’t have loops like this in a partial order.
You can’t have loops like this in a partial order.

In terms of sets, if a set XX is a subset of YY, and YY is a subset of XX, then they must have exactly the same elements, and thus are the same set.

Posets are partially ordered in the sense that you don’t need to be able to compare every pair of objects. For example, say SS = {a, b, c}. Then {a} and {b} are subsets of SS, but neither is a subset of the other, which is to say neither {a} \nsubseteq {b} nor {b} \nsubseteq {a}.

Total orders

Bool and N\mathbb{N} are also partial orders, and in fact they are also total orders. A total order is a poset for which every two objects are comparable, so either xxyy or yyxx is true (and if both are true then x=yx = y).

Pictorially the objects of a total order can be placed in a line with all the arrows pointing in the same direction, as in our pictures of Bool and N\mathbb{N} above.

The category of sets

This is probably the most important category in mathematics, since sets come up all the time in mathematics. We denote this category by Set. The objects of Set are, as you might expect, all sets. The morphisms between them are functions between sets.

If you don’t remember, a function f:XYf: X \to Y between sets XX and YY is a relation that takes each element xx in XX to an element yy in YY, where we usually denote this mapping explicitly by writing f(x)f(x) for yy. Note that ff maps each xx to an f(x)f(x) in YY, but for each yy there may or may not be an xx that maps to yy (in fact more than one xx could map to the same yy).

Identity morphisms are given by the identity function: for any set SS define idS:SSid_S: S \to S by idS(s)=sid_S(s) = s for all ss in SS.

Composition is also straightforward: for any two morphisms f:AB,g:BCf: A \to B, g: B \to C define their composite to be gf:ACg \circ f: A \to C by (gf)(a)=g(f(a))(g \circ f) (a) = g(f(a)) for all aa in AA.


Preorders are categories whose morphisms are simple: only one is allowed from one object to another. Monoids are like the reverse of preorders: there’s only one object, but there might be infinitely many morphisms.

Monoids might be more familiar in terms of sets: a monoid MM is defined to be a set with a binary operation :M×MM*: M \times M \to M that takes a pair (m,m)(m, m') of elements of MM and maps it to another element mm'' of MM. We write mm=mm * m' = m''. Note that in general mmmmm * m' ≠ m' * m.

There must also be an identity element ee in MM that satisfies me=em=mm * e = e * m = m for all mm in MM. The operation * must also satisfy an associativity property: (mn)p=m(np).(m * n) * p = m * (n * p).

From this description in terms of sets, do you see how to reconcile this with the category-theoretic definition of a monoid as a one-object category?

Here’s the answer: each element of MM corresponds to a morphism in the category, and in particular the identity element ee corresponds to the identity morphism idid. The binary operation * corresponds to composition of morphisms.

A common example of a monoid is strings in most programming languages: the empty string "" is the identity morphism, and string concatenation ++ is composition.

Strings form a monoid with the concatenation operation.
Strings form a monoid with the concatenation operation.

We’ll talk about another important class of monoids after we introduce the idea of isomorphisms.


We often come across the idea that two objects aa and bb are not quite equal, but instead equivalent or interchangeable. They are equivalent in the sense that there exist morphisms f:abf: a \to b and g:bag: b \to a such that

gf=idaandfg=idb.g \circ f = id_a \quad \text{and} \quad f \circ g = id _b.

We say that ff and gg are inverses of each other and write f=g1f = g^{-1} and g=f1g = f^{-1} to denote this. We also say that aa and bb are isomorphic, writing aba \cong b, and that a morphism hh is an isomorphism if an inverse h1h^{-1} exists.

Isomorphic objects are thought of as equivalent.
Isomorphic objects are thought of as equivalent.

The intuition is that you can go from aa to bb through ff and then back to aa through gg (and similarly from bb to aa and back to bb through gg and then ff), without losing any information.

As an example of losing information in Set, suppose X={x,y}X = \{x, y\} and Y={z}Y = \{z\}. Defining f:XYf:X \to Y by setting f(x)=f(y)=zf(x) = f(y) = z, we see there is no way to define an inverse function g:YXg: Y \to X that satisfies g(f(x))=xg(f(x)) = x and g(f(y))=yg(f(y)) = y (that is, gf=idXg \circ f = id_X). Going from XX to YY we lose information about where we started from.

In a preorder, objects aa and bb are isomorphic if a ba ≤ b and b ab ≤ a, and we can turn any preorder into a partial order by setting aa and bb equal to each other if aba \cong b.

In the string monoid example above, the only isomorphism is the empty string with itself, since only "" + "" = "".

However, isomorphisms may not be unique. That is to say, there may be more than one isomorphism between a given pair of objects. For example, in Set, let XX = {a, b, c} and YY = {1, 2, 3}. We can define an isomorphism by defining f1:XYf_1: X \to Y by f1(a)=1,f1(b)=2,f1(c)=3f_1(a) = 1, f_1(b) = 2, f_1(c) = 3 and g1:YXg_1: Y \to X by g1(1)=a,g1(2)=b,g1(3)=c.g_1(1) = a, g_1(2) = b, g_1(3) = c. You can check that g1f1g_1 \circ f_1 = idXid_X and f1g1f_1 \circ g_1 = idYid_Y.

But we can define another isomorphism by defining f2(a)=3,f2(b)=2,f2(c)=1f_2(a) = 3, f_2(b) = 2, f_2(c) = 1 and g2:YXg_2: Y \to X by g2(1)=c,g2(2)=b,g2(3)=a.g_2(1) = c, g_2(2) = b, g_2(3) = a. Again you can check that g2f2g_2 \circ f_2 = idXid_X and f2g2f_2 \circ g_2 = idYid_Y.

An example of more than one isomorphism between two objects.
An example of more than one isomorphism between two objects.

In fact there are a few more isomorphisms between XX and YY. How many are there?


Going back to our discussion of monoids, if every morphism of MM is an isomorphism, then MM is called a group.

Groups are super important, especially in physics. This is because groups generally have to do with symmetries, and symmetries are incredibly important.2 Examples of symmetries include concrete ones like rotational symmetry and more abstract ones like the Lorentz symmetry of special relativity.

For each symmetry, there is a group associated with it. The morphisms of the group (viewed as a one-object category) correspond to the transformations that preserve the symmetry.

For example, rotating a square about its center by 9090^{\circ} leaves it unchanged. In fact, there are seven more symmetry transformations of the square. Can you think of what they are? This group of symmetry transformations is known as the dihedral group of the square, usually denoted D4D_4.

I think it’s intuitive that groups are one-object categories, because each symmetry transformation only acts on a single object, and each transformation corresponds to a morphism from the (abstract) object in the category to itself. It’s basically an abstract picture of what’s happening.

The fact that each morphism is an isomorphism reflects the fact that the symmetry transformations are invertible: if I rotate by nintey degrees one way, I can undo it by rotating ninety degrees the other way.

Opposite categories

Our last example of categories is that of opposite categories given a category CC, we get another one for free! We denote it by CopC^{\text{op}} and call it the opposite category of CC. It’s opposite in the sense that the objects of CopC^{\text{op}} are the same as the objects of CC, but the morphisms are reversed: if f:abf: a \to b is a morphism from aa to bb in CC, then in CopC^{\text{op}} ff is considered a morphism from bb to aa instead.

Composition remains the same, so that if f:abf: a \to b and g:bcg: b \to c, then in the opposite category gfg \circ f becomes a morphism from cc to aa.

For preorders, this is literally reversing all the arrows.

The opposite category reverses all the morphisms.
The opposite category reverses all the morphisms.

  1. The way of combining resources corresponds to a monoidal product, which we haven’t discussed before, but the details aren’t important here. More precisely, a resource theory corresponds to a symmetric monoidal category, which we haven’t defined either. Check out the paper A mathematical theory of resources for more details.
  2. As an example of the importance of symmetries, Noether’s theorem says that if a physical system has a (continuous) symmetry, like a rotational symmetry by arbitrary degree, then that system has a conserved quantity. Examples of this include conservation of energy and momentum.

Written by Brandon Ling — physicist now developer.