2 added 143 characters in body

Introduction. Allow me to use the NBG axiomatic system as a foundation (*). Charles Ehresmann is acknowledged as the first one to have introduced the idea of multiplicative graphs as a further level of abstraction in the study of categories. Unfortunately, I don't have a copy of his Categories et structures on my shelves, thus I'm writing to ask for experts' advice on the subject.

I learnt from uncle Google that Lutz Schröder, in his 1999 PhD thesis (in German), has slightly further abstracted Ehresmann's original ideas by extending multiplicative graphs to composition graphs. But Schröder's thesis is not apparently available for free consultation through the web and, in addition, I cannot read German. Now, the point is that I would like to see a completely formal definition of Schröder's composition graphs, for the sake of comparison with something on which I'm currently working. So, this post is definitely another question about terminology and references.

Definitions. As far as I can understand, a graph (in the sense of Ehresmann) is a 5-tuple $\mathbf C = (\mathcal C_{\rm o}, \mathcal C_{\rm h}, s, t, i)$, consisting of two classes $\mathcal C_{\rm o}$ and $\mathcal C_{\rm h}$ (of objects and arrows, respectively), and functions $s,t: \mathcal C_{\rm h} \to \mathcal C_{\rm o}$ and $i: \mathcal C_{\rm o} \to \mathcal C_{\rm h}$ such that $s(i(A)) = t(i(A)) = A$ for all $A \in \mathcal C_{\rm o}$. Thus, if I'm not missing anything, Ehresmann's graphs have identities. The same should be true with a composition graph (in the sense of Schröder), which seems to be a pair $(\mathbf C, c)$, where $\mathbf C = (\mathcal C_{\rm o}, \mathcal C_{\rm h}, s, t, i)$ is a graph (in the sense of Ehresmann) and $c$ is a partial function from $\mathcal C_{h} \times \mathcal C_{h}$ to $\mathcal C_{\rm h}$ such that $(f,g) \in {\rm dom}(c)$ only if $t(f) = s(g)$. This should be indeed called

1. a multiplicative graph (in the sense of Ehresmann) if the 'if' in the latter statement is replaced with an 'if and only if';
2. an identitive composition graph if for $f \in \mathcal C_{\rm h}$ one has $c(f,i(t(f))) = f$ whenever $(f,i(t(f))) \in {\rm dom}(c)$ and $c(i(s(f)),f) = f$ whenever $(i(s(f)),f) \in {\rm dom}(c)$;
3. a strongly identitive composition graph if it is identitive and $(f,i(t(f))), (i(s(f)),f) \in {\rm dom}(c)$ for all $f$;
4. a semicategory if it is an associative composition graph, viz $c(c(f,g),h),c(f,c(g,h)) \in {\rm dom}(c)$ and $c(c(f,g),h) = c(f,c(g,h))$ whenever $(f,h),(g,h) \in {\rm dom}(c)$ (which is slightly more general than the homonymous notion of a semicategory given by nLab).

Questions. (1) Do these definitions reflect the actual ones of graphs, composition graphs (by Schröder) and multiplicative graphs (by Ehresmann)? (2) Do you know of any significant development of these topics, especially in relation to categorical logic?

See here something related and motivations.

(*) Yeah, I know. Some of you feel disgusted by the NBG stuff, for diverse and diverse reasons. But, please, refrain yourselves from annoying comments on this hand, since the personal taste of Mr Banana is not really the point, here. Thank you so much.

1

# Graphs, multiplicative graphs and composition graphs (à la Ehresmann)

Introduction. Allow me to use the NBG axiomatic system as a foundation (*). Charles Ehresmann is acknowledged as the first one to have introduced the idea of multiplicative graphs as a further level of abstraction in the study of categories. Unfortunately, I don't have a copy of his Categories et structures on my shelves, thus I'm writing to ask for experts' advice on the subject.

I learnt from uncle Google that Lutz Schröder, in his 1999 PhD thesis (in German), has slightly further abstracted Ehresmann's original ideas by extending multiplicative graphs to composition graphs. But Schröder's thesis is not apparently available for free consultation through the web and, in addition, I cannot read German. Now, the point is that I would like to see a completely formal definition of Schröder's composition graphs, for the sake of comparison with something on which I'm currently working. So, this post is definitely another question about terminology.

Definitions. As far as I can understand, a graph (in the sense of Ehresmann) is a 5-tuple $\mathbf C = (\mathcal C_{\rm o}, \mathcal C_{\rm h}, s, t, i)$, consisting of two classes $\mathcal C_{\rm o}$ and $\mathcal C_{\rm h}$ (of objects and arrows, respectively), and functions $s,t: \mathcal C_{\rm h} \to \mathcal C_{\rm o}$ and $i: \mathcal C_{\rm o} \to \mathcal C_{\rm h}$ such that $s(i(A)) = t(i(A)) = A$ for all $A \in \mathcal C_{\rm o}$. Thus, if I'm not missing anything, Ehresmann's graphs have identities. The same should be true with a composition graph (in the sense of Schröder), which seems to be a pair $(\mathbf C, c)$, where $\mathbf C = (\mathcal C_{\rm o}, \mathcal C_{\rm h}, s, t, i)$ is a graph (in the sense of Ehresmann) and $c$ is a partial function from $\mathcal C_{h} \times \mathcal C_{h}$ to $\mathcal C_{\rm h}$ such that $(f,g) \in {\rm dom}(c)$ only if $t(f) = s(g)$. This should be indeed called

1. a multiplicative graph (in the sense of Ehresmann) if the 'if' in the latter statement is replaced with an 'if and only if';
2. an identitive composition graph if for $f \in \mathcal C_{\rm h}$ one has $c(f,i(t(f))) = f$ whenever $(f,i(t(f))) \in {\rm dom}(c)$ and $c(i(s(f)),f) = f$ whenever $(i(s(f)),f) \in {\rm dom}(c)$;
3. a strongly identitive composition graph if it is identitive and $(f,i(t(f))), (i(s(f)),f) \in {\rm dom}(c)$ for all $f$;
4. a semicategory if it is an associative composition graph, viz $c(c(f,g),h),c(f,c(g,h)) \in {\rm dom}(c)$ and $c(c(f,g),h) = c(f,c(g,h))$ whenever $(f,h),(g,h) \in {\rm dom}(c)$ (which is slightly more general than the homonymous notion of a semicategory given by nLab).

Questions. (1) Do these definitions reflect the actual ones of graphs, composition graphs (by Schröder) and multiplicative graphs (by Ehresmann)? (2) Do you know of any significant development of these topics, especially in relation to categorical logic?

(*) Yeah, I know. Some of you feel disgusted by the NBG stuff, for diverse and diverse reasons. But, please, refrain yourselves from annoying comments on this hand, since the personal taste of Mr Banana is not really the point, here. Thank you so much.