Seven Sketches in Compositionality - Exercise 2.61


Give a possible intuitive interpretation of an NMY-category.


Consider a directed graph. Suppose we are a traveler that has to move in this graph and that only has partial knowledge about the graph itself. We ask ourselves which nodes can be reached from our starting point, given our knowledge of the graph. In some cases the answer will be "Yes! I can go from $x$ to $y$." (cmp. $\mathtt{yes}$); in other cases, the answer will be "No! I can’t go from $x$ to $y$." (cmp. $\mathtt{no}$); but, more commonly, the answer will just be "I don’t know know if I can go from $x$ to $y$." (cmp. $\mathtt{maybe}$).

Logically, if we know that there exist a $x \to y$ path and a $y \to z$ path, there must exist a $x \to z$ path. Suppose we know there exists a $x \to y$ path and suppose we don’t know whether there is a path $y \to z$. Then, we can only conclude that there might be a $x \to z$ path, but we are not sure. The answer to the question "Is there a $x \to z$ path?" is "I don’t know." even if we know that no $x \to y$ path exists and that there is no $y \to z$ path either, as there might be a path that does not involve $y$. I’ll leave it to the reader to speculate about the other possibilities.

The presence of such uncertainty can be rigorously modeled using a NMY-category $\mathcal{X}$: the objects of $\mathcal{X}$ will be the nodes of the graph and $\mathcal{X}(x,y)$ will be the answer to the question "Is the a path that links $x$ to $y$?". The two axioms of NMY-categories will have the following meaning:

  • $\mathtt{yes} \leq \mathcal{X}(x,x), \, \forall x$ implies that every node is connected to itself;

  • $min(\mathcal{X}(x,y),\mathcal{X}(y,z) ) \leq \mathcal{X}(x,z), \, \forall x,y,z$ implies the logical deductions stated above (and the unstated ones, obviously).

The asymmetry of $\leq$ is very interesting and is absolutely necessary to model uncertainty. Knowing the relation between $x$ and $y$, and between $y$ and $z$ can only give us positive information about the relation between $x$ and $z$, but it cannot be used to show that $x$ and $z$ are not connected. In other words, absence of evidence is not evidence of absence.

No comment found.

Add a comment

You must login to add a comment.

Site Maintenance

Our platform is currently undergoing maintenance. We apologize for any inconvenience. Please check back later.