Fix a (finite) set $A$. Say you are given a Cayley (multiplication) table for $A$: an $|A| \times |A|$ matrix, where each row and column corresponds to exactly one element of $A$, and the entries of the matrix are elements of $A \cup \{ - \}$. For example, if $A = \{ a, b, c, d \}$:
$\begin{array}{c|cccc} \circ & a & b & c & d \\ \hline a & - & b & - & c \\ b & d & b & - & a \\ c & - & - & a & b \\ d & d & - & a & - \\ \end{array}$
Intuitively, we interpret the above table as follows. The entry in row $x$, column $y$ gives us the product $x \circ y$: either this is another element $a \in A$, in which case we say $x \circ y = a$, or it is "$-$", in which case we say $x \circ y$ is undefined. So, any such table defines a partial magma on $A$.
Now, interpret the elements of $A$ as morphisms, with composition defined as above. Is there an algorithm to determine whether this set of morphisms forms a category? That is, if we let $\operatorname{Hom}(\mathbf{C}) = A$, is there a set of objects $\operatorname{Ob}(\mathbf{C})$, and functions $\operatorname{source}, \operatorname{target}: \operatorname{Hom}(\mathbf{C}) \to \operatorname{Ob}(\mathbf{C})$ such that these obey the axioms of a category?
Some ideas:
- There must be at least one object. If any product is undefined, there must be at least two objects. [A product $x \circ y$ is undefined iff $\operatorname{source}(x) \neq \operatorname{target}(y)$ - this could help].
- We need to assign source and target objects to each morphism, then check this assignment is consistent with the rules of a category.
- Identity would be easily checked for each object: associativity is a bit harder, but surely this has been done for a (partial) semigroup before?
Bonus question: how could this be done for other, single-operation algebraic structures? What about for multiple operations (rings, fields, vector spaces etc.) and providing multiple tables?