Category Intuition by Example

11 Replies

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.

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?

In some sense, the point of category theory is that it doesn’t matter. 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.

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.

The Category Set

One of the easiest examples is the category Set. The objects of the category are, obviously, sets; the morphisms are functions between sets; and composition is (obviously) function composition.

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?

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 a value of the range is mapped to, you know which value in the domain mapped to it.

The key property of the monomorphism is that it’s left-cancellative – 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 the left side of the composion. Why? Because we know that f maps each value in its domain to a unique 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.

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 one value that maps to it. It’s right-cancellative in the same way that the monomorphism is left-cancellative.

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.

The Category Poset

Poset is the category of partially ordered sets. A partially ordered set is a set with a binary relation, le, which satisfies the following properties:

  1. Reflexivity: forall a: a le a
  2. Antisymmetry: if a le b land b le a then a = b.
  3. Transitivity: if a le b land b le c then a le c

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

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 it needs to be a surjective function that preserves the ordering relation.

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.

  • Suppose we have arrows f : A rightarrow B, g : B rightarrow C. We know that f and g are monotonic functions.
  • 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).
  • Likewise, for any pair s,t in the domain of g, we know that if s le t, then g(s) le g(t).
  • 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))

The category Grp

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

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.

These are all, of course, very simple examples. They’re all concrete 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.

11 thoughts on “Category Intuition by Example”

  1. Ivan Nilin Navi

    “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.”

    A group homomorphism need not be surjective, and hence need not be reversible.

    Reply ↓
  2. stigant

    >> But in Poset it needs to be a surjective function that preserves the ordering relation.

    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.
    <<

    Don't we need monotonically _increasing_ functions to preserve the order? For example, let f(x) = -x on the poset of real numbers. f(x) is monotonic, but decreasing. if a f(b), so f doesn’t preserve the ordering. I guess you could say that f maps the poset (R,). But given that f:R->R, that’s not an intuitive notion.

    Reply ↓
    1. stigant

      ugg, I think half that comment got lost in inadvertent tags. It should say if a is less than b then f(a) is greater than f(b). Then, the solution is to say that f maps the poset (R, less than) to the poset (R, greater than) rather than mapping (R, less) to itself.

      Reply ↓
      1. outis

        (ℝ,≥) is a perfectly valid (if seemingly perverse) poset, so f(x) = -x is a perfectly valid functor (ℝ,≤) → (ℝ,≥), even though it’s not a functor (ℝ,≤) → (ℝ,≤). I suppose you could call it counter-intuitive, but that only if your intuition says “≤” in the definition of posets is “less than or equal”, which it isn’t. Structurally, ≤ and ≥ are the same; you could just as easily use ≥ to symbolize the poset relation in the definition. Let ≤⁻ = ≥ (so f: (ℝ,≤) → (ℝ, ≤⁻), if it helps.

        Reply ↓
        1. outis

          Just realized MarkCC’s Poset example isn’t couched in terms of functors; that’s something I got from Awodey. In MarkCC’s terms, (ℝ,≥), being a poset, is an object of Poset.

          Reply ↓
  3. Doug Spoonwood

    “a monomorphism is still a surjective function” I think you meant “a monomorphism is still an injective function” or “an epimorphism is still a surjective function”.

    Reply ↓
    1. Mark C. Chu-Carroll

      I’ve got one debunking post that I’m in the process of writing; it’ll go up probably this evening.

      Aside from that, I’ve been too busy to find good crap to debunk; if you have any suggestions, please send them to me!

      Reply ↓

  5. Pingback: Weekly List Bookmarks (weekly) | Eccentric Eclectica @ ToddSuomela.com

  6. outis

    Dear readers,

    There’s also the examples of group categories and poset categories (shamelessly lifted from Awodey), which are interesting because their arrows aren’t mappings. Unlike Grp, there’s a different group category for each group; a similar distinction exists between Poset (the category of posets) and poset categories.

    Each group category has only one object (which is arbitrary and unrelated to the group). Group elements are the arrows and the group operation becomes the composition operation.

    For poset categories, the objects are the elements of the ordered set. The arrows are defined by:

    a → b ⇔ a ≤ b

    Composition arises naturally as a consequence of the transitive property of ≤. For f = a → b and g = b → c:

    g ∘ f = a → c

    Reply ↓

Leave a Reply