1
$\begingroup$

Suppose you are given the "action" of a morphism, some specification of what it does to elements; in $\textbf{Set}$ or related categories it would be the graph of a function. Is it possible to determine, in theory or practice, (whether there exists) a set of arrows whose composition matches the given action? If there are many such sets, is it possible to determine the one(s) requiring minimal compositions?

My intuition, stemming from the digraph axiomatization of a category, suggests that this is a simple example of pathfinding. However, most categories not only have infinite or large object sets, but infinite or large hom-sets. It's not clear how the standard algorithms would work on an infinite graph, let alone a graph with infinitely many edges between each vertex. I couldn't find any information on generalizations of pathfinding to such cases. However, it seems like this would be a common enough question in the subject to have been asked before. Is there something I'm missing?

$\endgroup$
6
  • 2
    $\begingroup$ What do you mean by "a set of arrows whose composition matches the given action"? Can you give an example? Arrows where? $\endgroup$
    – Qiaochu Yuan
    Jan 18, 2021 at 9:47
  • $\begingroup$ Example: in $\textbf{3}$, suppose I have a have an external (i.e. non-categorical) set of criteria ("action," as I called it) that both $g\circ f$ and $h$ satisfy, where of course $g,f$ are the non-identity composable arrows and $h$ is the other non-identity arrow. $\{g,f\}$ and $\{h\}$ would be "sets of arrows whose composition matches the given action," and the smallest one is sought. Ordering isn't strictly necessary, as one could discern that from domain and codomain data associated with the arrows. $\endgroup$
    – Duncan W
    Jan 18, 2021 at 12:34
  • $\begingroup$ The reason for the convoluted phrasing is that I have a function in a set-theoretical sense that may not be representable by a single arrow in a category. I want to find the most efficient way to represent a function by possibly very many arrows. $\endgroup$
    – Duncan W
    Jan 18, 2021 at 12:39
  • 4
    $\begingroup$ In a category, the composite of two morphisms always exists, so pathfinding isn't interesting: either there is a path, or there isn't. If a path exists, there will always be a path of length 1. $\endgroup$
    – varkor
    Jan 18, 2021 at 12:41
  • $\begingroup$ @Duncan: I still do not understand your question. What is $\textbf{3}$? What is this "external set of criteria"? The smallest what? Sets of arrows where? What do you mean by "a function in a set-theoretical sense that may not be representable by a single arrow in a category"? What does "represent" mean here? $\endgroup$
    – Qiaochu Yuan
    Jan 19, 2021 at 5:03

1 Answer 1

Reset to default
-1
$\begingroup$

There isn't a universal answer to this. Many problems (NP problems) could be easily written in such a formulation. For example : Hamiltonian cycle.

Your category is the set of nodes you've visited + the node you're actually in. Your action is to move to a neighboring vertex and mark it as visited. You have an Hamiltonian cycle iff the shortest path from $\emptyset \times {x}$ to $V \times {x}$ is of length exactly $|V|$)

So each answer will have to be designed specifically to the problem at hand, with the help of the geometry of the problem.

But this isn't a lost cause ! The edit distances (Levenshtein distance, tree edit distance, time-warp edit distance, etc) are generally defined as pathfinding distances on huge sets, but computed with dynamic algorithm that run in polynomial time of the input size.

If you can't find an "analytic" solution, maybe a pathfinding algorithm like A* can help you find a solution faster. The idea is to have a lower-bound heuristic ("the path from X to Y is at least n"), and use this kind of bound to orient your search. This could help you explore the neighbors in an interesting order and not explore a huge part of the category.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .