A free category on the graph of flights. What idea is captured?

Question

I disagree with an exercise in my cat theory book.

In exercise 5.1.2.35 it asks me what idea is captured by the free category on $G$, where $G$ is the graph whose vertices are all the European cities and whose arrows are airplane flights connecting the cities.

The solution argues that this captures the idea of flight itineraries. However to me it just captures rubbish. You would have morphisms of the like

Amsterdam → Moscow → Amsterdam → Genova → Amsterdam → Paris → Amsterdam → Rome → Amsterdam

And now, this is not a composition on many morphism, this is a possible path on the underlying graph which was stuffed inside $\operatorname{Hom}_{\mathcal{G}}(\mathtt{Amsterdam}, \mathtt{Amsterdam})$.

Answer 1

In this interpretation of the category, the intention is that you should read $\hom(A, B)$ as being the answer to the question "Which itineraries start in city $A$ and end in city $B$?"

Ideas like whether or not an itinerary passes through another city is expressed in different terms. For example, given an itinerary $f$ from Amsterdam to London, the assertion:

• $f$ goes from Amsterdam to London by way of Moscow

expressed in category language would be the issertion

• $f$ factors into a product $g \cdot h$, where $h$ is an itinerary starting in Amsterdam and ending in Moscow, and $g$ is an itinerary starting in Moscow and ending in London

Answer 2

From what I read in the comments, I think you misunderstand something about the free category generated by a graph $G$.

---

Because graph can have very different meaning depending on who you are talking about, let us agree that it means a directed non involutive multigraph, that is two sets $G_0,G_1$ and two functions $s,t:G_1\rightrightarrows G_0$. In the book's example, $G_0$ is the set of european cities, $G_1$ the sets of flights between these, $s$ selects the start of the flight and $t$ selects the destination of the flight.

From what I read in your post, I guess you understand that objects of the free category $F(G)$ are the elements of $G_0$ (the cities), and that the morphisms $x\to y$ in $F(G)$ are the finite path from $x$ to $y$ in $G$, meaning the finite sequences $(e_1,\dots,e_n)$ with $$s(e_1)=x,s(e_2)=t(e_1),\dots,s(e_n)=t(e_{n-1}),t(e_n)=y$$ I guess you also understand that identity morphisms are given by the empty sequences.

From what I read in the comments, I'm not sure you understand composition: this is given by concatenation. So that composing $(e_1,\dots,e_n) : x \to y$ with $(f_1,\dots,f_m): y \to z$ gives $(e_1,\dots,e_n,f_1,\dots,f_m): x \to z$. In particular, it means that $$ (e_1,\dots,e_n) = (e_n)\circ \dots \circ (e_1) $$ where $(e_i): s(e_i) \to t(e_i)$ is the sequence of length $1$ defined by the edge $e_i$.

Coming back to the book's example, given a flight $\mathbf{AF110}: \mathrm{Paris} \to \mathrm{Oslo}$ and a flight $\mathbf{SK042} : \mathrm{Oslo} \to \mathrm{Tromsö}$, the morphism $(\mathbf{AF110},\mathbf{SK042})$ in the free category is not just a meaningless name given to some morphism $\mathrm{Paris}\to\mathrm{Tromsö}$, it is indeed the itinerary $$ (\mathbf{AF110},\mathbf{SK042}) = (\mathbf{SK042}) \circ (\mathbf{AF110}) $$ starting from Paris, landing in Oslo, then taking off from Oslo and finally landing in Tromsö. To go back to your example, there is indeed some itineraries from Amsterdam to Amsterdam, going all over Europe before coming back (although very few people would book that kind of itinerary I guess...)

---

(If I completely misunderstood your question, then sorry for the unecessary answer and I would have to agree with other people in that it is probably a matter of vocabulary and not about mathematics per se.)