Roads, routes and stay-put arrows
Tonight's idea
Draw towns as dots and one-way roads as arrows. A route is a list of roads, each starting where the one before ended. If one route ends where another starts, you can join them: drive the first, then the second. Staying where you are counts as a route too, with no roads in it. Call it the stay-put arrow of that town.
Join three routes and you get the same list of roads whichever join you do first. Join a stay-put arrow onto a route and nothing changes.
A category has objects and arrows between them. Arrows that meet end to start can be joined, \((f \text{ then } g) \text{ then } h = f \text{ then } (g \text{ then } h)\), and every object has its own stay-put arrow, which changes nothing when joined on.
Towns and routes form a category. Category theory, begun by Samuel Eilenberg and Saunders Mac Lane in the 1940s, studies math(s) through how things connect, not what they are made of. It calls a stay-put arrow an identity.
Watch one: four towns
The objects are the towns. The arrows are the routes, not just the roads. Write a route as its list of roads in driving order.
Routes from A to D. From A you leave by \(p\) or \(s\). After \(p\) you are at B, and can finish with \(t\), or with \(q\) and then \(r\). After \(s\) you are at C and must take \(r\). So there are exactly three: \(pt\), \(pqr\) and \(sr\).
Order of joining. Join \(p\), \(q\), \(r\) in two ways. First \(p\) then \(q\) is the route \(pq\), and \(pq\) then \(r\) is \(pqr\). Or first \(q\) then \(r\) is \(qr\), and \(p\) then \(qr\) is \(pqr\). The same list of roads both times.
When joining fails. "\(s\) then \(t\)" means nothing: \(s\) ends at C, but \(t\) starts at B.
Your turn
- Use the map above. (a) How many routes have 0 roads? 1 road? 2 roads? 3 roads? How many arrows does this category have in all? (b) A new road \(u\) is built from D to A. Explain why there are now infinitely many routes from A to A.
- Still on the map, without \(u\). Write \(1_B\) for the stay-put arrow of B. (a) What is \(p\) then \(1_B\)? What is \(1_A\) then \(p\)? Explain using lists of roads. (b) Which of these joins make sense: \(p\) then \(t\); \(t\) then \(p\); \(q\) then \(q\); \(1_C\) then \(r\); \(p\) then \(1_A\)?
- A category with no roads. The objects are the numbers 1 to 12. There is one arrow from \(a\) to \(b\) exactly when \(a\) divides \(b\) (so \(3 \to 12\), but no arrow \(12 \to 3\)). (a) Which number's stay-put arrow comes from "5 divides 5"? Why does every number have one? (b) If there are arrows \(a \to b\) and \(b \to c\), why is there an arrow \(a \to c\) to be their join? (c) How many arrows arrive at 12? How many arrows are there in all?
- Some people stand in a room. Draw an arrow from \(x\) to \(y\) when \(x\) is taller than \(y\). (a) Arrows \(x \to y\) and \(y \to z\) can be joined. Why? (b) This is still not a category. Which rule fails? (c) Change the rule to "\(x\) is at least as tall as \(y\)". Is it a category now?
Stretch: roads back
An arrow \(f\) from X to Y can be undone if some arrow \(g\) from Y to X makes \(f\) then \(g\) the stay-put arrow of X, and \(g\) then \(f\) the stay-put arrow of Y. A category in which every arrow can be undone is called a groupoid. (a) Give every road on the map a return road, so \(p\) gets \(p'\) from B to A. In the category of routes, is \(p\) then \(p'\) the stay-put arrow of A? Which routes can be undone? (b) Now keep a shorter record: a trip is only (start, end), and (X, Y) then (Y, Z) is (X, Z). With return roads you can get from any town to any town. How many trips are there, and why is this a groupoid?
Answers
- (a) 0 roads: 4, the stay-put arrows. 1 road: 5. 2 roads: 4, namely \(pq\), \(pt\), \(qr\), \(sr\). 3 roads: 1, namely \(pqr\). Every road leads to a town later in the alphabet, so no route visits a town twice and none has 4 roads. In all \(4 + 5 + 4 + 1 = 14\) arrows. (b) Now \(ptu\) is a route from A back to A. Drive it once, twice, three times and so on: each is a different list of roads, so the routes never run out.
- (a) Both are \(p\). The stay-put arrow has no roads, so joining it to either end of the list "\(p\)" adds nothing. (b) \(p\) then \(t\): yes, the route \(pt\) from A to D. \(t\) then \(p\): no, \(t\) ends at D and \(p\) starts at A. \(q\) then \(q\): no, \(q\) ends at C but starts at B. \(1_C\) then \(r\): yes, it is \(r\). \(p\) then \(1_A\): no, \(p\) ends at B and \(1_A\) starts at A (you would need \(1_B\)).
- (a) The stay-put arrow of 5. Every number divides itself, since \(a = a \times 1\). (b) If \(b = a \times k\) and \(c = b \times m\) for whole numbers \(k, m\), then \(c = a \times (k \times m)\), so \(a\) divides \(c\). The order of joining cannot matter here, because there is never more than one arrow from one number to another. So this is a category. (c) Six arrive at 12, from 1, 2, 3, 4, 6 and 12 itself. Counting arrivals at each of 1 to 12 gives \(1 + 2 + 2 + 3 + 2 + 4 + 2 + 4 + 3 + 4 + 2 + 6 = 35\) arrows, of which 12 are stay-put arrows.
- (a) If \(x\) is taller than \(y\) and \(y\) is taller than \(z\), then \(x\) is taller than \(z\), so the arrow \(x \to z\) is there to be the join. (b) Nobody is taller than themselves, so no one has a stay-put arrow. A category needs one at every object. (c) Yes. Everyone is at least as tall as themselves, joins work as in (a), and there is at most one arrow from one person to another, so the order of joining cannot matter. Two people of equal height get an arrow each way, which is allowed.
Stretch. (a) No. \(p\) then \(p'\) is the route \(pp'\) with two roads, and the stay-put arrow has none. Joining adds the numbers of roads, so a join has no roads only when both parts have none. Only the stay-put arrows can be undone, so routes do not form a groupoid, even with return roads. An extra rule is needed: out and back counts as staying put. (b) \(4 \times 4 = 16\) trips. The stay-put arrow of X is (X, X), and joins depend only on the first start and the last end, so the order of joining does not matter. Each trip (X, Y) is undone by (Y, X): one way round gives (X, X), the other (Y, Y).