talked about a bit<\/a> when I was writing about group theory. We take that concept of a function mapping from one set of values to another, and strip it down: the basic concept is something that provides a map from one thing to some other thing – and that’s all we want.<\/p>\nIn classic style, we’ll define a category<\/em> C as a tuple: (O, M, º)<\/code>, where:<\/p>\n\n- O, or Obj(C), is a set of objects<\/em>. Objects are anything<\/em> – we don’t care. Anything that we can define maps over.\n
- M, or Mor(C) is a set of arrows or morphisms. Every arrow has a unique source<\/em> and a unique target<\/em>, both of which are objects in M. Given two objects a and b in O, we also write Mor(a,b) for the set of morphisms from a to b. To talk about a specific morphism from a to b, we write it as “name : a → b”; as in “f : int → int”.\n
- º is a binary operation that is the abstraction of function composition; º is a mapping from (Mor(a,b), Mor(b,c)) to Mor(a,c). It’s got the basic properties of function composition:\n
\n- Associativity: (∀ f : a → b, g : b → c, h : c → d) h º (g º f) = (h º g) º f\n
- Identity: (∀ a,b ∈ O(C)) (exists 1a<\/sub>, 1b<\/sub> ∈ Mor(C)) (∀ f : a → b) 1b<\/sub> º f = f = f º 1a<\/sub>.\n<\/ol>\n<\/ul>\n
One neat little trick to simplify things is that we can actually throw away Obj(C), and replace it with the set of identity morphisms: since there is exactly one identity morphism per object, there’s no real need to distinguish between the identity morphism and the object. It’s a nice trick because it means that we have nothing but morphisms all the way down; but it’s really just a trick. We can talk about Obj(C); or Id(C); but we still need to be able to talk about the objects in some way, whether they’re just a subset of the morphisms, or something distinct.<\/p>\n
Now, we get to something about category theory that I really don’t like. Category theory is front-loaded with rather a lot of definitions about different kinds of morphisms and different kinds of categories. The problem with that is that these definitions are very important, but we don’t have enough of the theory under our belts to be able to get much of a sense for why we should care about them, or what their intuitive meaning is. But that’s the way it goes sometimes; you have to start somewhere. It will<\/em> make sense eventually, and you’ll see why these definitions matter.<\/p>\nThere are a lot of special types of morphisms, defined by properties. Here’s the basic list:<\/p>\n
\n- A monic<\/em> (or monomorphism) is an arrow f : a → b such that (∀ g1<\/sub> , g2<\/sub>: x → a) f º g1<\/sub> = f º g2<\/sub> ⇒ g1<\/sub> = g2<\/sub>. (That is, if any two arrows composed with f in f º g end up at the same object only if they are the same.)\n
- An epic<\/em> (or epimorphism) is an arrow f : a → b such that (∀ g1<\/sub> , g2<\/sub>: b → x) g1<\/sub> º f = g2<\/sub> º f ⇒ g1<\/sub> = g2<\/sub>. (This is almost the same as a monic, but it’s from the other side of the composition; instead of (f º g) in the definition, it’s (g º f).)\n
- An isomorphism<\/em> is an arrow f : a → b such that (∃ g : b → a) f º g = 1b<\/sub> ∧ g º f = 1a<\/sub>.\n
- An endomorphism<\/em> is an arrow f : a → b such that a = b.\n
- An automorphism<\/em> is an arrow that is both an endmorphism and an isomorphism.\n<\/ul>\n
One last definition, just because it gives me a chance to point out something useful about category theory. A functor<\/em> is a morphism in the category of all categories. What that means is that it’s a structure-preserving mapping between categories. It’s neat in a theoretical way, because it demonstrates that we’re already at a point where we’re seeing how category theory can make it easier to talk about something complicated: we’re using it to describe itself! But the concept of functor also has a lot of applications; in particular, the module system of my favorite programming language makes extensive use of functors.<\/p>\n In Ocaml, a module is something called a structure, which is a set of definitions with constrained types. One of the things you often want to be able to do is to write a piece of code in a way that allows you to make it parametric on some other structure. The way you do that is to write a functor: a “function” from a structure to a structure. For example, to implement a generic binary tree, you need a type of values that you’ll put in the tree; and an operation to compare values. The way you do that is to write a functor which takes a structure defining a type and a comparison operator, and mapping it to a structure which is an implementation of a binary tree for that type and comparison.<\/p>\n
The Ocaml functor is a category theoretic functor: category theory provides an easy way to talk about the concept of the compile-time “function” from structure to structure.<\/p>\n","protected":false},"excerpt":{"rendered":"
To get started, what is category theory? Back in grad school, I spent some time working with a thoroughly insane guy named John Case who was the new department chair. When he came to the university, he brought a couple of people with him, to take temporary positions. One of them was a category theorist […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[76,24],"tags":[],"class_list":["post-9","post","type-post","status-publish","format-standard","hentry","category-category-theory","category-goodmath"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-9","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/9","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=9"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/9\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=9"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=9"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=9"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}