---
title: A Zoo of Categories
module: Foundations
moduleNumber: 1
lessonNumber: 2
order: 102
summary: >
  The axioms admit two very different kinds of model: large categories of
  structured sets and their structure-preserving maps (Set, Mon, Grp, Top,
  Vect), and small categories that are themselves single algebraic objects — a
  monoid as a one-object category, a poset as a thin category. The awkward cases
  Rel and Pfn have sets as objects but relations and partial functions as arrows,
  and a typed programming language presents its types and programs as a category.
topics: [Foundations]
sources:
  - book: Simmons
    ref: "Ch. 1 §1.2 Categories of structured sets; §1.4–1.5 More complicated categories"
  - book: Leinster
    ref: "§1.1 Examples 1.1.3, 1.1.8 — categories of structures; categories as structures"
  - book: Barr & Wells
    ref: "Ch. 2 §2.1 Basic definitions; §2.2 Functional programming languages as categories; §2.3–2.5 Mathematical structures as categories"
draft: false
---

The [axioms of a category](/category-theory/foundations/what-is-a-category) are
deliberately spare, and they admit models of two quite different flavors. In the
first, the category is enormous and each object is a whole mathematical structure:
$\mathbf{Set}$, $\mathbf{Grp}$, $\mathbf{Top}$. In the second, the category is
small and _is itself_ a single mathematical structure: a monoid is a one-object
category, a poset is a category with at most one arrow between any two objects.
Category theory studies both at once, and most of its results say something about
each.

## Categories of structured sets

Objects are sets furnished with extra structure, arrows are the functions that
respect that structure, and composition and identities are inherited from
functions.[^simmons-structured] Checking the axioms is routine each time —
the composite of two structure-preserving maps preserves structure, and the
identity function trivially does.

| Category | Objects | Arrows |
| --- | --- | --- |
| $\mathbf{Set}$ | sets | all functions |
| $\mathbf{Mon}$ | monoids | monoid morphisms |
| $\mathbf{Grp}$ | groups | group homomorphisms |
| $\mathbf{Ab}$ | abelian groups | group homomorphisms |
| $\mathbf{Ring}$ | rings | ring homomorphisms |
| $\mathbf{Vect}_k$ | vector spaces over $k$ | linear maps |
| $\mathbf{Top}$ | topological spaces | continuous maps |
| $\mathbf{Pos}$ | posets | monotone maps |

Three of these need comment.

- **$\mathbf{Mon}$.** A monoid $(R, \ast, 1)$ is a set with an associative binary
  operation and a two-sided unit; a morphism $\varphi : R \to S$ satisfies
  $\varphi(r \ast s) = \varphi(r) \ast \varphi(s)$ and $\varphi(1) = 1$. Simmons
  calls the study of monoids "the study of composition in the miniature": a monoid
  is what remains of a category when only one object is allowed.
- **$\mathbf{Pos}$ and $\mathbf{Pre}$.** A preorder is a reflexive transitive
  relation; a partial order is additionally antisymmetric. Arrows in both
  categories are the monotone maps, $x \le y \Rightarrow f(x) \le f(y)$. For posets
  $R, S$ the hom-sets $\mathbf{Pre}(R, S)$ and $\mathbf{Pos}(R, S)$ coincide, which
  makes $\mathbf{Pos}$ a _full_ subcategory of $\mathbf{Pre}$.
- **$\mathbf{Top}$.** Objects carry a topology rather than an algebraic operation,
  and the arrows are continuous maps. It behaves less tamely than the algebraic
  examples: a [continuous bijection need not be an
  isomorphism](/category-theory/foundations/what-is-a-category).

The pattern "structured sets plus structure-preserving functions" covers most
categories met in a first pass through algebra and topology, but it is not the
definition of a category, and the next two families break it in different ways.

## Awkward relatives of Set

Both of the following categories have plain sets as objects, yet their arrows are
not functions in the ordinary sense. They matter in computing, where partiality
and nondeterminism are everyday phenomena.

- **Partial functions, $\mathbf{Pfn}$.** An arrow $A \to B$ is a total function
  $f : X \to B$ defined on some subset $X \subseteq A$. To compose
  $A \xrightarrow{f} B \xrightarrow{g} C$ with domains of definition $X$ and $Y$,
  restrict to $U = \{a \in X \mid f(a) \in Y\}$ and set
  $(g \circ f)(a) = g(f(a))$ for $a \in U$. For a third arrow $h : C \to D$,
  associativity holds because both bracketings of $h \circ g \circ f$ are defined
  on exactly $\{a \mid f(a) \in Y,\ g(f(a)) \in
  \text{dom}(h)\}$ and agree there.[^simmons-pfn]
- **Relations, $\mathbf{Rel}$.** An arrow $A \to B$ is a relation
  $\alpha \subseteq A \times B$. The composite of $\alpha : A \to B$ and
  $\beta : B \to C$ relates $x$ to $z$ exactly when some $y \in B$ has
  $(x, y) \in \alpha$ and $(y, z) \in \beta$. The identity on $A$ is the diagonal
  $\Delta_A = \{(x, x) \mid x \in A\}$.[^bw-rel]

A function is a special relation and a special partial function, so $\mathbf{Set}$
sits inside both. Each enlargement keeps the objects and changes only what counts
as an arrow — a reminder that a category is determined at least as much by its
arrows as by its objects.

> **Worked example (Composing partial functions).** Let $A = \{1, 2, 3\}$,
> $B = \{x, y\}$, $C = \{u, v\}$. Take $f : A \to B$ in $\mathbf{Pfn}$ defined on
> $\{1, 2\}$ by $f(1) = x$, $f(2) = y$ (undefined at $3$), and $g : B \to C$
> defined on $\{x\}$ by $g(x) = u$ (undefined at $y$). The composite $g \circ f$
> is defined on
> $$
> U = \{a \in \{1, 2\} \mid f(a) \in \{x\}\} = \{1\},
> $$
> with $(g \circ f)(1) = g(f(1)) = u$. Composition shrinks the domain of
> definition from $\{1, 2\}$ to $\{1\}$: partiality accumulates.

> **Worked example (Composing relations).** Let $A = \{1, 2\}$, $B = \{x, y\}$,
> $C = \{u, v\}$, with $\alpha = \{(1, x), (1, y), (2, y)\} : A \to B$ and
> $\beta = \{(x, u), (y, v)\} : B \to C$ in $\mathbf{Rel}$. The composite
> $\beta \circ \alpha$ relates $a$ to $c$ when some $b$ has $(a, b) \in \alpha$
> and $(b, c) \in \beta$:
> $$
> (1, x)(x, u) \Rightarrow (1, u), \quad (1, y)(y, v) \Rightarrow (1, v),
> \quad (2, y)(y, v) \Rightarrow (2, v),
> $$
> so $\beta \circ \alpha = \{(1, u), (1, v), (2, v)\}$. The relation $\alpha$
> sends $1$ to two outputs at once, which a partial function cannot do.

## Small categories as single structures

In the second family the whole category is itself a single manageable algebraic
object.

### A monoid as a one-object category

Let $M$ be a monoid. Build a category $\mathcal{C}(M)$ with a single object $\ast$,
one arrow $\ast \to \ast$ for each element of $M$, composition given by the monoid
operation, and $1_\ast$ the unit element. Associativity and the unit laws of the
category are precisely the monoid axioms.[^bw-monoid] Conversely, any one-object
category yields a monoid: its arrows under composition. The two notions are the
same data presented twice.

$$
% caption: The additive monoid of natural numbers as a one-object category: each
% element is a loop on the single object, and composition is addition, so the
% loop for 1 composed with itself gives the loop for 2.
\begin{tikzpicture}[scale=1.0, >=stealth, font=\small]
\definecolor{acc}{HTML}{4A6FA5}
\node[circle, fill=acc, inner sep=1.8pt] (m) at (0,0) {};
\node[font=\small] at (0,-0.9) {one object};
\draw[->, black, thick] (m) to[out=150, in=210, looseness=10] node[left=2pt] {$0$} (m);
\draw[->, acc, thick] (m) to[out=60, in=120, looseness=10] node[above=2pt] {$1$} (m);
\draw[->, acc, thick] (m) to[out=-30, in=30, looseness=10] node[right=2pt] {$2$} (m);
\node[black, font=\footnotesize] at (0,-1.5) {composition is $+$};
\end{tikzpicture}
$$

If every arrow of the one-object category is invertible, the monoid is a group.
More generally, a category in which _every_ arrow is an isomorphism is called a
**groupoid**; a group is a one-object groupoid.

### A poset as a thin category

Let $(P, \le)$ be a preordered set. Build a category with the elements of $P$ as
objects and exactly one arrow $x \to y$ when $x \le y$, none otherwise.
Reflexivity supplies the identities, transitivity supplies composition, and the
axioms hold automatically because between any two objects there is at most one
arrow — every diagram in such a category commutes.[^lein-order] Categories with
this property are called **thin**. Antisymmetry corresponds to the condition that
isomorphic objects are equal.

$$
% caption: The divisor poset of 12 as a thin category; arrows are the relation
% $x$ divides $y$, drawn Hasse-style with composites (such as the arrow from 1 to
% 12) omitted because they are forced.
\begin{tikzpicture}[scale=1.0, >=stealth, font=\small]
\definecolor{acc}{HTML}{4A6FA5}
\node (n1) at (0,0) {$1$};
\node (n2) at (-1.2,1.2) {$2$};
\node (n3) at (1.2,1.2) {$3$};
\node (n4) at (-1.2,2.4) {$4$};
\node (n6) at (1.2,2.4) {$6$};
\node (n12) at (0,3.6) {$12$};
\draw[->, acc, thick] (n1) -- (n2);
\draw[->, acc, thick] (n1) -- (n3);
\draw[->, acc, thick] (n2) -- (n4);
\draw[->, acc, thick] (n2) -- (n6);
\draw[->, acc, thick] (n3) -- (n6);
\draw[->, acc, thick] (n4) -- (n12);
\draw[->, acc, thick] (n6) -- (n12);
\end{tikzpicture}
$$

The two miniature readings constrain a category in opposite ways, and every
category mixes them:

| Degenerate case | Constraint | What survives |
| --- | --- | --- |
| monoid | one object | composition structure |
| preorder | at most one arrow per hom-set | comparison structure |
| discrete category | only identity arrows | a bare class of objects |

A **discrete category** is the extreme in both directions at once: no arrows
except the mandatory identities, so it is nothing more than its collection of
objects.

### Finite categories drawn in full

A category can also be given by an explicit finite table of objects and arrows.
The categories $\mathbf{0}$, $\mathbf{1}$, and $\mathbf{2}$ were
[introduced with the axioms](/category-theory/foundations/what-is-a-category); one
step up in size are the shapes that index the constructions of later lessons.

$$
% caption: Two small index categories: the parallel pair that indexes equalizers,
% and the commuting triangle in which $h = g f$ is the only nontrivial equation.
\begin{tikzpicture}[scale=1.0, >=stealth, font=\small]
\definecolor{acc}{HTML}{4A6FA5}
% parallel pair
\node (p1) at (0,0) {$A$};
\node (p2) at (2.4,0) {$B$};
\draw[->, acc, thick] ([yshift=3pt]p1.east) -- ([yshift=3pt]p2.west) node[midway, above] {$f$};
\draw[->, acc, thick] ([yshift=-3pt]p1.east) -- ([yshift=-3pt]p2.west) node[midway, below] {$g$};
% triangle
\node (t1) at (5.6,0.9) {$A$};
\node (t2) at (7.8,0.9) {$B$};
\node (t3) at (7.8,-0.9) {$C$};
\draw[->, acc, thick] (t1) -- (t2) node[midway, above] {$f$};
\draw[->, acc, thick] (t2) -- (t3) node[midway, right] {$g$};
\draw[->, black, thick] (t1) -- (t3) node[midway, below left] {$h = gf$};
\end{tikzpicture}
$$

When a finite category is specified by a drawing, composition must be defined for
every composable pair and the axioms checked; usually the drawing leaves no
choice. These small categories are the index shapes over which
[limits](/category-theory/limits-colimits/limits) are taken: the parallel pair
indexes equalizers, the discrete two-object category indexes binary
[products](/category-theory/universal-properties/products-and-coproducts).

## A programming language as a category

A typed functional programming language presents a category, the point of contact
between category theory and computing science.[^bw-fpl] Take a language $L$ with:

- **primitive data types**, plus derived types built by constructors;
- **operations** between types, including a do-nothing operation $\mathtt{id}_A$
  on each type $A$;
- a **composition constructor** taking $f : A \to B$ and $g : B \to C$ to a
  program $f; g : A \to C$;
- a **unit type** $\mathbf{1}$ such that each constant $c$ of type $A$ is an
  operation $c : \mathbf{1} \to A$.

Impose the evident equations ($f; \mathtt{id} = f$, associativity of $;$). The
resulting category $\mathcal{C}(L)$ has the types of $L$ as objects and the
operations — programs — as arrows, with $g \circ f = f; g$. Here
$\mathcal{C}(L)$ is a _model_ of the language, not its syntax: two source programs
that the equations force to be equal, such as $f$ and $f; \mathtt{id}$, become the
same arrow.

For example, take a language with types $\mathtt{NAT}$, $\mathtt{BOOLEAN}$, and
$\mathtt{CHAR}$, with constants $0 : \mathbf{1} \to \mathtt{NAT}$ and
$\mathtt{true}, \mathtt{false} : \mathbf{1} \to \mathtt{BOOLEAN}$, operations
$\mathtt{succ} : \mathtt{NAT} \to \mathtt{NAT}$,
$\mathtt{ord} : \mathtt{CHAR} \to \mathtt{NAT}$, and
$\mathtt{chr} : \mathtt{NAT} \to \mathtt{CHAR}$, subject to
$\mathtt{chr} \circ \mathtt{ord} = \mathtt{id}_{\mathtt{CHAR}}$.

$$
% caption: A fragment of the category of a toy language. The program next is the
% composite chr after succ after ord; the equation chr after ord = id makes some
% distinct source programs equal as arrows.
\begin{tikzpicture}[scale=1.0, >=stealth, font=\small,
  ty/.style={draw, minimum width=17mm, minimum height=8mm, align=center, font=\footnotesize}]
\definecolor{acc}{HTML}{4A6FA5}
\node[ty] (one) at (0,1.6) {$\mathbf{1}$};
\node[ty] (nat) at (3.4,1.6) {\texttt{NAT}};
\node[ty] (chr) at (3.4,-0.8) {\texttt{CHAR}};
\node[ty] (bool) at (0,-0.8) {\texttt{BOOLEAN}};
\draw[->, acc, thick] (one) -- (nat) node[midway, above] {$0$};
\draw[->, acc, thick] (one) -- (bool) node[midway, left] {\texttt{true}};
\draw[->, acc, thick] (nat) to[out=25, in=-25, looseness=5] node[right] {\texttt{succ}} (nat);
\draw[->, acc, thick] ([xshift=-5pt]chr.north) -- ([xshift=-5pt]nat.south) node[midway, left] {\texttt{ord}};
\draw[->, acc, thick] ([xshift=5pt]nat.south) -- ([xshift=5pt]chr.north) node[midway, right] {\texttt{chr}};
\end{tikzpicture}
$$

The composite program
$\mathtt{next} = \mathtt{chr} \circ \mathtt{succ} \circ \mathtt{ord} :
\mathtt{CHAR} \to \mathtt{CHAR}$ computes the successor character, and the arrows
$\mathtt{next}$ and
$\mathtt{chr} \circ \mathtt{succ} \circ \mathtt{ord} \circ \mathtt{chr} \circ
\mathtt{ord}$ are equal in $\mathcal{C}(L)$ because of the imposed equation. Typing
is the source/target structure of the category, not an annotation layered on top.
The correspondence between typed lambda calculi and
[cartesian closed categories](/category-theory/cartesian-closed-lambda/lambda-calculus-correspondence)
develops this identification in full.

## Free categories and free monoids

One more source of examples, midway between the structured-set world and the
small-category world. Every directed graph $G$ generates a **free category**
$F(G)$: the objects are the nodes of $G$, the arrows are the finite paths, with
composition given by concatenating paths and identities given by the empty paths.
Associativity is the associativity of concatenation.[^bw-free]

Two special cases:

- The graph with one node and no edges generates the category $\mathbf{1}$.
- The graph with one node and one loop generates the one-object category whose
  arrows are the finite strings over a one-letter alphabet, i.e. the **free
  monoid** on one generator, isomorphic to $(\mathbb{N}, +, 0)$.

The free monoid on an arbitrary set $A$ is the **Kleene closure** $A^\ast$: all
finite lists of elements of $A$ under concatenation, with the empty list as unit.
The word "free" carries a precise universal meaning, given by the
[free–forgetful adjunctions](/category-theory/adjunctions/free-forgetful-adjunctions);
here it names a construction that turns any graph into a category and any set into a
monoid.

> **Worked example (The free monoid on two letters).** For $A = \{a, b\}$, the
> elements of $A^\ast$ are the finite strings $\varepsilon, a, b, aa, ab, ba, bb,
> aab, \dots$, and the operation is concatenation: $(ab)(ba) = abba$. It is
> associative, since $(a \cdot b) \cdot a = aba = a \cdot (b \cdot a)$, and the
> empty string is the two-sided unit, $\varepsilon w = w = w \varepsilon$. It is
> not commutative: $ab \neq ba$. The free monoid on _one_ letter is
> $\{a\}^\ast = \{\varepsilon, a, aa, \dots\}$, isomorphic to $(\mathbb{N}, +, 0)$
> by counting letters.

## Summary of the examples

The table records the two flavors and where each example lives.

| Example | Kind | Objects | Arrows | Special feature |
| --- | --- | --- | --- | --- |
| $\mathbf{Set}$, $\mathbf{Grp}$, $\mathbf{Top}$, $\mathbf{Vect}_k$ | large | structures | structure maps | the classical template |
| $\mathbf{Pfn}$, $\mathbf{Rel}$ | large | sets | partial functions, relations | arrows are not functions |
| monoid $M$ | small | one | elements of $M$ | composition in miniature |
| preorder / poset $P$ | small | elements of $P$ | instances of $\le$ | comparison in miniature; thin |
| discrete category | small | any class | identities only | no structure at all |
| $\mathcal{C}(L)$ for a language $L$ | small | types | programs | equations quotient the syntax |
| $F(G)$ for a graph $G$ | small | nodes | paths | freely generated |

Two disciplines carry forward. First, never assume an object has elements or an
arrow is a function; half the examples above violate each assumption. Second, the
same categorical statement specializes across the zoo — a statement about
categories is simultaneously a statement about sets, monoids, orders, spaces, and
programming languages. [Functors](/category-theory/foundations/functors), the maps
_between_ categories, turn constructions like "underlying set," "free monoid," and
"path category" into mathematical objects in their own right.

[^simmons-structured]: **Simmons**, _An Introduction to Category Theory_, §1.2 — categories of structured sets; the monoid and preset/poset examples worked in detail, and $\mathbf{Pos}$ as a full subcategory of $\mathbf{Pre}$.
[^simmons-pfn]: **Simmons**, §1.2, Example 1.2.3 — the category $\mathbf{Pfn}$ of sets and partial functions, with composition by restriction to the composable part.
[^bw-rel]: **Barr & Wells**, _Category Theory for Computing Science_, §2.1.13–2.1.14 — the categories $\mathbf{Pfn}$ and $\mathbf{Rel}$, with the diagonal relation as identity.
[^bw-monoid]: **Barr & Wells**, §2.3.1–2.3.12 — preordered sets, semigroups, monoids, the Kleene closure, and the constructions $\mathcal{C}(S, \alpha)$ and $\mathcal{C}(M)$ presenting an ordered set and a monoid as categories.
[^lein-order]: **Leinster**, _Basic Category Theory_, §1.1, Examples 1.1.8(b)–(e) — discrete categories, groups and monoids as one-object categories, and preorders as categories with at most one arrow between objects.
[^bw-fpl]: **Barr & Wells**, §2.2 — functional programming languages as categories: the assumptions A-1 to A-3, the category $\mathcal{C}(L)$, and the NAT/BOOLEAN/CHAR example with the program next.
[^bw-free]: **Barr & Wells**, §2.6.16–2.6.17 — the free category (path category) generated by a graph, and the one-loop graph generating the free monoid on one generator.