# What is the difference between Categories and Relations?

For a common basis, I'll state basic definitions of a category and the relation type I'm thinking of. They're here for quick clarity, not precision, so feel free to revise for an answer.

Category:
A collection of objects, a collection of arrows each with a source and target among said objects, identity arrows, and a composition operator satisfying an associative law over arrows.

Reflexive relation on AxA:
A collection of objects, a labelled multi-set of pairs of said objects satisfying the reflexive law, and the standard relation combinator operation (which satisfies the associative law).
Note that labelled multi-set relations are commonly expressed and utilized in discrete math as multi-graphs. I collapse graphs and relations here for unified axiomatic treatment. This is not to treat, e.g., paths over graphs as different from relation composition.

What, exactly, separates these two? They appear essentially identical in definition and meaning to me. Relations immediately appear more general, given that categories only analogize to a certain restricted class of relations.
I note some notational difference, such as how categories name each arrow; I don't see how that would change mathematical power. Similarly with the explicit treatment of composition. While such contrivances can come in handy for certain proofs or explorations, I don't see how it justifies treating the two as separate branches rather than syntactic shims on identical concepts.

[EDITS: fixed associativity statement, extended relations to multi-set representation with graph analogy]

-
What is an associative relation, as opposed to an associative function on ordered pairs? Do you mean, perhaps, a transitive relation? – Niel de Beaudrap Nov 25 '10 at 11:39
Categories are much, much more general. Have you actually read anything about category theory? – Qiaochu Yuan Nov 25 '10 at 12:07
@Qiaochu: My knowledge of the area has no impact on the question. Suffice it to say that the impetus for my post is not ignorance. – Chad Wellington Nov 28 '10 at 6:59
In any case, one obvious difference between categories and relations is that in a relation, for any two objects $a$ and $b$, either $(a,b)$ is in the relation or it is not; while in a category, there may be many distinct arrows between the two objects $a$ and $b$. For example, the category of finite sets with total functions as arrows would make a very boring relation, with $aRb$ for all sets $a$ and $b$ except when $a \neq b = \varnothing$. – Rahul Nov 28 '10 at 8:22
I'm not so sure I understand the point of your question. The same structures appear in different branches of mathematics with different name all the time. Category theory is much more about a perspective / notational choice than a desire for "mathematical power". There are many structures that subsume categories, multi-graphs, and many other subjects. It doesn't mean one should use those frameworks. – Ryan Budney Nov 29 '10 at 6:31

A directed multigraph can be thought of as a one-dimensional simplicial complex: the vertices are points, and the edges are 1-simplices.

Given a category, we can form its nerve, and the 1-skeleton will essentially be a multi-graph.

The observation of the OP is that these two constructions are roughly inverse to each other.

The relationship between simplicial sets and categories is an important one, and is at the basis of the theory of higher categories and its relationship to homotopy theory. Thus the OP's observation and question shouldn't be dismissed.

On the other hand, I'm not sure that I agree with the sentiment of the OP's final non-parenthetical sentence: "I don't see how it justifies treating the two as separate branches rather than syntactic shims on identical concepts." Certainly (multi-)graph theorists and (higher-)category/homotopy theorists both make itensive studies of 1-dimensional simplicial sets, but the questions they ask and the constructions they are concerned with are typically extremely different. If they do find common ground, that's great, but they needn't be obliged to seek it.

Most working mathematicians using categories are, furthermore, not thinking in a homotopical/simplicial way at all about the structures involved, but are just taking advantage of the very useful language and range of concepts that category theory provides. These are concepts that (as far as I know) are not used at all by those studying multi-graphs and related structures, and so I don't see any reason that people should be obliged or even encouraged to translate (what to them are) familiar category-theoretic notions into a different terminological framework of relations/multi-graphs.

[Added: Ryan Budney's comment above makes essentially the same point in a pithier fashion.]

-
"Mathematics is a collection of trivialities". I advance no great purpose in my question. Category Theory does develop its own proof and description techniques, with which I have no issue (modulo syntactic shed-painting). I saw a tight analogy in the definition of categories matching relations (or graphs), but I never saw mention of this in any writeup-- from the original paper to modern treatments. I just wanted my suspicions about this (IMO) conspicuous absence rigorously confirmed or denied, even if somewhat pointless. Thanks! – Chad Wellington Nov 29 '10 at 10:42

Qiaochu is right: categories are much more general. Let me provide a concrete example which, while in a sense trivial, may illustrate just how much more you could get from a category than you can from a reflexive and transitive relation.

Consider the positive integers $\mathbb P$. The usual total order $\leqslant$ is a perfectly good reflexive, transitive relation on this set. We can think of this as a category which consists of the identity map $\mathrm{id}_n$ on each integer n ∈ $\mathbb P$, and the composition of the successor maps $\sigma_n: n \to n+1$. The result is essentially an almost acyclic directed graph (all circuits are stationary walks on a single vertex).

Now let me describe to you a different category on the positive integers: the category of injective linear maps on finite-dimensional real vector spaces — which is to say, the category whose objects are the positive integers, and whose arrows are m × n matrices over $\mathbb R$, with rank n, for m ≥ n.

An aside. "What!?" you may exclaim; "How can you talk about matrices having domains and codomains consisting of positive integers?" Well, the shape of each matrix defines what sorts of other matrices it can be composed with, and any action of a matrix M on a vector v ∈ $\mathbb R^n$ could be viewed as composing the m × n matrix M with the n × 1 matrix v to obtain an m × 1 matrix Mv. The integers stand in for the dimension of the vector space $\mathbb R^n$ or $\mathbb R^m$ which are the "real" domain and codomain of the matrix; and because we can substitute the linear action of operators on $\mathbb R^n$ with the effect of composing two linear operators (one of which happens to have a domain of $\mathbb R^1$), we may ignore the structure inside of the vector spaces and refer to them just by their dimensions.

As with the directed graph generated by the total order ≤, there exist arrows m → n for any m ≥ n (by definition). All of the maps from n to m for m > n+1 can be obtained by composing maps n → n+1 and n+1 → m; and furthermore, all maps n → n+1 can be obtained by composing any single designated map $\sigma_n: n \to n+1$ with a suitable map $\tau: n \to n$. So this category has a number of things in common with the one defined by the total order ≤. But there are important differences, owing in part to the fact that there are infinitely maps n → n for each n. Because of this, this second category has much more structure than a binary relation.

For instance, it becomes meaningful and interesting to talk about coproducts.

Definition. Let A,B be two objects. A coproduct of A and B is an object (A $\amalg$ B), together with two maps iA : A → (A $\amalg$ B) and iB : B → (A $\amalg$ B) such that, for any other object X and maps f : A → X and g : B → X, there exists a unique map (f | g) : (A $\amalg$ B) → X such that f = (f | g) $\circ$ iA and g = (f | g) $\circ$ iB . That is, in the following diagram, any two directed walks between a common pair of points represent the same map:

$\begin{matrix} \qquad\! A \!\!&\!\! \xrightarrow{\textstyle \;i_A\;} \!\!&\!\! (A \amalg B) \!\!&\!\! \xleftarrow{\textstyle \;i_B\;} \!\!&\!\! B \!\qquad \\ \mathrm{id_A}\Bigg\updownarrow & & \Bigg\downarrow(f|g)\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!& &\Bigg\updownarrow\mathrm{id_B} \\ \qquad\! A \!\!&\!\! \xrightarrow[\textstyle \quad f \quad] \!\!\!\!\!\!\!\!\!\!&\!\! X \!\!&\!\!\!\!\!\!\!\!\!\! \xleftarrow[\textstyle \quad g \quad] \!\!&\!\! B\!\qquad \end{matrix}$

1. In the case of the partial order ≤, the coproduct of A and B is just  max { A, B } , which you should verify for yourself.
2. In the category of matrices we described above, the coproduct of A and B is not the maximum of A and B, but is instead the integer A+B, corresponding to splitting a vector of dimension A+B into a block of size A and a block of size B.

• The "inclusion" map $i_A$ would correspond to mapping a vector in v ∈ $\mathbb R^A$ into the first A coefficients of a vector in $\mathbb R^{A+B}$, with the others set to zero;
• The "inclusion" map $i_B$ would be similar, mapping vectors in $\mathbb R^B$ into the final B coefficients.
• For functions fA → A+B and gB → A+B, the map (f | g) corresponds to performing the map f to the first block and g to the second block of the vector.

Of course, there's more than one way to decompose $\mathbb R^{A+B}$ into blocks; we could have chosen a different definition for the maps iA and iB, by having iB map vectors in $\mathbb R^B$ into the first B coefficients, and iA map vectors into the final A coefficients. This way of embedding $\mathbb R^A$ and $\mathbb R^B$ into the same space at the same time is equivalent to the one we describe above; in fact we can show that there is a unique isomorphism between these two ways of constructing (A $\amalg$ B). So, the coproduct (A $\amalg$ B) is dependent on the choice of maps iA and iB — but not in any way which is really important.

Even though the first category generated by ≤ is what you get when you forget the matrix structure of the second category — by replacing each infinite collection of arrows in each case with a single arrow between the same points — that second category of injective linear operators is substantially different from the simple one described by ≤.

This is just scratching the surface of one fingernail of category theory; but hopefully it convinces you that categories and reflexive, transitive binary relations are not trivially equivalent.

-
I see the direct address of my question directly in one place: "Because of this, this second category has much more structure than a binary relation." You refer back to this when you mention that the second category collapses to the first upon collapsing the self-arcs corresponding to the matrix structure. I do not see where this exceeds the expressivity of binary relations. The second category can be stated in a relation using a labelled multigraph for connectivity and a predicate or other class descriptor to encompass the enumeration of matrix-transform edges. Have I missed something? – Chad Wellington Nov 28 '10 at 9:07
@Chad: just what is it that you mean by "the expressivity of binary relations", which you feel is not different in the two categories above? What is is that you mean for a binary relation to 'express'? If all you are interested in is the question "does there exist an arrow between A and B", then as I noted before, there is no difference. But connectivity is only one concept which you can obtain in category theory; it also distinguishes between different paths between two points as having possibly different properties. – Niel de Beaudrap Nov 28 '10 at 11:48
@Chad: from your comments further above, it seems to me that you probably need to do a little bit of reading about category theory if you're really interested in this question. For instance, as noted by Rahul, categories always contain all possible compositions of arrows (i.e. where the domain of one agrees with the codomain of the other); this is explicitly included in every definition I have seen, but you seem to have missed it. Ultimately, however, category theory is meant to consider much more than just connectivity; so if connectivity is all you care for, don't worry about categories. – Niel de Beaudrap Nov 28 '10 at 11:54
I've cleaned up my post per your and Rahul's comments; thanks, I think I have a much clearer presentation of what I'm trying to find out. I also understand that CT makes a clearer axiomatic statement of composition, whereas relations often leave this implicit. However, the path concept is seen quite frequently in relations-cum-graphs, so that does not provide CT more power. Here I could turn the tables and imply your need to read up on discrete math, but I don't see how that's helpful. Let's keep the discourse contained to the question. – Chad Wellington Nov 29 '10 at 0:23
@Chad: Category theory is not 'about' composition, any more than number theory is 'about' the Peano successor function. Composition is just one of the building blocks of category theory, which (if you will forgive me) you made conspicuous by having missed it. --- I suggest that you ask yourself the following: is everything you can say about the subject of "injective linear transformations on spaces $\mathbb R^n$" captured by the total ordering $\leqslant$ on the natural numbers? If not, what more is there to the subject of the linear transformations, which is not captured by the ordering? – Niel de Beaudrap Nov 29 '10 at 7:59

This is an example of that the axioms of a theory doesn't say much of the intentions with the theory. The purpose of relation has never been to study universal properties, for example.

-