Why aren't morphisms defined as a set of relations?

Question

I've been studying category theory and on the books, it's never too clear what a morphism really is. Some say that a morphism could be a function, but there are examples of morphisms which are not functions, for example: Morphisms in the category of relations. My guess is that they are property-preserving relations. From Simmons': Introduction to Category Theory, there's a small list of things that are categories:

And from the few ones I know, one could represent morphisms as property-preserving relations. That is, each object in each of the categories can be a set and by taking an appropriate relation, we could define a morphism as being this relation(?). So what is happening?

• I'm wrong and seeing morphisms as set of relations would have some kind of problem? (Why?)

• They expect us to notice that they are really set of relations?

Another wild guess is that it seems that a category is a concept logically pre-set theory. That is, a category is a concept that can be made without mentioning sets? This seems a little odd because each of the concepts in the list seems to need set theory. I guess the only one we don't need it are categories of categories?

Answer 1

A category consists of:

• a set called $O$;
• for every two elements $A, B \in O$, a set called $\operatorname{Hom}(A, B)$;
• for every three objects $A, B, C$, a function $\circ_{ABC} : \operatorname{Hom}(B, C) \times \operatorname{Hom}(A, B) \to \operatorname{Hom}(A, C)$, usually just denoted $\circ$ since there can be no confusion,

such that the functions $\circ$ are associative where defined.

In particular, a category is in some sense a generalization of the notion of a group where two elements (i.e., morphisms) may or may not have a product, and an element may or may not have an inverse.

Just like you can have abstract groups whose elements aren't given by, say, permutations or matrices†, you can have abstract categories whose objects aren't given by sets and whose morphisms aren't given by functions between those sets. And these are just as useful in category theory as abstract groups are in group theory. For instance, you can encode the notion of a commuting square of morphisms in some category $\mathsf{C}$ as a functor

$$F : \mathsf{J} \to \mathsf{C},$$

where $J$ is a special category consisting of four objects and four morphisms forming a commuting square. (See Diagram on Wikipedia for more.)

---

† Of course there's Cayley's theorem, but do you really want to embed, say, $GL_3(\mathbb{C})$ as a subgroup of the permutations of an uncountably infinite set? It can be done but it's not helpful.

Answer 2

Your list of examples is just really misleading, though these are the examples that are most easy to understand: categories where the objects are sets with structure. This need not be the case though.

Some examples for other kinds of categories $\mathcal{A}$:

• let $P$ a (pre-) ordered set. Let the objects of $\mathcal{A}$ be elements of $P$ and a morphism $x\to y$ to be the tuple $(x,y)$ which exists if and only if $x\leq y$ (this is indeed a category! Why?)
• let $M$ be a monoid. Let $*$ be the only object of $\mathcal{A}$ and morphisms $*\to*$ be all the elements of $M$. Composition is given by the monoid operation $\cdot$.
• let $G$ be a quiver (directed graph possibly with loops and multiple edges between nodes). Form the free category $\mathcal A$ on $G$ by taking the nodes as objects. A morphism $A\to B$ is a path from $A$ to $B$. Composition is done by sticking paths together. (Empty paths give you identities)
• let $\mathcal{A}'$ be a category. Now let objects of $\mathcal{A}$ be pairs of sequences $((A_i)_{i\in \mathbb N}, (\delta_i : A_{i} \to A_{i+1})_{i\in \mathbb{N}})$ of objects and morphisms in $\mathcal{A}'$. A morphism: $$((A_i)_{i\in \mathbb N}, (\delta_i : A_{i} \to A_{i+1})_{i\in \mathbb{N}}) \to ((B_i)_{i\in \mathbb N}, (\eta_i : A_{i} \to A_{i+1})_{i\in \mathbb{N}})$$ is a sequence of morphisms $(f_i : A_i \to B_i)_{i\in \mathbb N}$ such that the obvious squares of morphisms commute (which ones?)

It would probably be a good idea to just verify that all of the above are categories. Then you should be fairly comfortable with morphisms not being relations.

Here is a more "obscure" example:

• take propositions (of some logic) as objects of $\mathcal{A}$ and a morphism $A\to B$ is a proof of $B$ given $A$; composition is simply done by sticking proofs $A\to B$ and $B\to C$ together to a proof $A\to C$

Answer 3

Here is one of my favorite categories:

• The objects are natural numbers
• $\hom(m, n)$ is the collection of all $n \times m$ matrices
• Composition is matrix multiplication

I like this example, because:

• You are already very familiar with this category
• It is very clearly an algebraic structure
• Categories are clearly the right kind of structure to describe it (e.g. "monoid" only works for square matrices). Also, see "abelian category" to cover addition too.
• It violates a lot of preconceptions one might have about categories