Is the world-wide web a category? Question posed in “Category Theory for Programmers” by Bartosz Milewski.

category-theorygraph theoryprogramming

Challenge 1.4.4 of Bartosz Milewski's "Category Theory for Programmers" poses the following question:

Is the world-wide web a category in any sense? Are the links morphisms?

I believe it is a category, where the objects are pages and the morphisms are links between pages (specifically URIs of pages, since the content itself might change upon page refresh). To prove this then it must be established that 1) there is an identity morphism for every object (page URIs), and 2) morphims (links between those pages/URIs) compose.

  1. The identity morphism is page refresh, or even more simply, doing nothing at all. My preference would be page refresh, since the pages identity is its current content if that differs from the current page load.

  2. Links compose because page A links to B and B to C, then one can navigate from A to C by first following the link from A to B and then immediately following the link from B to C. However, another way of looking at it is that for links to compose, then anytime page A links to B and B to C, then A must have a link directly to page C. That stronger condition generally isn't true. My inclination is to say that the awkward composition of navigating through intermediate pages should count as a composition function in its own right, but taken to an extreme in which two pages require thousands (or millions, etc) of intervening redundant link navigation, perhaps it shouldn't qualify. This raises another question, though it's off topic: what is the expected number of links required for that awkward protocol on average, and in the worst case? If it isn't too awful, then perhaps it would be worth tolerating. In any case, just wondering what others think about this interesting question.

Best Answer

You got it right in your question. It's a category if you define the morphisms as reachability through 0 or more links (or reachability through 1 or more links OR the refresh button). As Qiaochu Yuan mentioned any graph has a corresponding category where A -> B is a morphism iff B is reachable from A in 0 or more steps.

Alternatively if you were to say A -> B is a morphism iff A links to B, the internet would not be a category, since the identity morphism won't exist for all objects (a page may not link to itself), and morphisms don't compose (A may link to B and B to C but A does not necessarily link to C).

Related Question