Introduction to Category Theory/Categories

Categories

Definition

A category $𝒞$ consists of the following data:

• Objects. These are referred to by generic symbols like $A,B,C,...$ .
• Arrows. These are referred to by generic symbols like $f,g,h,...$ .

These data are required to satisfy the following axioms:

• An object is not an arrow; an arrow is not an object.
• Domains. To every arrow $f$, we assign a unique object denoted by $\text{dom}(f)$. We say $f$ is from $\text{dom}(f)$ .
• Codomains. To every arrow $g$, we assign a unique object denoted by $\text{cod}(g)$. We say $g$ is to $\text{cod}(g)$ .
• Composition of arrows. For every two arrows $f$ and $g$, if $\text{cod}(f)=\text{dom}(g)$, then, there is an arrow $g\circ f$ such that $\text{dom}(g\circ f)=\text{dom}(f)$ and $\text{cod}(g\circ f)=\text{cod}(g)$ .
• Associativity of composition. For any three arrows $f,g$ and $h$ such that $\text{cod}(f)=\text{dom}(g)$ and $\text{cod}(g)=\text{dom}(h)$, we have that $(h\circ g)\circ f=h\circ (g\circ f)$ .
• Existence of identity for each object. For every object $A$, there is an arrow $1_A$, called the identity arrow of A, such that
  • $\text{dom}(1_A)=A$ and $\text{cod}(1_A)=A$, and
  • for every arrow $f$, if $\text{dom}(f)=A$ then $f\circ 1_A=f$, and if $\text{cod}(f)=A$ then $1_A\circ f=f$ .

Note that the existence statement for identities does not claim their uniqueness. However, we can actually prove that the identity arrow is unique to its respective object.

Arrows are often called morphisms. For a morphism $f$, we usually write $f:A\to B$ to simultaneously show its domain and codomain. The collection of all arrows from $A$ to $B$ is written, depending on choice, as ${\text{hom}}_{𝒞}(A,B)$ or $𝒞(A,B)$. If this collection is small enough to be a set, we call $𝒞$ locally small; we say $𝒞$ is large otherwise. We almost always deal with locally small categories.

Discussion

These principles are just those of the `algebra of function composition' already introduced in the discussion of functions. So we're making a shift from thinking about functions in terms of what they do to the elements of sets, to thinking about (vaguely) function-like entities that are described in terms of their external behavior in terms of composition. But we see from the upcoming list of examples that arrows are only function-like in certain respects; they definitely do not have to actually be functions.

From the definition, some basic results follow (in the same way they do for monoids and groups).

• a sequence of arrows $a_1,\dots a_n$ composes to the same thing no matter how it is parenthesized, as long as the order is kept. e.g. $a\circ (b\circ (c\circ d))=((a\circ b)\circ c)\circ d$, etc.
• identities are unique. That is, if we have some $h:A\to A$ such that $h\circ f=f$ for all $f:B\to A$ and $g\circ h=g$ for all $g:A\to C$, then $h=1_A$

The first of these is normally proved by induction in graduate level introductions to abstract algebra (such as Serge Lang's Algebra), but the proof is not very illuminating (at least to beginners). The proof of the second is however a mini-classic, which you would have already encountered if you've done any group theory:

$h=h\circ 1_A=1_A$

It's the two-sidedness of the property characterizing the identity that makes this work.

Examples

Sets

$𝒮ets$ is a category whose objects are sets and whose arrows are functions.

There is however a technical point to manage. In the account of functions given earlier, a function is presented as a kind of relation between two sets, its domain, which it is `from', and its codomain, which it is `to'. This is what's needed for category theory, but in the most commonly encountered set-theoretical definition, a function is just a set of ordered pairs meeting the condition that nothing appears as first member of two different pairs (different pairs being those with either different first or second members, by the set-theoretical principle of extensionality). The set of second members is called the range, and a function is then `to' any set that contains the range as a subset. This would not work out for category theory, since we need each arrow to have only one domain and only one codomain.

So to make a set-theoretic function serve as a category arrow in $𝒮ets$, we need to bundle it with with some superset of its range, which then constitutes is codomain, so it's an ordered pair <set-theoretic function, codomain>. But we don't have to add a domain, since, unlike the range, that's determined intrinsically by the set of ordered pairs.

So, having taken all that on board and proved to ourselves that $𝒮ets$ is a category, we get for free the results from the Discussion section above that identities are unique.

Monoids

Every monoid is a category with only one object. Category is a generalization of monoid. The section on Free Categories just below expands on this point.

All Monoids

The category of monoids $ℳon$ is a category, whose objects are monoids and whose arrows are monoid homomorphisms.

This represents a very large and important class of examples: for pretty much any of the kinds of algebraic systems you might study in an Abstract Algebra course, there will be a category with instances of the kind of system in question as objects, and homomorphisms (however defined for that particular kind of system) as arrows.

Posets

A partially ordered set or a poset is a category, whose objects are elements of the poset and whose arrows are 'less than or equal' relations.

In greater detail, a preorder is a category in which there is at most one arrow from any object $A$ to any object $B$. So the relation "there is an arrow from $A$ to $B$" will satisfy the axioms of reflexivity and transitivity, but not necessarily either symmetry or antisymmetry. We can impose antisymmetry by requiring at most one arrow connecting $A$ and $B$, regardless of direction. This example provides another instance where arrows aren't functions. The Hasse diagram of a poset is a directed graph whose corresponding free category is that set with its partial order.

All Posets

The category of posets $𝒫os$ is a category, whose objects are posets and whose arrows are order preserving functions. If A and B are posets, then function $f:A\to B$ is order preserving or monotone, if for every elements x and y in A $f(x)\le f(y)\text{ if }x\le y$. This is another example where algebraic systems of some type are the objects, and their homomorphisms the arrows.

Free Categories

Directed graphs

A simple directed graph.

Here we have objects ($A,B,C,D$) and arrows ($w,x,y,z$), the basic furniture of a category, but no category because there are no rules. In particular, the only arrows present are the ones depicted.

A directed graph is a collection of objects and arrows without any rules of composition or identity arrows. We say that a graph is small, if the collections are sets. A small directed graph can be described as a set O of objects and a set A of arrows, and two functions $\text{dom}:A\to O$ and $\text{cod}:A\to O$ that associate domain and codomain to each arrow. Conversely, given any two disjoint sets A and O, and any two functions from A to O, we get a small directed graph.

Free category on a (directed) graph

An obvious way to get a category out of a graph is to let category arrows be (finite) sequences of graph arrows, with the empty sequence $<>$ serving as the identity for each node, and composition of sequences defined in the `obvious' way.

Well that's the basic idea but there are a few annoying technicalities. First, and trivially, we have to decide whether to write our sequences in the order of traversal of a path (intuitively natural), or in the standard order of arrow (and function) composition (counter-intuitive but supported by tradition). We'll try to uphold rationality against tradition for a few minutes and write our paths in the order of traversal. So, technically an arrow f in a category freely generated by graph is a sequence $<x_1,x_2,\dots ,x_m>$ of arrows $x_i$ in graph such that $\text{cod}(x_i)=\text{dom}(x_{i+1})$ for all indexes i. The word freely means that two sequences $<x_1,x_2,\dots ,x_m>$ and $<y_1,y_2,\dots ,y_n>$ represent the same arrow if and only if they are the same sequence, that is

$m=n$ and $x_1=y_1,x_2=y_2,\dots ,x_m=y_n$.

Composition of arrows is defined:

If $f=<x_1,\dots ,x_m>$, $g=<y_1,\dots ,y_n>$, and cod $x_m$=dom $y_1$, then:

$g\circ f=<x_1,\dots ,x_m,y_1,\dots ,y_n>$

Ugh. Well, eventually stuff like this gets easier to write for yourself than to read. Note the confusing order switch between the structure of the composed sequence and the arrow-composition notation. Associativity of course follows from the associativity of composition of sequences.

The other technical point involves the identities and the requirements for something to be an arrow; can you figure out what it is and suggest a solution?

We say that a category is free, if it's freely generated by some directed graph.

Free categories are of considerable importance for applying category theory to logic (e.g. Lambek and Scott (1986) Introduction to Higher Order Categorical Logic). They also provide a fine illustration of why arrows don't have to be functions. And of the point above that a category is a generalization of a monoid, since the category arrows are like monoid elements that can't always be composed. Monoids in general have one feature that free categories can lack, in that different compositions of arrows can result in the same monoid element. This can happen with categories too, but not with free ones.

Foundational Issues

There are some tricky foundational points that arise in the definition of category. The word 'collection' was used where one might have expected 'set', because in many important examples of categories, the collections of objects and arrows are 'too big' to be sets, but instead must be proper classes. The most obvious case is our first example, the category $𝒮et$, where Russell's Paradox tells us that there can't be any such thing as a set of all sets, so the collection of objects of $𝒮et$ can't be a set.

If the collections of objects and arrows of a category are sets, it is called a small category, otherwise, a large category. So $𝒮et$ is large, and any monoid is small. What about a poset, or $ℳon$? Most of the large categories that people are interested in, such as $𝒮et$, have the property that for any objects $A,B$, ${\text{hom}}_{𝒞}(A,B)$ is a set. Such a category is called locally small.

Category theorists appear on the whole to not be very interested in fussing about foundations, so if you can remember what 'small', 'large', and 'locally small' mean, you almost certainly know enough.

'Spinoff' Categories

All algebraic systems provide various further ones of the same kind; for groups, for example, we might have some interesting subgroups and quotient groups, and will always have lots of product groups. Categories seem to participate in the process with an unusual degree of exuberance. For each of the 'spinoff categories' below (not a standard term, but it seems quite appropriate to this author (AA)), it is a good basic exercise to prove that it really is a category. The proof is always a routine demonstration that:

• the putative arrow-composition actually produces an arrow in the category
• composition is associative
• such that each object has an identity arrow

There are plenty more of these things than we illustrate here, but is it necessary to learn them all at once?

The Opposite Category

For any category $𝒞$, we also have the opposite category ${𝒞}^{op}$, formed by retaining the objects of $𝒞$ without change, but swapping the domain and codomain of each arrow. Composition is defined by the equation $f^{op}\circ g^{op}=(g\circ f{)}^{op}$. Yet another way of making the point that arrows don't have to be functions. Here is an outline of the proof that ${𝒞}^{op}$ really is a category. This is also often called the dual category.

Pair Categories

For any categories $𝒞$, $𝒟$, we can form the pair category $(𝒞,𝒟)$ whose objects are pairs $(C,D)$ of objects from $𝒞$, $𝒟$, respectively, and whose arrows are pairs $(f,g)$ of arrows of $𝒞$, $𝒟$, respectively, such that if $f:C\to C^{\prime }$, $g:D\to D^{\prime }$, then

$(f,g):(C,D)\to (C^{\prime },D^{\prime })$

Composition is defined as:

$(f^{\prime },g^{\prime })\circ (f,g)=(f^{\prime }\circ f,g^{\prime }\circ g)$

This is basically a direct product construction, and generalizes straightforwardly to $n$-tuples.

Slice Categories

File:Slice diagram.png

Arrow ($h$ in slice category

For any object $A$ of a category $𝒞$, the slice category of objects over $A$, $𝒞/A$, has as objects those arrows of $𝒞$ that have $A$ as their codomain. The arrows are a bit harder to describe. Suppose that $f:B\to A$ and $g:C\to A$ are objects of $𝒞/A$. Then $h:B\to C$ of $𝒞$ is also an arrow of $𝒞/A$, from $f$ to $g$, if $g\circ h=f$. This is illustrated in the commutative diagram to the right, which is a graph representing some objects and arrows in the category, and there is a convention that any two paths between the same node are the same arrow (typically derived by a different composition of other arrows). Commutative diagrams can be formalized as a way to represent facts about categories (e.g. Barr and Wells (1999:91-94), but we'll just take them as suggestive intuitive representations for equations, which will be the 'official' format for imposing identities on different compositions of arrows.

File:Slice composition diagram.png

Composition of arrows in slice category

We now need to define composition for the arrows; the basic idea is that the composite of two slice-category arrows is the slice-category correspondent of the two original arrows. We need to do a bit of work to show that this works, as expressed in the diagram to the right. Here $h$ is an arrow $f\to f^{\prime }$, and $h^{\prime }$ one $f^{\prime }\to f^{″}$. For $h^{\prime }\circ h$ to be an arrow from $f$ to $f^{″}$, it must be the case that $f^{″}\circ h^{\prime }\circ h=f$, which you can verify as an exercise. Associativity and identities then follow immediately from these properties of the original arrows of $𝒞$.

A (perhaps excessively) fine point is that, although people standardly speak of the arrows of $𝒞/A$ as being certain of the arrows of $𝒞$, this can't technically be quite right, since arrows have unique domains and codomains, and these are different for the arrows of the two categories. What we really want is for each suitable arrow of $𝒞$ to induce a (different) corresponding arrow of $𝒞/A$. A construction that would suffice would be to have the arrows of $𝒞/A$ be triples of the form (original arrow, new domain, new codomain).

Morphisms

Monomorphism

We've already discussed Injective, or one-to-one functions, and observed that the 'internal' property of one-to-oneness, for functions, is equivalent to the 'external' property of being cancellable on the left ($g\circ f_1=g\circ f_2$ if and only if $f_1=f_2$). Arrows that aren't functions of any kind can't be one-to-one, but they can have the cancellation property, giving us:

Monomorphism, a categorical analogy of injective function.

A monomorphism (also called a monic morphism or a mono) is a morphism $f:X\to Y$ which is left-cancellative in the following sense

$f\circ g_1=f\circ g_2$ implies $g_1=g_2$ for all morphisms $g_1,g_2:Z\to X$.

The situation described by these equations is often depicted by this diagram:

Put another way, map $f:X\to Y$ is monic if and only if the induced map $f_{*}:\text{hom}(Z,X)\to \text{hom}(Z,Y)$ is injective for all $Z$. Here $f_{*}$ is function such that $f_{*}(g)=f\circ g$ for all $g$ in $\text{hom}(Z,X)$. If your mind bounces off this statement at first, it's definitely worth reflecting on until it really seems to make sense.

In the category $𝒮ets$ the monomorphisms are exactly the injective functions as we proved in the first lesson. Many familiar arrows, such as the homomorphisms of various kinds of algebraic systems, are functions with some additional restrictions placed on them (e.g. they must preserve some algebraic relationships). Such arrows are (almost?) always one-to-one/injective as functions if and only if they are monic as arrows. Eventually we'll be able to formulate a more precise and general version of this claim.

Two easy results about monomorphisms are:

• If $f$ and $g$ are monomorphisms, then $g\circ f$ is one too,
• If $g\circ f$ is a monomorphism, then $f$ is one too.

Here are the proofs.

Epimorphism

Likewise, there is an 'external' version of the 'internal' property of onto-ness:

Epimorphism is (almost) a categorical analog of surjective function.

An epimorphism (also called an epic morphism or an epi) is a morphism $f:X\to Y$ which is right-cancellative in the following sense:

$g_1\circ f=g_2\circ f$ implies $g_1=g_2$ for all morphisms $g_1,g_2:Y\to Z$.

Put another way, a map $f:X\to Y$ is epic if and only if the induced map $f^{*}:\text{hom}(Y,Z)\to \text{hom}(X,Z)$ is injective for all Z. Here $f^{*}$ is a function such that $f^{*}(g)=g\circ f$ for all g in $\text{hom}(Y,Z)$.

In the category $𝒮ets$ the epimorphisms are exactly the surjective functions as we proved in the first lesson. There is also another way to define surjective, which is equivalent to epimorphism in many interesting categories, but certainly not in all categories.

From the discussion of Opposite categories, we can see that a monomorpism $f$ is an epimorphism in ${𝒞}^{op}$ (or, if we want to be ultra-fussy, corresponds to one), and vice-versa. This gives us free proofs for two results about epimormorphisms corresponding to the ones about monomorphisms above. We also say that mono- and epi-morphisms are dual concepts.

Example: Non-surjective epimorphism

Consider the monoid homomorphism f from the natural numbers to the integers that takes every number to itself, that is

$f:\mathbb{N}\to \mathbb{Z}$, where $f(n)=n$ for all integers n.

The morphism f is clearly not surjective as a function in the category of sets. We claim it's an epimorphism in the category of monoids.

Let M be any monoid and let $g_1,g_2$ be any monoid homomorphisms $\mathbb{Z}\to M$, such that $g_1\circ f=g_2\circ f$. This means that $g_1$ and $g_2$ agree on all non-negative numbers. We must show that they agree on negative numbers also. We do this by induction.

$g_1(-1)=g_1(-1)\circ 1_M$

$=g_1(-1)\circ g_2(0)$

$=g_1(-1)\circ g_2(1+(-1))$

$=g_1(-1)\circ g_2(1)\circ g_2(-1)$

$=g_1(-1)\circ g_2(f(1))\circ g_2(-1)$

$=g_1(-1)\circ g_1(f(1))\circ g_2(-1)$

$=g_1(-1+1)\circ g_2(-1)$

$=1_M\circ g_2(-1)=g_2(-1)$

Now suppose we have proven $g_1(-n)=g_2(-n)$. We prove it for n+1 by

$g_1(-(n+1))=g_1((-n)+(-1))=g_1(-n)\circ g_1(-1)=g_2(-n)\circ g_2(-1)=g_2((-n)+(-1))=g_2(-(n+1)).$

Isomorphism

Isomorphism is a categorical analogy of bijection.

An isomorphism is a morphism $f:X\to Y$ that has an inverse morphism $g:Y\to X$ such that

$g\circ f=1_X$ and $f\circ g=1_Y$.

We say that objects X and Y are isomorphic, denoted $X\cong Y$, if there exists an isomorphism between them.

Inverses are unique, that is if h, g are both inverses of f, then h = g. The easy proof is left to reader as an exercise. This fact lets us speak of the inverse of f, written $f^{-1}$. Every isomorphism is monomorphism and epimorphism, but the converse is not true.

Example: morphisms in posets

In a partially ordered set morphisms are 'less-than-or-equal' relations. For any two objects a, b in a poset, there's at most one morphism from a to b. It follows that every morphism is monic and epic. On the other hand only morphisms with inverses are identity morphisms (proof: anti-symmetry).

Exercise: Duals of isomorphisms

Prove that if $f$ is an isomorphism in $𝒞$, then so is its correspondent (its dual) in ${𝒞}^{op}$.

Initial and terminal objects

In the next lesson we'll be looking at concepts defined by universal properties, which characterize things up to isomorphism, that is, any two things that have the property are isomorphic. In Category Theory, it is relatively unusual to be interested in actual identity: identity up to isomorphism is most often all that is of interest, in accord with the general focus on external behavior rather than internal construction. The simplest universal properties are those being initial and final objects:

An object A in a category $𝒞$ is an initial object, if for every object C in $𝒞$, there is exactly one arrow from A to C. Similarly an object A in a category $𝒞$ is a terminal object, if for every object C in $𝒞$, there is exactly one arrow from C to A. Some basic facts about these are:

• A initial object of $𝒞$ is a terminal object of ${𝒞}^{op}$, and vice-versa
• Initial and terminal objects are unique up to a unique isomorphism. That is if A and B are both initial objects, then there is a unique isomorphism from A to B.

Proof: exercises

Examples

• In the category of sets ( $𝒮et$) the empty set is an initial object. For any set X there is only one function from the empty set to set X, the empty function. Any set with only one element, a singleton set, is a terminal object. In $𝒮et$, there is in fact only one initial object, due to the axiom of extensionality. And, for any set X there is only one function from X to a singleton set, a constant function that has the same value on every element of X. There are many different singleton sets, but they are all isomorphic. These examples provide a further illustration of how 'internal' properties can be replaced by 'external' ones, since the notions of having zero elements or one can be described (for sets) in terms of the arrows from or to the set. Of course one has to do quite a bit of further development in order to describe all of the properties of sets 'externally'.

• The monoid with only one element, the identity element, is both initial and terminal object in the category of monoids. An object that is both initial and terminal is called a zero object. The zero object is only unique up to isomorphism.

• In a poset, the least element, if there is one, is an initial object, and the greatest element, if there is one, is a terminal object. Here the initial and terminal objects are fully unique.

Discussion

A few further points:

• An initial object in $𝒞$ is terminal in ${𝒞}^{op}$ (proof: trivial).
• Any arrow $f:1\to A$, where $1$ is a terminal object, is monic (proof: exercise)
• An arrow $f:1\to A$ is often called an 'element' of $A$. Can you identity the property of $𝒮et$ that motivates this terminological usage? (hint)

Hints and Details

Identities for Free Categories

The problem is that arrows are supposed to have unique domains and codomains, so the empty sequence technically can't serve as the identity arrow for every node in the graph (= object in the free category). A reasonable solution is to use the nodes themselves as their own identity arrows, and engineer this by brute force into the definition of composition.

Opposite Categories

Outline of proof that ${𝒞}^{op}$ is a category:

• the result of composition belongs to the opposite category by definition.
• composition is associative via a chain of identities involving the definition of opposite-composition and the associativity of the original category.
• the identities of the original category serve as identities for the opposite category.

Monomorphisms

• Suppose $f,g$ are monomorphisms, and $g\circ f\circ h=g\circ f\circ h^{\prime }$. Then $f\circ h=f\circ h^{\prime }$ (why?) and so $h=h^{\prime }$ (why), so $g\circ f$ is a monomorphism. QED

• Suppose $g\circ f$ is a monomorphism, and $f\circ h=f\circ h^{\prime }$. Then $g\circ f\circ h=g\circ f\circ h^{\prime }$, so $h=h^{\prime }$. Therefore, $f$ is a monomorphism. QED.

If you're new to algebraic proofs, make sure you understand the implicit role of associativity in these arguments

Other surjections

• Split epimorphism: every generalized element in codomain is an image of generalized element in domain. This is equivalent to condition that morphism has right-inverse.

  This condition is too strong for many algebraic categories. For example monoid homomorphism from $\mathbb{Z}$ to cyclic monoid $\mathbb{Z}/n\mathbb{Z}$ is not split epi.

• S-surjective: every $S\to \text{cod(f)}$ is an image of $S\to \text{dom(f)}$. If S is a separator, every $S\to \text{cod(f)}$ is monic and category has subobject classifier this is equivalent to epimorphism. (Lawvere&Rosebrugh P4.10)

  Monoid homomorphism $\mathbb{N}\to \mathbb{Z},n\mapsto n$ is not $\mathbb{N}$-surjective, since $n\mapsto -n$ is not in the image.

Arrows as Elements

If $1$ is a terminal object of $𝒮et$, and $A$ is an object of $𝒮et$, then there is a one-to-one correspondence between the conventional set-theoretic members of $𝒜$ and the arrows from $1$ to $A$.

Exercises

1. We say that an arrow $f:A\to B$ has a left inverse if there is an arrow $g:B\to A$ so that $g\circ f=1_A$. Suppose that $f$ has a left inverse and show that $f$ is a monomorphism.
2. Show that an epimorphism with a left inverse is an isomorphism.
3. Give an example of a category and an arrow in that category that is not an isomorphism but is both a monomorphism and epimorphism.

Related resources

• w:Category (mathematics)
• w:Morphism
• w:Monomorphism
• w:Epimorphism
• w:Initial object
• The Unapologetic Mathematician/Categories
• The Unapologetic Mathematician/Initial and Terminal Objects
• The Unapologetic Mathematician/Functors