Learning Category Theory, examples

To specify a category, we have to give a set of objects, and for each pair of objects a set of morphisms between them. We then have to define a way to compose morphisms that is associative. If we have, for each object, a unique identity morphism, then we have defined our category.

If we take objects as sets and the morphisms as functions, then composition is just the composition of functions. This is clearly associative, and for each set there is definitely an identity function.

If we take objects as groups and group homomorphisms as morphisms. Group homomorphisms are simply function that satisfy the following axioms: for groups G and F a group homomorphism is a function f:F -> G such that, with e the identity, f(e) = e and for x and y in G with additive notation f(x+y) = f(x)+f(y) and f(-x) = -f(x). Allow me my abuse of notation where the "e", "-", and "+" have different meanings on the left and right hand side of the equations. Since function composition is associative, group homomorphism composition is associative and there is clearly a identity function for each group- the identity function on the underlying set.

To see that categories are not just about categories for different mathematical theories, lets look at posets. A poset is a set with a partial order. A partial order is an reflexive, antisymmetric, transitive relation. While there is certainly a category of posets, with posets as objects and monotone functions as morphisms, each poset is itself a category. To see this take the objects as the underlying set of the poset. For each pair of objects the set of morphisms is empty if the objects are not related, and it is the set containing the empty set if they are. Clearly for all elements "a" in the underlying set, a <= a (a is related to a) so the morphisms from a to a contains one and only one morphism, the identity. Composition comes directly from the need to make the relation transitive- the composition of two morphisms is the set containing the empty set if the objects in the source and the target of the composite are related.

Another example of a structure that has both a category and is a category is monoids. The category of monoids, Mon, is very much like Grp but without negation. To see that each monoid is itself a category, take a monoid, M, and form the category where the objects to be a single object, perhaps the empty set, and the morphisms the elements of the monoid. Then the composition of morphisms (elements of the monoid) is the action of the monoid. All morphisms in this category are composable as they all have the same source and destination. The associativity and identity are given by the associativity and identity of the monoid.

So, we have seen some examples of categories. Next time perhaps I will go into some of the ways that category theory is used in Haskell by introducing Functors and showing different ways to think about them.