# Objects are finite sets, arrows are matrices. How is this a category?

I just started to read this book on category theory.

How is this example below a category?

I have difficulty imagining what this construct really is.

Could someone please illuminate me ?

I have a physics background, I am not a mathematician.

Perhaps with some very simple example or analogy that is understandable for a physicist's mind.

EDIT:

Does this example make sense at all ?

EDIT 2:

What confuses me is that for a given object $A$, $i=|A|$ is fixed, so is $j=|B|$, so the location of a natural number in the matrix $F$ is determined by the size of $A$ and $B$. So the arrow from $A$ to $B$ is a number in a matrix and not the matrix itself !

EDIT 3: Many thanks for the answers ! I think I get it now.

Example:

As a reminder a category is defined as:

EDIT 4:

I just bought the latest eBook version where this mistake has been corrected:

-

## migrated from mathoverflow.netMar 26 '14 at 11:29

This question came from our site for professional mathematicians.

The definition is complete. Have you tried verifying the axioms? – Zhen Lin Mar 26 '14 at 11:06
Not the place to ask, please use MSE. – abx Mar 26 '14 at 11:08
The definition of the example makes no sense to me as it is written. Perhaps the author meant that $f$ is an arrow from $A$ to $B$ iff it is a matrix with $|A|$ rows and $|B|$ columns (and with entries in $\mathbb{N}$). – Ramiro de la Vega Mar 26 '14 at 11:17
Yes, it makes no sense to me either. – jhegedus Mar 26 '14 at 11:22
Thanks for correcting me. – jhegedus Mar 26 '14 at 17:08

I think that this is what is going on:

The objects are finite sets.

For the morphisms: given two sets $A$ and $B$ you want a set $Mor(A,B)$ of elements/arrows $f: A \to B$. So here $A$ is the domain and $B$ is the codomain of $f$. This needs to satisfy the composition law.

Here you have for two finite sets $A$ and $B$ this set of morphisms consists of all $\lvert A \rvert\times\lvert B\rvert$ matrices (with entries in $\mathbb{N}$). That is, a morphism/arrow is exactly a matrix. You compose two morphisms/arrows by multiplying the matrices. So The composition of morphisms/arrows is given by matrix multiplication so that if $f \in Mor (A,B)$ and $g\in Mor(B,C)$, then $g\circ f\in Mor(A, C)$. Is this well defined? Yes, because $Mor(A,C)$ consists exactly of $\lvert A \rvert\times\lvert C\rvert$ matrices and you get that from multiplying $\lvert A \rvert\times\lvert B\rvert$ matrices with $\lvert B \rvert\times\lvert C\rvert$ matrices.

-
According to the author’s definition of a category, given a arrow $f$, there must be an object $dom(f)$. Given a $m\times n$ matrix $f$, what is $dom(f)$? If there’s more than one object $A$ with $|A|=m$, $dom(f)$ isn’t well defined. Or else the arrows have to be more than just matrices, so they carry information about which specific sets are their $dom$ and $cod$. Or the author’s definition of category is wrong. – Steve Kass Mar 26 '14 at 12:30
@SteveKass: Given $f\in Mor(A,B)$ the domain is $A$ and the codomain is $B$. We write $f \to B$. So indeed there is just one object for the domain and one for codomain. – Thomas Mar 26 '14 at 13:02
I am going by Definition 1.1 in the extract of this question. It says nothing about the set $Mor(a,b)$, but I'm realizing that this is crucial to the definition. How would anyone read Definition 1.1 and not be confused? Definition 1.1 fails to mention that arrows in different morphism sets aren't the same. It's like defining numbers and then telling someone they should have realized "the integer 7" and "the real number 7" are not the same. I can imagine a world where they aren't, but Definition 1.1 doesn't give a clue. – Steve Kass Mar 26 '14 at 16:49
Also, since "It does not make sense to talk about an $f$ without an $A$ or $B$," would you agree that it also makes no sense to say that $f$ is a matrix? You can't give a mathematician a matrix and expect her to know what $A$ and $B$ you're talking about. (You've been helpful and careful here, but some commenters seem to insist that the arrows in this category simply are matrices. That seems problematic, because they have to be "matrices with context.") – Steve Kass Mar 26 '14 at 16:53
@SteveKass: I agree! The definition that way it is written isn't great. A key point about category theory is to be precise and this definition isn't very precise. – Thomas Mar 26 '14 at 16:54

I think that this is indeed worded incorrectly. I assume the author really wanted to write $F=(n_{i\,j})_{1\le i\le\lvert A\rvert,1\le j\le\lvert B\rvert}$.

-
Yes, that would make more sense then. I am always very confused when learning new mathematics and then find something I don't understand. Then I am not sure if it was the author's mistake or mine. Usually it's me who does not understand the new material and that is why I was asking it here if it is me who is not understanding what this really is. Or is this just a typo that is driving me crazy ? – jhegedus Mar 26 '14 at 12:23
I agree that this is confusing if you do not already know where the author is headed. I on the other hand to to reread the paragraph to see the problem, because I was already focussed on the next step. Your explanation headed by EDIT 2 was helpful. – Carsten S Mar 26 '14 at 12:27
Oh, and I had not seen that the answer had already been given as a comment... – Carsten S Mar 26 '14 at 12:28
It was good to get a confirmation, thanks! – jhegedus Mar 26 '14 at 12:30

I think the intended example is this:

The objects are finite sets and given two objects $A$ and $B$, $hom(A,B)$ is the set of all $|A| \times |B|$ matrices with entries in $\mathbb{N}$ (you could replace $\mathbb{N}$ here by $\mathbb{Z}$, $\mathbb{R}$ or anything for which matrix multiplication is well defined and associative). Then it is straightforward to check the axioms.

-
I'm still confused. Suppose $A=\{1\}$ and $B=\{2\}$ are two of the objects. Then let $f$ be the $1\times1$ matrix $(1)$. The definition says that for $f$, there are objects $dom(f)$ and $cod(f)$. What are they? And the definition says that there are identity arrows on both $A$ and $B$. If the arrows are matrices, $1_A$ and $1_B$ are the same matrix, $f$. But $A=dom(1_A)\ne dom(1_B)=B$, yet if we replace both $1_A$ and $1_B$ by $f$, how can $dom(f)\ne dom(f)$? – Steve Kass Mar 26 '14 at 16:44
@Steve Kass There are infinite arrows between A and B, perhaps this might resolve the contradiction you depicted. – jhegedus Mar 26 '14 at 17:22
@SteveKass: I guess you are right and technically one should "label" the arrows in $hom(A,B)$ so that (for instance) they really are triples $(A,B,F)$ where $F$ is a matrix and the composition is $(A,B,F)\circ(B,C,G)=(A,C,FG)$. Still, this is an essentially different category than the one described in user18921´s answer, and I think it is closer to the intended category in the OP´s example. – Ramiro de la Vega Mar 26 '14 at 18:23
@jhegedus the problem is not that there are multiple arrows between A and B, the problem is that it is not possible to retrieve A and B uniquely from the arrow. The interpretation mentioned by Ramiro is one way to solve it, the one by Henning in another comment a different one. – Paŭlo Ebermann Mar 26 '14 at 19:53

The category the author was intending to define is as follows.

1. Objects. Finite sets

2. Arrows. An arrow $f : A \rightarrow B$ is just a function $f : A \times B \rightarrow \mathbb{N}$.

3. Composition. The composition of arrows $f : A \rightarrow B$ and $g : B \rightarrow C$ is the unique function $h : A \times C \rightarrow \mathbb{N}$ given as follows. $$h(a,c) = \sum_{b \in B}f(a,b)g(b,c)$$

4. Identities. If $A$ is an object, then $\mathrm{id}_A$ is the unique function $A \times A \rightarrow \mathbb{N}$ given as follows.

\begin{align} a=a' & \;\rightarrow\; \mathrm{id}_A(a,a')=1 \\ a\neq a' & \;\rightarrow\; \mathrm{id}_A(a,a')=0 \end{align}

To see what this has to do with matrices, just imagine that every object of this category is not a set, but rather a totally ordered set. Then an arrow $f : A \rightarrow B$ in this category, which as you'll recall is just a function $f : A \times B \rightarrow \mathbb{N},$ can be visualized as an $|A| \times |B|$ array of natural numbers.

-
The objects can be represented as matrices, but that representation isn’t faithful if there are distinct objects of the same cardinality. It seems wrong to say that the arrows are matrices, because you can’t take one of these arrows $f$, say of dimensions $m\times n$, and tell me what $dom(f)$ is, unless there is only one object with cardinality $m$. (Similarly in regular algebra, if we have sets and functions between them, you can’t tell me what the domain of $f(x)=x^2$ is without knowing anything else.) – Steve Kass Mar 26 '14 at 12:35
@SteveKass: The objects are not matrices. The objects are finite sets. – Thomas Mar 26 '14 at 13:05
@Thomas: Thanks. I presumed, wrongly it seems, that the requirement that for each arrow there are given objects $dom(f)$ and $cod(f)$ meant that those objects were well-defined from $f$. But this is still very confusing to me. Is the collection of arrows a set? If it is, and it's a set of matrices, then the $1\times1$ identity matrix appears only once. Suppose both $\{1\}$ and $\{2\}$ are objects, and consider the arrow $(1)$ ($1\times1$ matrix). What are $dom((1))$ and $cod((1))$? – Steve Kass Mar 26 '14 at 16:36
@Thomas It is perfectly reasonable to identify an $n$ by $m$ matrix of natural numbers with a function from $n \times m$ to $\mathbb{N}$. Indeed, this is the most straightforward definition of a matrix that comes to mind. – Kundor Mar 26 '14 at 17:00
@Thomas: The problem with saying that it's "just" matrices is that doing so requires the objects to be not just finite sets, but finite sets with a distinguished enumeration of their elements that specifies which rows/columns of the matrix correspond to which elements of the set. Then the whole thing collapses into the category of dimensions (as objects) and matrices (as morphisms) with some of the objects uselessly duplicated. It's more faithful to the original idea to keep the ordering of each finite set abstract, which is what the $\mathbb N^{A\times B}$ construction achieves. – Henning Makholm Mar 26 '14 at 19:40