A Zoo of Categories

The axioms of 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.¹ Checking the axioms is routine each time — the composite of two structure-preserving maps preserves structure, and the identity function trivially does.

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 $\phi :R\to S$ satisfies $\phi (r\ast s)=\phi (r)\ast \phi (s)$ and $\phi (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.

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\stackrel{f}{\to }B\stackrel{g}{\to }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.²
• 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\}$.³

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.

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.⁴ Conversely, any one-object category yields a monoid: its arrows under composition. The two notions are the same data presented twice.

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.⁵ Categories with this property are called thin. Antisymmetry corresponds to the condition that isomorphic objects are equal.

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

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 $0$, $1$, and $2$ were introduced with the axioms; one step up in size are the shapes that index the constructions of later lessons.

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 are taken: the parallel pair indexes equalizers, the discrete two-object category indexes binary products.

A programming language as a category

A typed functional programming language presents a category, the point of contact between category theory and computing science.⁶ 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 $1$ such that each constant $c$ of type $A$ is an operation $c: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:1\to \mathtt{NAT}$ and $\mathtt{true},\mathtt{false}: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}}$.

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 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.⁷

Two special cases:

• The graph with one node and no edges generates the category $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; here it names a construction that turns any graph into a category and any set into a monoid.

Summary of the examples

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

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, the maps between categories, turn constructions like underlying set, free monoid, and path category into mathematical objects in their own right.