After a long hiatus (sorry about that!), I would like to resume the series on Stone duality. You may recall I started this series by saying that my own point of view on mathematics is strongly informed by category theory, followed by a little rant about the emotional reactions that category theory seems to excite in many people, and that I wouldn’t be “blathering” about categories unless a strong organic need was felt for it. Well, it’s come to that point: to continue talking sensibly about Stone duality, I really feel some basic concepts of category theory are now in order. So: before we pick up the main thread again, I’ll be talking about categories up to the point of the central concept of adjoint pairs, generalizing what we’ve discussed before in the context of truth-valued matrix algebra.
I’ll start by firmly denouncing a common belief: that category theory is some arcane, super-abstract subject. I just don’t believe that’s a healthy way of looking at it. To me, categories are no more and no less abstract than groups, rings, fields, etc. — they are just algebraic structures of a certain type (and a not too complicated type at that). That said, they are particularly ubiquitous and useful structures, which can be studied either as small structures (for example, posets provide examples of categories, and so do groups), or to organize the study of general types of structure in the large (for example, the class of posets and poset morphisms forms a category). Just think of them that way: they are certain sorts of algebraic structures which crop up just about everywhere, and it is very useful to learn something about them.
Usually, the first examples one is shown are large categories, typically of the following sort. One considers the class of mathematical structures of a given type: it could be the class of groups, or of posets, or of Boolean algebras, etc. The elements of a general such class are given the neutral name “objects”. Then, we are also interested in how the objects are related to each other, typically through transformations which “preserve” the given type of structure. In the case of sets, transformations are just functions; in the case of groups, the transformations are group homomorphisms (which preserve group multiplication, inversion, and identities); in the case of vector spaces, they are linear transformations (preserving vector addition and scalar multiplication); in the case of topological spaces, they are continuous maps (preserving a suitable notion of convergence). In general, the transformations are given the neutral name “homomorphisms”, or more often just “morphisms” or “maps”.
In all of these cases, two morphisms , compose to give a new morphism (for example the composite of two group homomorphisms is a group homomorphism), and do so in an associative way (), and also there is an identity morphism for each object which behaves as identities should ( for any morphism ). A collection of objects, morphisms between them, together with an associative law of composition and identities, is called a category.
A key insight of category theory is that in general, important structural properties of objects can be described purely in terms of general patterns or diagrams of morphisms and their composites. By means of such general patterns, the same concept (like the concept of a product of two objects, or of a quotient object, or of a dual) takes on the same form in many different kinds of category, for many different kinds of structure (whether algebraic, or topological, or analytic, or some mixture thereof) — and this in large part gives category theory the power to unify and simplify the study of general mathematical structure. It came as quite a revelation to me personally that (to take one example) the general idea of a “quotient object” (quotient group, quotient space, etc.) is not based merely on vague family resemblances between different kinds of structure, but can be made absolutely precise and across the board, in a simple way. That sort of explanatory power and conceptual unification is what got me hooked!
In a nutshell, then, category theory is the study of commonly arising structures via general patterns or diagrams of morphisms, and the general application of such study to help simplify and organize large portions of mathematics. Let’s get down to brass tacks.
Definition: A category consists of the following data:
- A class of objects;
- A class of morphisms;
- A function which assigns to each morphism its domain, and a function which assigns to each morphism its codomain. If , we write to indicate that and .
- A function , taking an object to a morphism , called the identity on .
Finally, let denote the class of composable pairs of morphisms, i.e., pairs such that . The final datum:
- A function , taking a composable pair to a morphism , called the composite of and .
These data satisfy a number of axioms, some of which have already been given implicitly (e.g., and ). The ones which haven’t are
- Associativity: for each composable triple .
- Identity axiom: Given , .
Sometimes we write for the class of objects, for the class of morphisms, and for , for the class of composable -tuples of morphisms.
Nothing in this definition says that objects of a category are “sets with extra structure” (or that morphisms preserve such structure); we are just thinking of objects as general “things” and depict them as nodes, and morphisms as arrows or directed edges between nodes, with a given law for composing them. The idea then is all about formal patterns of arrows and their compositions (cf. “commutative diagrams”). Vishal’s post on the notion of category had some picture displays of the categorical axioms, like associativity, which underline this point of view.
In the same vein, categories are used to talk about not just large classes of structures; in a number of important cases, the structures themselves can be viewed as categories. For example:
- A preorder can be defined as a category for which there is at most one morphism for any two objects . Given there is at most one morphism from one object to another, there is no particular need to give it a name like ; normally we just write to say there is a morphism from to . Morphism composition then boils down to the transitivity law, and the data of identity morphisms expresses the reflexivity law. In particular, posets (preorders which satisfy the antisymmetry law) are examples of categories.
- A monoid is usually defined as a set equipped with an associative binary operation and with a (two-sided) identity element for that operation. Alternatively, a monoid can be construed as a category with exactly one object. Here’s how it works: given a monoid , define a category where the class consists of a single object (which I’ll give a neutral name like ; it doesn’t have to be any “thing” in particular; it’s just a “something”, it doesn’t matter what), and where the class of morphisms is defined to be the set . Since there is only one object, we are forced to define and for all . In that case all pairs of morphisms are composable, and composition is defined to be the operation in : . The identity morphism on is defined to be . We can turn the process around: given a category with exactly one object, the class of morphisms can be construed as a monoid in the usual sense.
- A groupoid is a category in which every morphism is an isomorphism (by definition, an isomorphism is an invertible morphism, that is, a morphism for which there exists a morphism such that and ). For example, the category of finite sets and bijections between them is a groupoid. The category of topological spaces and homeomorphisms between them is a groupoid. A group is a monoid in which every element is invertible; hence a group is essentially the same thing as a groupoid with exactly one object.
Remark: The notion of isomorphism is important in category theory: we think of an isomorphism as a way in which objects are the “same”. For example, if two spaces are homeomorphic, then they are indistinguishable as far as topology is concerned (any topological property satisfied by one is shared by the other). In general there may be many ways or isomorphisms to exhibit such “sameness”, but typically in category theory, if two objects satisfy the same structural property (called a universal property; see below), then there is just one isomorphism between them which respects that property. Those are sometimes called “canonical” or “god-given” isomorphisms; they are 100% natural, no artificial ingredients!
Earlier I said that category theory studies mathematical structure in terms of general patterns or diagrams of morphisms. Let me give a simple example: the general notion of “cartesian product”. Suppose are two objects in a category. A cartesian product of and is an object together with two morphisms , (called the projection maps), satisfying the following universal property: given any object equipped with a map for , there exists a unique map such that for . (Readers not familiar with this categorical notion should verify the universal property for the cartesian product of two sets, in the category of sets and functions.)
I said “a” cartesian product, but any two cartesian products are the same in the sense of being isomorphic. For suppose both and are cartesian products of . By the universal property of the first product, there exists a unique morphism such that for . By the universal property of the second product, there exists a unique morphism such that . These maps and are inverse to one another. Why? By the universal property, there is a unique map (namely, ) such that for . But also satisfies these equations: (using associativity). So by the uniqueness clause of the universal property; similarly, . Hence is an isomorphism.
This sort of argument using a universal property is called a universality argument. It is closely related to what we dubbed the “Yoneda principle” when we studied posets.
So: between any two products of and , there is a unique isomorphism respecting the product structure; we say that any two products are canonically isomorphic. Very often one also has chosen products (a specific choice of product for each ordered pair ), as in set theory when we construe the product of two sets as a set of ordered pairs . We use to denote (the object part of) a chosen cartesian product of .
Exercise: Use universality to exhibit a canonical isomorphism . This is called a symmetry isomorphism for the cartesian product.
Many category theorists (including myself) are fond of the following notation for expressing the universal property of products:
where the dividing line indicates a bijection between pairs of maps and single maps into the product, effected by composing with the pair of projection maps. We have actually seen this before: when the category is a poset, the cartesian product is called the meet:
In fact, a lot of arguments we developed for dealing with meets in posets extend to more general cartesian products in categories, with little change (except that instead of equalities, there will typically be canonical isomorphisms). For example, we can speak of a cartesian product of any indexed collection of objects : an object equipped with projection maps , satisfying the universal property that for every -tuple of maps , there exists a unique map such that . Here we have a bijection between -tuples of maps and single maps:
By universality, such products are unique up to unique isomorphism. In particular, is a choice of product of the collection , as seen by contemplating the bijection between triples of maps and single maps
and similarly is another choice of product. Therefore, by universality, there is a canonical associativity isomorphism
Remark: It might be thought that in all practical cases, the notion of cartesian product (in terms of good old-fashioned sets of tuples) is clear enough; why complicate matters with categories? One answer is that it isn’t always clear from purely set-theoretic considerations what the right product structure is, and in such cases the categorical description gives a clear guide to what we really need. For example, when I was first learning topology, the box topology on the set-theoretic product seemed to me to be a perfectly natural choice of topology; I didn’t understand the general preference for what is called the “product topology”. (The open sets in the box topology are unions of products of open sets in the factors . The open sets in the product topology are unions of such products where for all but finitely many .)
In retrospect, the answer is obvious: the product topology on is the smallest topology making all the projection maps continuous. This means that a function is continuous if and only if each is continuous: precisely the universal property we need. Similarly, in seeking to understand products or other constructions of more abstruse mathematical structures (schemes for instance), the categorical description is de rigeur in making sure we get it right.
For just about any mathematical structure we can consider a category of such structures, and this applies to the notion of category itself. That is, we can consider a category of categories! (Sounds almost religious to me: category of categories, holy of holies, light of lights…)
- Remark: Like “set of sets”, the idea of category of categories taken to a naive extreme leads to paradoxes or other foundational difficulties, but there are techniques for dealing with these issues, which I don’t particularly want to discuss right now. If anyone is uncomfortable around these issues, a stopgap measure is to consider rather the category of small categories (a category has a class of objects and morphisms; a small category is where these classes are sets), within some suitable framework like the set theory of Gödel-Bernays-von Neumann.
If categories are objects, the morphisms between them may be taken to be structure-preserving maps between categories, called “functors”.
Definition: If and are categories, a functor consists of a function (between objects) and a function (between morphisms), such that
- and , for each morphism (i.e., preserves domains and codomains of morphisms);
- for each object , and for each composable pair (i.e., preserves identity morphisms and composition of morphisms).
Normally we are not so fussy in writing or ; we write and for morphisms and objects alike. Sometimes we drop the parentheses as well.
If are groups or monoids regarded as one-object categories, then a functor between them amounts to a group or monoid homomorphism. If are posets regarded as categories, then a functor between them amounts to a poset map. So no new surprises in these cases.
Exercise: Define a product of two categories , and verify that the definition satisfies the universal property of products in the “category of categories”.
Exercise: If a category has chosen products, show how a functor may be defined which takes a pair of objects to its product . (You need to define the morphism part of this functor; this will involve the universal property of products.)
15 comments
Comments feed for this article
June 29, 2008 at 12:32 pm
Basic Category Theory, II « Todd and Vishal’s blog
[…] on naturality in a moment. Let me first give a few more examples of universal constructions. Last time we discussed the general concept of a cartesian product — obviously in honor of Descartes, […]
July 12, 2008 at 12:21 am
36th Carnival of Mathematics « Todd and Vishal’s blog
[…] most of you already know about it. Among other articles/posts, one of Todd’s recent post Basic Category Theory I is part of the carnival. He followed it up with another post titled Basic Category Theory II. There […]
July 12, 2008 at 12:41 pm
Basic Category Theory, III: Representability, adjoints, and the Yoneda lemma « Todd and Vishal’s blog
[…] requires some preface. First, we need the following fundamental construction: for every category there is an opposite category , having the same classes of objects and morphisms as , but with […]
July 18, 2008 at 5:54 pm
Ultrafilter convergence, compactness, and the spectrum of a Boolean algebra « Todd and Vishal’s blog
[…] | Tags: spectrum, Stone-Cech compactification, ultrafilter | by Todd Trimble After this brief (?) categorical interlude, I’d like to pick up the main thread again, and take a closer look […]
August 28, 2008 at 12:32 pm
Jocelyn Paine
I enjoyed this article, and have passed it to some cognitive science colleagues I am trying to persuade of category theory’s explanatory power and conceptual unification — pointing them at your example of the quotient object as a construction that can be instantiated in many different kinds of mathematical structure.
Also to help explain category theory, I’ve been coding some interactive Web-based demonstrations. I’d like to mention them here, because they demonstrate properties of products. They’re at http://www.j-paine.org/cgi-bin/webcats/webcats.php. Pressing the “Many Products” button will generate a product (X,π1, π2) in the category of finite sets that isn’t the “chosen product”, and will show its projections π1, π2 and its isomorphism to the “chosen product”. The “Universality” button generates a set Y, and shows the unique morphism f from it to the product X. I’ll be adding more as I have time.
August 28, 2008 at 1:24 pm
Todd Trimble
Thanks! I’ve seen some of your comments over at the n-Category Café and was intrigued, although I don’t have much understanding of the areas you describe. For those who are reading this, I’ll point them to this comment of yours in particular (some of what you describe of HRRs and analogical reasoning reminds me of an infamous encounter between Hofstadter and Feynman).
I like your Web-based demonstrations, and I hope they can be made more vividly graphical or diagrammatic — that would make them great tools for learning category theory.
August 28, 2008 at 5:23 pm
Jocelyn Paine
Brilliant! I’m really pleased that you like the demonstrations. Some of the code arose from experiments in mechanising Goguen’s sheaf semantics of interacting objects, and I’ve got quite a bit more to put up.
I agree wholeheartedly about graphics, and I’d like to point you at a posting I made on my Dr Dobbs blog spot, Finding the Best Metaphors will be the Work of a Generation. Look at the quotation from Hans Moravec, but also scroll down and see the comments. I’ve said a bit there about why I want to promote category theory, and about the rôle of graphics.
That’s for the future, but one can also use “graphic” imagery in words. I’ve just added such a section to the end of the “Many Products” demo, to try conveying the notion that it’s the arrows, not the objects, that are really important. The world’s first category theory text adventure! What do you think?
I’d love to read about that encounter between Hofstadter and Feynman. Do you have a reference?
August 28, 2008 at 7:29 pm
Todd Trimble
If memory serves, the story is recounted in Genius by James Gleick, a biography of Feynman. I don’t have the book to hand, but if/when I do I can copy out the relevant passage.
Hofstadter gives some details in the P.S. and P.P.P.S. to his article “Analogies and Roles in Human and Machine Thinking” (reproduced in Metamagical Themas), p. 574 and p. 603 respectively. In the P.S. he writes
And then from the P.P.P.S.:
August 28, 2008 at 8:16 pm
Todd Trimble
I just looked at your posting on the Dr Dobbs blog spot, and free associating a little on the “kinaesthetic virtual machine”, I’m reminded of the way that category theorists wave their hands about at commutative diagrams to explain what they’re thinking. And how back in the early 60s, Eilenberg challenged Peter Freyd to formalize the logic underlying some of this handwaving, which Freyd wrote an article on maybe 15 years later (in Algebra, Topology, and Category Theory, ed. A. Heller and M. Tierney). An updated account can be found in the remarkable book Categories, Allegories by Freyd and Scedrov (look for the material on Q-sequences).
Regarding Erdős’s hand-flapping: I often wonder if Erdős was in fact autistic (Asperger’s or the like) — hand-flapping is a very marked characteristic in autistic children, which perhaps he never outgrew. Hard to know for sure.
August 29, 2008 at 5:39 pm
Jocelyn Paine
Interesting – I must look at Categories, Allegories.
Free-associating myself, your remark about category theorists explaining their thoughts, and about formalising the underlying logic, made me think about formalising the purpose of categorical constructions. (Or of any other mathematical construction.)
I’m going to connect this with a project called BOWiki. This is a wiki which uses the same software as Wikipedia, augmented so that it can store machine-readable logical assertions about wiki entries.
There are many such wikis; BOWiki’s authors intend their assertions to record information about the purpose of specific genes, proteins, and other biological entities. In the sense of purpose towards achieving a goal.
For example, the purpose of the heart is to pump blood. The purpose of a red blood cell is to transport oxygen. The purpose of some particular protein might be to switch on the gene that codes for another protein that strengthens cell walls.
The authors use the so-called “Ontology of Functions”. I don’t know much about this, and how generic a term it is: the wiki seems to be almost empty, and though it links to online papers, they don’t give much detail. You can get the gist from BOWiki a collaborative annotation and ontology curation framework, by Michael Backhaus and Janet Kelso. They illustrate with the following piece of machine-readable logic, embedded in the wiki page for a protein called MAL21:
[[realizes::function=sugar transporter activity;
realization=sugar transport;
context=human body]]
Getting back to category theory, it would be a nice project to build a categorists’ version of BOWiki, that records the purpose of categorical constructions and proof steps. Including the diagram handwaving. For example, the purpose of a colimit (at least in computing) is often to “put things together”, as Ronald Brown and Timothy Porter suggest in their Category Theory and Higher Dimensional Algebra: potential descriptive tools in neuroscience.
Such an encyclopaedia could be very useful in teaching, in that humans find it easier — don’t we? — to understand tools when we know what they are used for.
August 29, 2008 at 8:34 pm
Todd Trimble
Let a thousand flowers bloom! I expect such an encyclopedia could be very useful for certain types of top-down learners, and would be generally worthwhile to have around. It would need some careful planning, though.
You may be aware that the Fields Medalists Tim Gowers and Terence Tao are both keenly interested in developing a “Tricks Wiki” which explains various “tricks” or methods of mathematical proof and research strategies and when to deploy them. Tim Gowers is also quite interested in automatic theorem proving and has very thoughtful things to say about this, as can be gleaned from this article which discusses what it means to say a proof is “deep”.
I for my own modest part am contemplating writing a blog series on categorical set theory, which is an approach to foundations of mathematics alternative to ZFC, and which could become a useful module for describing some purposes of various categorical constructions. It would also be intended to build bridges between “naive” set theory and a formal function-based set theory.
September 1, 2008 at 8:07 am
ZFC and ETCS: Elementary Theory of the Category of Sets « Todd and Vishal’s blog
[…] got finished first, and I thought that it would be of interest to some who have been following my category theory […]
September 12, 2008 at 2:00 pm
Jocelyn Paine
A quick note to say that to the online demos mentioned earlier I’ve added demonstrations of initial objects, terminal objects, and coproducts in the category of finite sets. And diagrams. Not very vivid yet — finding the right graphics software is difficult.
October 19, 2008 at 8:18 pm
Jocelyn Paine
Yet another update about the online demos. I’ve added equalisers and coequalisers; and as one might therefore hope, pullbacks, pushouts, limits, and colimits. The “Generate and demonstrate a limit” button works by generating a random graph using the Erdős-Rényi G(n, p) method, which, given a number of nodes, connects each pair of nodes with a specified probability. Turn the result into a categorical diagram, randomly generate a functor into the category of finite sets, take the limit by decomposing into products and equalisers, and plot. Colimits work dually.
December 5, 2008 at 7:44 pm
Can Category Theory Serve as the Foundation of Mathematics? « Combinatorics and more
[…] Trible wrote (on Todd’s and Vishal Blog) a series of posts ( I, II, III) on category theory, and additional posts (I,II) on category theory and axiomatic set […]