2
$\begingroup$

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:

enter image description here

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?

$\endgroup$
  • 1
    $\begingroup$ In a sense, the Yoneda lemma makes this observation precise $\endgroup$ – Omnomnomnom Aug 28 '16 at 5:15
  • 1
    $\begingroup$ Because, in general, morphisms are not relations. $\endgroup$ – Pedro Tamaroff Aug 28 '16 at 6:00
  • $\begingroup$ @PedroTamaroff What morphism wouldn't be a relation? $\endgroup$ – Billy Rubina Aug 28 '16 at 6:01
  • $\begingroup$ It's worth noting that any category yields a type theory, by taking its objects as types, and the objects of type $X$ are the morphisms with codomain $X$. $\endgroup$ – Hurkyl Aug 31 '16 at 18:38
6
$\begingroup$

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$
$\endgroup$
  • $\begingroup$ But my point is: I didn't said that they all are relations (perhaps I wrote it poorly? If yes, sorry.) I said that it seems that they all can be represented as relations, and I believe that this representation could add more concreteness to understanding morphisms. At least for your examples, I guess I can put them into a relational representation. $\endgroup$ – Billy Rubina Aug 28 '16 at 9:52
  • $\begingroup$ How? And even if many of them are relations (possibly of infinite arity) if you tweak them long enough the composition will usually not be relational composition. So there is no real point to that. - I didn't even mention models of theories internal to some category, where the morphisms can be veeeery far from your run-of-the-mill relation (e.g. categories internal to the category of small categories) $\endgroup$ – Stefan Perko Aug 28 '16 at 9:58
  • 1
    $\begingroup$ The words "object" and "morphism" that occur in the definition of category are only required to obey the axioms for a category. Draw two dots on a piece of paper, draw three arrows, one going from one dot to the other, and the other two arrows looping from each dot to itself. There is only one way to define composition, so this is a category. It is illustrated in the Wikibooks category theory book at en.wikibooks.org/wiki/Category_Theory/Categories Those arrows are marks on paper. They are not functions or relations. $\endgroup$ – SixWingedSeraph Aug 28 '16 at 19:10
  • $\begingroup$ @StefanPerko You take - for example - two pre-ordered sets. Now you take all the relations that are monotonic functions. Does this work? $\endgroup$ – Billy Rubina Aug 31 '16 at 0:30
  • $\begingroup$ @StefanPerko I guess I expressed it wrong. A morphism is a structure-preserving set of relations, that's what I meant originally. $\endgroup$ – Billy Rubina Aug 31 '16 at 1:13
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, I've seen this definition in which $Hom(A,B)$ is the set of all functions (And at some places, it's the set of all morphisms.) When it's a function, it's ok, understandable. But when it's all morphisms, I guess there is a problem (which I mentioned at my question). Unless the set of all morphisms $=$ the set of all functions. Is it? $\endgroup$ – Billy Rubina Aug 28 '16 at 5:58
  • 2
    $\begingroup$ No, $Hom(A, B)$ is just a set. It's part of the data of the category. Since $A$ and $B$ need not be sets, they elements of $Hom(A, B)$ can't be functions in general. For instance, consider the category where $O = \{1, 2\}$, $Hom(1, 1) = \{i\}$, $Hom(1, 2) = \{f\}$, $Hom(2, 2) = \{j\}$, $i \circ i = i$, $j \circ j = j$, and $f \circ i = j \circ f = f$. $\endgroup$ – Daniel McLaury Aug 28 '16 at 6:03
  • 1
    $\begingroup$ A "morphism," by definition, is just an element of one of the sets $Hom(A, B)$, which can be literally any set whatsoever. $\endgroup$ – Daniel McLaury Aug 28 '16 at 6:06
  • 1
    $\begingroup$ A set of anything. For instance, in the category I described in my previous comment, one of the morphisms was simply the letter "j." $\endgroup$ – Daniel McLaury Aug 28 '16 at 7:16
  • 1
    $\begingroup$ It's probably worth emphasizing that a group, as suggested above, is literally an example of a category. Insofar as an element of a group is not generally a relation, e same must be said for morphisms in a category. $\endgroup$ – Kevin Carlson Aug 28 '16 at 8:31
2
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.