Introduction to Category Theory/Categories
A category consists of the following data:
- Objects. These are referred to by generic symbols like .
- Arrows. These are referred to by generic symbols like .
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 , we assign a unique object denoted by . We say is from .
- Codomains. To every arrow , we assign a unique object denoted by . We say is to .
- Composition of arrows. For every two arrows and , if , then, there is an arrow such that and .
- Associativity of composition. For any three arrows and such that and , we have that .
- Existence of identity for each object. For every object , there is an arrow , called the identity arrow of A, such that
- and , and
- for every arrow , if then , and if then .
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 , we usually write to simultaneously show its domain and codomain. The collection of all arrows from to is written, depending on choice, as or . 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.
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 composes to the same thing no matter how it is parenthesized, as long as the order is kept. e.g. , etc.
- identities are unique. That is, if we have some such that for all and for all , then
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:
It's the two-sidedness of the property characterizing the identity that makes this work.
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 , 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 is a category, we get for free the results from the Discussion section above that identities are unique.
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.
The category of monoids 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.
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 to any object . So the relation `there is an arrow from to 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 and , 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.
The category of posets is a category, whose objects are posets and whose arrows are order preserving functions. If A and B are posets, then function is order preserving or monotone, if for every elements x and y in A . This is another example where algebraic systems of some type are the objects, and their homomorphisms the arrows.
Here we have objects () and arrows (), 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 and 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 of arrows in graph such that for all indexes i. The word freely means that two sequences and represent the same arrow if and only if they are the same sequence, that is
- and .
Composition of arrows is defined:
- If , , and cod =dom , then:
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.
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 , 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 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 is large, and any monoid is small. What about a poset, or ? Most of the large categories that people are interested in, such as , have the property that for any objects , 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.
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 , formed by retaining the objects of without change, but swapping the domain and codomain of each arrow. Composition is defined by the equation . Yet another way of making the point that arrows don't have to be functions. Here is an outline of the proof that really is a category. This is also often called the dual category.
For any categories , , we can form the pair category whose objects are pairs of objects from , , respectively, and whose arrows are pairs of arrows of , , respectively, such that if , , then
Composition is defined as:
This is basically a direct product construction, and generalizes straightforwardly to -tuples.
For any object of a category , the slice category of objects over , , has as objects those arrows of that have as their codomain. The arrows are a bit harder to describe. Suppose that and are objects of . Then of is also an arrow of , from to , if . 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.
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 is an arrow , and one . For to be an arrow from to , it must be the case that , 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 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 construction that would suffice would be to have the arrows of be triples of the form (original arrow, new domain, new codomain).
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 ( if and only if ). 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 which is left-cancellative in the following sense
- implies for all morphisms .
The situation described by these equations is often depicted by this diagram:
Put another way, map is monic if and only if the induced map is injective for all . Here is function such that for all in . 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 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 and are monomorphisms, then is one too,
- If is a monomorphism, then is one too.
Here are the proofs.
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 which is right-cancellative in the following sense:
Put another way, a map is epic if and only if the induced map is injective for all Z. Here is a function such that for all g in .
In the category 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 is an epimorphism in (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
- , where 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 be any monoid homomorphisms , such that . This means that and agree on all non-negative numbers. We must show that they agree on negative numbers also. We do this by induction.
Now suppose we have proven . We prove it for n+1 by
Isomorphism is a categorical analogy of bijection.
An isomorphism is a morphism that has an inverse morphism such that
- and .
We say that objects X and Y are isomorphic, denoted , 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 . 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 is an isomorphism in , then so is its correspondent (its dual) in .
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 , and vice-versa
- Initial and terminal objects are unique up to isomorphism. That is if A and B are both initial objects, then there is isomorphism from A to B.
- In the category of sets ( ) 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 , 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.
A few further points:
- An initial object in is terminal in (proof: trivial).
- Any arrow , where is a terminal object, is monic (proof: exercise)
- An arrow is often called an 'element' of . Can you identity the property of 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.
Outline of proof that 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.
- Suppose are monomorphisms, and . Then (why?) and so (why), so is a monomorphism. QED
- Suppose is a monomorphism, and . Then , so . Therefore, is a monomorphism. QED.
If you're new to algebraic proofs, make sure you understand the implicit role of associativity in these arguments
- 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 to cyclic monoid is not split epi.
- S-surjective: every is an image of . If S is a separator, every is monic and category has subobject classifier this is equivalent to epimorphism. (Lawvere&Rosebrugh P4.10)
- Monoid homomorphism is not -surjective, since is not in the image.
Arrows as Elements
If is a terminal object of , and is an object of , then there is a one-to-one correspondence between the conventional set-theoretic members of and the arrows from to .
- We say that an arrow has a left inverse if there is an arrow so that . Suppose that has a left inverse and show that is a monomorphism.
- Show that an epimorphism with a left inverse is an isomorphism.
- Give an example of a category and an arrow in that category that is not an isomorphism but is both a monomorphism and epimorphism.