Introduction to Category Theory/Categories

Categories

edit

Definition

edit

A category   consists of the following data:

  • Objects. These are referred to by generic symbols like   .
  • Arrows. These are referred to by generic symbols like   .

These data are required to satisfy the following axioms:

  • An object is not an arrow; an arrow is not an object.
  • Domains. To every arrow  , we assign a unique object denoted by  . We say   is from   .
  • Codomains. To every arrow  , we assign a unique object denoted by  . We say   is to   .
  • Composition of arrows. For every two arrows   and  , if  , then, there is an arrow   such that   and   .
  • Associativity of composition. For any three arrows   and   such that   and  , we have that   .
  • Existence of identity for each object. For every object  , there is an arrow  , called the identity arrow of A, such that
    •   and  , and
    • for every arrow  , if   then  , and if   then   .

Note that the existence statement for identities does not claim their uniqueness. However, we can actually prove that the identity arrow is unique to its respective object.

Arrows are often called morphisms. For a morphism  , we usually write   to simultaneously show its domain and codomain. The collection of all arrows from   to   is written, depending on choice, as   or  . If this collection is small enough to be a set, we call   locally small; we say   is large otherwise. We almost always deal with locally small categories.

Discussion

edit

These principles are just those of the `algebra of function composition' already introduced in the discussion of functions. So we're making a shift from thinking about functions in terms of what they do to the elements of sets, to thinking about (vaguely) function-like entities that are described in terms of their external behavior in terms of composition. But we see from the upcoming list of examples that arrows are only function-like in certain respects; they definitely do not have to actually be functions.

From the definition, some basic results follow (in the same way they do for monoids and groups).

  • a sequence of arrows   composes to the same thing no matter how it is parenthesized, as long as the order is kept. e.g.  , etc.
  • identities are unique. That is, if we have some   such that   for all   and   for all  , then  

The first of these is normally proved by induction in graduate level introductions to abstract algebra (such as Serge Lang's Algebra), but the proof is not very illuminating (at least to beginners). The proof of the second is however a mini-classic, which you would have already encountered if you've done any group theory:

 

It's the two-sidedness of the property characterizing the identity that makes this work.

Examples

edit

Sets

edit

  is a category whose objects are sets and whose arrows are functions.

There is however a technical point to manage. In the account of functions given earlier, a function is presented as a kind of relation between two sets, its domain, which it is `from', and its codomain, which it is `to'. This is what's needed for category theory, but in the most commonly encountered set-theoretical definition, a function is just a set of ordered pairs meeting the condition that nothing appears as first member of two different pairs (different pairs being those with either different first or second members, by the set-theoretical principle of extensionality). The set of second members is called the range, and a function is then `to' any set that contains the range as a subset. This would not work out for category theory, since we need each arrow to have only one domain and only one codomain.

So to make a set-theoretic function serve as a category arrow in  , we need to bundle it with with some superset of its range, which then constitutes is codomain, so it's an ordered pair <set-theoretic function, codomain>. But we don't have to add a domain, since, unlike the range, that's determined intrinsically by the set of ordered pairs.

So, having taken all that on board and proved to ourselves that   is a category, we get for free the results from the Discussion section above that identities are unique.

Monoids

edit

Every monoid is a category with only one object. Category is a generalization of monoid. The section on Free Categories just below expands on this point.

All Monoids

edit

The category of monoids   is a category, whose objects are monoids and whose arrows are monoid homomorphisms.

This represents a very large and important class of examples: for pretty much any of the kinds of algebraic systems you might study in an Abstract Algebra course, there will be a category with instances of the kind of system in question as objects, and homomorphisms (however defined for that particular kind of system) as arrows.

Posets

edit

A partially ordered set or a poset is a category, whose objects are elements of the poset and whose arrows are 'less than or equal' relations.

In greater detail, a preorder is a category in which there is at most one arrow from any object   to any object  . So the relation "there is an arrow from   to  " will satisfy the axioms of reflexivity and transitivity, but not necessarily either symmetry or antisymmetry. We can impose antisymmetry by requiring at most one arrow connecting   and  , regardless of direction. This example provides another instance where arrows aren't functions. The Hasse diagram of a poset is a directed graph whose corresponding free category is that set with its partial order.

All Posets

edit

The category of posets   is a category, whose objects are posets and whose arrows are order preserving functions. If A and B are posets, then function   is order preserving or monotone, if for every elements x and y in A  . This is another example where algebraic systems of some type are the objects, and their homomorphisms the arrows.

Free Categories

edit

Directed graphs

edit
 
A simple directed graph.

Here we have objects ( ) and arrows ( ), the basic furniture of a category, but no category because there are no rules. In particular, the only arrows present are the ones depicted.

A directed graph is a collection of objects and arrows without any rules of composition or identity arrows. We say that a graph is small, if the collections are sets. A small directed graph can be described as a set O of objects and a set A of arrows, and two functions   and   that associate domain and codomain to each arrow. Conversely, given any two disjoint sets A and O, and any two functions from A to O, we get a small directed graph.

Free category on a (directed) graph

edit

An obvious way to get a category out of a graph is to let category arrows be (finite) sequences of graph arrows, with the empty sequence   serving as the identity for each node, and composition of sequences defined in the `obvious' way.

Well that's the basic idea but there are a few annoying technicalities. First, and trivially, we have to decide whether to write our sequences in the order of traversal of a path (intuitively natural), or in the standard order of arrow (and function) composition (counter-intuitive but supported by tradition). We'll try to uphold rationality against tradition for a few minutes and write our paths in the order of traversal. So, technically an arrow f in a category freely generated by graph is a sequence   of arrows   in graph such that   for all indexes i. The word freely means that two sequences   and   represent the same arrow if and only if they are the same sequence, that is

  and  .

Composition of arrows is defined:

If  ,  , and cod  =dom  , then:
 

Ugh. Well, eventually stuff like this gets easier to write for yourself than to read. Note the confusing order switch between the structure of the composed sequence and the arrow-composition notation. Associativity of course follows from the associativity of composition of sequences.

The other technical point involves the identities and the requirements for something to be an arrow; can you figure out what it is and suggest a solution?

We say that a category is free, if it's freely generated by some directed graph.

Free categories are of considerable importance for applying category theory to logic (e.g. Lambek and Scott (1986) Introduction to Higher Order Categorical Logic). They also provide a fine illustration of why arrows don't have to be functions. And of the point above that a category is a generalization of a monoid, since the category arrows are like monoid elements that can't always be composed. Monoids in general have one feature that free categories can lack, in that different compositions of arrows can result in the same monoid element. This can happen with categories too, but not with free ones.

Foundational Issues

edit

There are some tricky foundational points that arise in the definition of category. The word 'collection' was used where one might have expected 'set', because in many important examples of categories, the collections of objects and arrows are 'too big' to be sets, but instead must be proper classes. The most obvious case is our first example, the category  , where Russell's Paradox tells us that there can't be any such thing as a set of all sets, so the collection of objects of   can't be a set.

If the collections of objects and arrows of a category are sets, it is called a small category, otherwise, a large category. So   is large, and any monoid is small. What about a poset, or  ? Most of the large categories that people are interested in, such as  , have the property that for any objects  ,   is a set. Such a category is called locally small.

Category theorists appear on the whole to not be very interested in fussing about foundations, so if you can remember what 'small', 'large', and 'locally small' mean, you almost certainly know enough.

'Spinoff' Categories

edit

All algebraic systems provide various further ones of the same kind; for groups, for example, we might have some interesting subgroups and quotient groups, and will always have lots of product groups. Categories seem to participate in the process with an unusual degree of exuberance. For each of the 'spinoff categories' below (not a standard term, but it seems quite appropriate to this author (AA)), it is a good basic exercise to prove that it really is a category. The proof is always a routine demonstration that:

  • the putative arrow-composition actually produces an arrow in the category
  • composition is associative
  • such that each object has an identity arrow

There are plenty more of these things than we illustrate here, but is it necessary to learn them all at once?

The Opposite Category

edit

For any category  , we also have the opposite category  , formed by retaining the objects of   without change, but swapping the domain and codomain of each arrow. Composition is defined by the equation  . Yet another way of making the point that arrows don't have to be functions. Here is an outline of the proof that   really is a category. This is also often called the dual category.

Pair Categories

edit

For any categories  ,  , we can form the pair category   whose objects are pairs   of objects from  ,  , respectively, and whose arrows are pairs   of arrows of  ,  , respectively, such that if  ,  , then

 

Composition is defined as:

 

This is basically a direct product construction, and generalizes straightforwardly to  -tuples.

Slice Categories

edit
 
Arrow (  in slice category

For any object   of a category  , the slice category of objects over  ,  , has as objects those arrows of   that have   as their codomain. The arrows are a bit harder to describe. Suppose that   and   are objects of  . Then   of   is also an arrow of  , from   to  , if  . This is illustrated in the commutative diagram to the right, which is a graph representing some objects and arrows in the category, and there is a convention that any two paths between the same node are the same arrow (typically derived by a different composition of other arrows). Commutative diagrams can be formalized as a way to represent facts about categories (e.g. Barr and Wells (1999:91-94), but we'll just take them as suggestive intuitive representations for equations, which will be the 'official' format for imposing identities on different compositions of arrows.

 
Composition of arrows in slice category

We now need to define composition for the arrows; the basic idea is that the composite of two slice-category arrows is the slice-category correspondent of the two original arrows. We need to do a bit of work to show that this works, as expressed in the diagram to the right. Here   is an arrow  , and   one  . For   to be an arrow from   to  , it must be the case that  , which you can verify as an exercise. Associativity and identities then follow immediately from these properties of the original arrows of  .

A (perhaps excessively) fine point is that, although people standardly speak of the arrows of   as being certain of the arrows of  , this can't technically be quite right, since arrows have unique domains and codomains, and these are different for the arrows of the two categories. What we really want is for each suitable arrow of   to induce a (different) corresponding arrow of  . A construction that would suffice would be to have the arrows of   be triples of the form (original arrow, new domain, new codomain).

Morphisms

edit

Monomorphism

edit

We've already discussed Injective, or one-to-one functions, and observed that the 'internal' property of one-to-oneness, for functions, is equivalent to the 'external' property of being cancellable on the left (  if and only if  ). Arrows that aren't functions of any kind can't be one-to-one, but they can have the cancellation property, giving us:

Monomorphism, a categorical analogy of injective function.

A monomorphism (also called a monic morphism or a mono) is a morphism   which is left-cancellative in the following sense

  implies   for all morphisms  .

The situation described by these equations is often depicted by this diagram:

 

Put another way, map   is monic if and only if the induced map   is injective for all  . Here   is function such that   for all   in  . If your mind bounces off this statement at first, it's definitely worth reflecting on until it really seems to make sense.

In the category   the monomorphisms are exactly the injective functions as we proved in the first lesson. Many familiar arrows, such as the homomorphisms of various kinds of algebraic systems, are functions with some additional restrictions placed on them (e.g. they must preserve some algebraic relationships). Such arrows are (almost?) always one-to-one/injective as functions if and only if they are monic as arrows. Eventually we'll be able to formulate a more precise and general version of this claim.

Two easy results about monomorphisms are:

  • If   and   are monomorphisms, then   is one too,
  • If   is a monomorphism, then   is one too.

Here are the proofs.

Epimorphism

edit

Likewise, there is an 'external' version of the 'internal' property of onto-ness:

Epimorphism is (almost) a categorical analog of surjective function.

An epimorphism (also called an epic morphism or an epi) is a morphism   which is right-cancellative in the following sense:

  implies   for all morphisms  .
 

Put another way, a map   is epic if and only if the induced map   is injective for all Z. Here   is a function such that   for all g in  .

In the category   the epimorphisms are exactly the surjective functions as we proved in the first lesson. There is also another way to define surjective, which is equivalent to epimorphism in many interesting categories, but certainly not in all categories.

From the discussion of Opposite categories, we can see that a monomorpism   is an epimorphism in   (or, if we want to be ultra-fussy, corresponds to one), and vice-versa. This gives us free proofs for two results about epimormorphisms corresponding to the ones about monomorphisms above. We also say that mono- and epi-morphisms are dual concepts.

Example: Non-surjective epimorphism

edit

Consider the monoid homomorphism f from the natural numbers to the integers that takes every number to itself, that is

 , where   for all integers n.

The morphism f is clearly not surjective as a function in the category of sets. We claim it's an epimorphism in the category of monoids.

Let M be any monoid and let   be any monoid homomorphisms  , such that  . This means that   and   agree on all non-negative numbers. We must show that they agree on negative numbers also. We do this by induction.

 
 
 
 
 
 
 
 

Now suppose we have proven  . We prove it for n+1 by

 

Isomorphism

edit

Isomorphism is a categorical analogy of bijection.

An isomorphism is a morphism   that has an inverse morphism   such that

  and  .

We say that objects X and Y are isomorphic, denoted  , if there exists an isomorphism between them.

Inverses are unique, that is if h, g are both inverses of f, then h = g. The easy proof is left to reader as an exercise. This fact lets us speak of the inverse of f, written  . Every isomorphism is monomorphism and epimorphism, but the converse is not true.

Example: morphisms in posets

edit

In a partially ordered set morphisms are 'less-than-or-equal' relations. For any two objects a, b in a poset, there's at most one morphism from a to b. It follows that every morphism is monic and epic. On the other hand only morphisms with inverses are identity morphisms (proof: anti-symmetry).

Exercise: Duals of isomorphisms

edit

Prove that if   is an isomorphism in  , then so is its correspondent (its dual) in  .

Initial and terminal objects

edit

In the next lesson we'll be looking at concepts defined by universal properties, which characterize things up to isomorphism, that is, any two things that have the property are isomorphic. In Category Theory, it is relatively unusual to be interested in actual identity: identity up to isomorphism is most often all that is of interest, in accord with the general focus on external behavior rather than internal construction. The simplest universal properties are those being initial and final objects:

An object A in a category   is an initial object, if for every object C in  , there is exactly one arrow from A to C. Similarly an object A in a category   is a terminal object, if for every object C in  , there is exactly one arrow from C to A. Some basic facts about these are:

  • A initial object of   is a terminal object of  , and vice-versa
  • Initial and terminal objects are unique up to a unique isomorphism. That is if A and B are both initial objects, then there is a unique isomorphism from A to B.

Proof: exercises

Examples

edit
  • In the category of sets (  ) the empty set is an initial object. For any set X there is only one function from the empty set to set X, the empty function. Any set with only one element, a singleton set, is a terminal object. In  , there is in fact only one initial object, due to the axiom of extensionality. And, for any set X there is only one function from X to a singleton set, a constant function that has the same value on every element of X. There are many different singleton sets, but they are all isomorphic. These examples provide a further illustration of how 'internal' properties can be replaced by 'external' ones, since the notions of having zero elements or one can be described (for sets) in terms of the arrows from or to the set. Of course one has to do quite a bit of further development in order to describe all of the properties of sets 'externally'.
  • The monoid with only one element, the identity element, is both initial and terminal object in the category of monoids. An object that is both initial and terminal is called a zero object. The zero object is only unique up to isomorphism.
  • In a poset, the least element, if there is one, is an initial object, and the greatest element, if there is one, is a terminal object. Here the initial and terminal objects are fully unique.

Discussion

edit

A few further points:

  • An initial object in   is terminal in   (proof: trivial).
  • Any arrow  , where   is a terminal object, is monic (proof: exercise)
  • An arrow   is often called an 'element' of  . Can you identity the property of   that motivates this terminological usage? (hint)

Hints and Details

edit

Identities for Free Categories

edit

The problem is that arrows are supposed to have unique domains and codomains, so the empty sequence technically can't serve as the identity arrow for every node in the graph (= object in the free category). A reasonable solution is to use the nodes themselves as their own identity arrows, and engineer this by brute force into the definition of composition.

Opposite Categories

edit

Outline of proof that   is a category:

  • the result of composition belongs to the opposite category by definition.
  • composition is associative via a chain of identities involving the definition of opposite-composition and the associativity of the original category.
  • the identities of the original category serve as identities for the opposite category.

Monomorphisms

edit
  • Suppose   are monomorphisms, and  . Then   (why?) and so   (why), so   is a monomorphism. QED
  • Suppose   is a monomorphism, and  . Then  , so  . Therefore,   is a monomorphism. QED.

If you're new to algebraic proofs, make sure you understand the implicit role of associativity in these arguments

Other surjections

edit

w:Epimorphism#Related concepts

  • Split epimorphism: every generalized element in codomain is an image of generalized element in domain. This is equivalent to condition that morphism has right-inverse.
    This condition is too strong for many algebraic categories. For example monoid homomorphism from   to cyclic monoid   is not split epi.
  • S-surjective: every   is an image of  . If S is a separator, every   is monic and category has subobject classifier this is equivalent to epimorphism. (Lawvere&Rosebrugh P4.10)
    Monoid homomorphism   is not  -surjective, since   is not in the image.

Arrows as Elements

edit

If   is a terminal object of  , and   is an object of  , then there is a one-to-one correspondence between the conventional set-theoretic members of   and the arrows from   to  .

Exercises

edit
  1. We say that an arrow   has a left inverse if there is an arrow   so that  . Suppose that   has a left inverse and show that   is a monomorphism.
  2. Show that an epimorphism with a left inverse is an isomorphism.
  3. Give an example of a category and an arrow in that category that is not an isomorphism but is both a monomorphism and epimorphism.
edit