{"id":1550,"date":"2011-10-09T20:30:01","date_gmt":"2011-10-10T00:30:01","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/?p=1550"},"modified":"2011-10-09T20:30:01","modified_gmt":"2011-10-10T00:30:01","slug":"category-intuition-by-example","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2011\/10\/09\/category-intuition-by-example\/","title":{"rendered":"Category Intuition by Example"},"content":{"rendered":"

The good thing about category theory is that it abstracts everything down to a couple of very simple, bare-bones concepts, and lets us play with those concepts in really fascinating ways. But the bad thing about category theory is that it abstracts everything down so much that it can be difficult to have any intuitive sense about what things actually mean.<\/p>\n

We said that a category is, basically, a collection of objects connected by arrows, and a composition operation over the arrows. But what the heck is an object, and what is an arrow?<\/p>\n

In some sense, the point of category theory is that it doesn’t matter<\/em>. There’s a set of fundamental concepts that underly all composable mapping-like things, and category theory focuses in on those fundamental concepts, and what they mean.<\/p>\n

But still, to understand category theory, you need to be able to get some kind of intuitive handle on what’s going on. And so, we’ll take a look at a few examples.<\/p>\n

The Category Set<\/b><\/h2>\n

One of the easiest examples is the category Set<\/b>. The objects of the category are, obviously, sets; the morphisms are functions between sets; and composition is (obviously) function composition.<\/p>\n

That much is easy. Now, what about the special arrows? What do all of the epi, iso, endo, and auto arrows in the category of sets?<\/p>\n

An monomorphism over the category of sets is an injective function – that is, a function which maps each value in the domain to a distinct value in the range. So you can always reverse the function: given a value in the range of the function, you can always say, specifically, exactly what value in the domain maps to it. In a monomorphism in the category set, there may be values in the target of the morphism that aren’t mapped to by any element of the range; but if<\/em> a value of the range is mapped to, you know which value in the domain mapped to it.<\/p>\n

The key property of the monomorphism is that it’s left-cancellative<\/em> – that is, if f is a monomorphism, then we know that f circ g == f circ h is only true if g = h. We can cancel<\/em> the left side of the composion. Why? Because we know that f maps each value in its domain to a unique<\/em> value in its range. So f circ g and f circ h can only be the same if they map all of the same values in their domain to the same values in their range – that is, if they’re the same function.<\/p>\n

An epimorphism is an onto function – that is, a mapping f from a set X to a set Y in which for every value y in Y, there’s some value in x in X such that f(x)=y. It’s a dual of the notion of a monomorphism; for each value in the range, there is at least one value in the domain that maps to it. But it’s not necessary that the domain values be unique – there can be multiple values in the domain that map onto a particular value in the range, but for every element of the domain, there’s always at least<\/em> one value that maps to it. It’s right-cancellative<\/em> in the same way that the monomorphism is left-cancellative.<\/p>\n

What about iso-morphism? If you combine the ideas of mono-morphism and epi-morphism, what you end up with is a function where every member of the domain is mapped onto a unique value in the range, and every value in the range is mapped onto by at least one value: it’s a one-to-one function. <\/p>\n

The Category Poset<\/b><\/h2>\n

Poset<\/b> is the category of partially ordered sets<\/em>. A partially ordered set is a set with a binary relation, le, which satisfies the following properties:<\/p>\n

    \n
  1. Reflexivity: forall a: a le a<\/li>\n
  2. Antisymmetry: if a le b land b le a then a = b.<\/li>\n
  3. Transitivity: if a le b land b le c then a le c<\/li>\n<\/ol>\n

    In the category of partially ordered sets, the arrows are monotonic<\/em> functions – that is, functions that preserve the partial ordering. So if x le y, then if f is monotonic, f(x) le f(y).<\/p>\n

    The arrow composition operation, circ, is still just function composition. In terms of meaning, it’s pretty much the same as it was for simple sets: a monomorphism is still a surjective function; etc. But in Poset<\/b> it needs to be a surjective function that preserves the ordering relation.<\/p>\n

    We know that monotonic functions fit the associative and identity properties of category arrows – they’re still just functions, and monotonicity has no effect on those. But for posets, the composition is a bit tricky – we need to ensure that composition maintains the partial order. Fortunately, that’s easy. <\/p>\n

      \n
    • Suppose we have arrows f : A rightarrow B, g : B rightarrow C. We know that f and g are monotonic functions.<\/li>\n
    • So for any pair of x and y in the domain of f, we know that if x le y, then f(x) le f(y). <\/li>\n
    • Likewise, for any pair s,t in the domain of g, we know that if s le t, then g(s) le g(t).<\/li>\n
    • So we just put those together: if x le y, then f(x) le f(y). f(x) and f(y) are in the domain of g, so if f(x) le f(y) then we know g(f(x)) le g(f(y))<\/li>\n<\/ul>\n

      The category Grp<\/b><\/h2>\n

      Our last example is the category of groups<\/em>, which is called Grp<\/b>. In this category, the objects are (obviously) groups. What are arrows? Group homomorphisms – that is, essentially, functions between sets that preserve the group structure.<\/p>\n

      What’s a homomorphism in this category? That’s a bit confusing, because we get stuck with some overloaded terminology. But it’s basically just a symmetry-preserving surjection – that is, it’s a reversable mapping from a group into a second group, where the group symmetry of the first group is mapped onto the group symmetry of the second by the arrow. You should be able to follow the meanings of the other kinds of morphisms by using similar reasoning.<\/p>\n

      These are all, of course, very simple examples. They’re all concrete<\/em> categories, where the objects are (speaking very loosely) sets. There are categories – many very interesting ones – where the objects aren’t sets or even particularly set-like – but we’ll get to those later. For now, the ideas of objects as sets gives you an intuitive handle to grab onto.<\/p>\n","protected":false},"excerpt":{"rendered":"

      The good thing about category theory is that it abstracts everything down to a couple of very simple, bare-bones concepts, and lets us play with those concepts in really fascinating ways. But the bad thing about category theory is that it abstracts everything down so much that it can be difficult to have any intuitive […]<\/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],"tags":[],"class_list":["post-1550","post","type-post","status-publish","format-standard","hentry","category-category-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-p0","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/1550","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=1550"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/1550\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=1550"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=1550"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=1550"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}