Multiplicative graph

Short description: Type of partial category

For comparison, this diagram shows a typical arrow composition in an ordinary category. (Without arrow composition, it is simply a directed graph.) The arrows $f$ and $g$ in the diagram are consecutive; they connect in $B=\text{cod}(f)=\text{dom}(g).$ In an ordinary category, the composition of any pair of consecutive arrows exists, whereas in a multiplicative graph, a pair of consecutive arrows is not necessarily composable.

In mathematics, a multiplicative graph (in French: graphe multiplicatif or neocategory in some English-language papers) is an algebraic structure in category theory. It is a generalization of an ordinary category in the sense that neither the associativity of arrow composition nor the composibility of a pair of connected arrows are assumed. While an ordinary category is a notion combining a directed graph and a monoidal structure, a multiplicative graph is a partial magma-like structure. Namely, it is a structure in one‑to‑one correspondence with the vertices of a directed graph, and each object has left and right identity morphisms, but composability is partial, and, moreover, associativity is not required.

Arrow composition in an ordinary category satisfies the following property: if arrows $f$ and $g$ connect in the sense that $\text{dom}(g)=\text{cod}(f),$ their composition $g\circ f$ is defined, and, moreover, $\text{dom}(g\circ f)=\text{dom}(f)$ and $\text{cod}(g\circ f)=\text{cod}(g).$ In a multiplicative graph, however, condition $\text{dom}(g)=\text{cod}(f)$ does not guarantee the existence of $g\circ f$ within that structure without further assumptions – but if this composition exists, it also satisfies $\text{dom}(g\circ f)=\text{dom}(f)$ and $\text{cod}(g\circ f)=\text{cod}(g).$ When drawing a diagram for a multiplicative graph, it is almost always necessary to explicitly draw all existing arrows that play a role in the argument. For example, as shown in Coppey (1980), square diagrams in a multiplicative graph can take one of five types depending on which potential compositions in the diagram are actually defined.

This notion first appears in Ehresmann's book Catégories et structures. The French school bases its definition of sketch on the notion of a multiplicative graph, because this definition required a category-like structure that avoided redundant axioms as much as possible. This structure is the multiplicative graph, and this is a type of relaxed notion of category, such as a semicategory.

Cury studied enriched multiplicative graph. As a more general notion, there is the compositional graph, and multiplicative graphs can be seen as strongly identitive compositional graphs.

Definition

Group-like structures
	Totality	Associativity	Identity	Invertibility	Commutativity
Semigroupoid	Unneeded	Required	Unneeded	Unneeded	Unneeded
Small Category	Unneeded	Required	Required	Unneeded	Unneeded
Groupoid	Unneeded	Required	Required	Required	Unneeded
Magma	Required	Unneeded	Unneeded	Unneeded	Unneeded
Quasigroup	Required	Unneeded	Unneeded	Required	Unneeded
Loop	Required	Unneeded	Required	Required	Unneeded
Semigroup	Required	Required	Unneeded	Unneeded	Unneeded
Inverse Semigroup	Required	Required	Unneeded	Required	Unneeded
Monoid	Required	Required	Required	Unneeded	Unneeded
Group	Required	Required	Required	Required	Unneeded
Abelian group	Required	Required	Required	Required	Required
^α Closure, which is used in many sources, is an equivalent axiom to totality, though defined differently.

A multiplicative graph $\mathrm{\Sigma }$ is couple formed by a set denoted by $\underset{\_}{\mathrm{\Sigma }}$, and a partial law of composition $\kappa$ on $\underset{\_}{\mathrm{\Sigma }}$ satisfying the following axioms:

1. $\kappa$ is a mapping from a subset of $\underset{\_}{\mathrm{\Sigma }}\times \underset{\_}{\mathrm{\Sigma }}$ (denoted by $\mathrm{\Sigma }*\mathrm{\Sigma }$ and called the set of composable couples) into $\underset{\_}{\mathrm{\Sigma }}$; instead of $\kappa (y,x)$, we write $y\circ x$ and we call $y\circ x$ the composite of $(y,x)$.
2. There exists a reflexive graph $(\underset{\_}{\mathrm{\Sigma }},\beta ,\alpha )$ (i.e. $\alpha$ and $\beta$ are retractions from $\underset{\_}{\mathrm{\Sigma }}$ onto a subset of $\underset{\_}{\mathrm{\Sigma }}$, denoted by ${\mathrm{\Sigma }}_0$), such that:

(existence of units [existence of composition for loops]): For each element $x$ of $\underset{\_}{\mathrm{\Sigma }}$, the composites $x\circ \alpha (x)$ and $\beta (x)\circ x$ are defined, and we have

$x\circ \alpha (x)=x=\beta (x)\circ x.$

Here, $\alpha (x)$ is the right identity of $x$ and is called the source of $x$, while $\beta (x)$ is the left identity of $x$ and is called the target of $x$;

(coherence of dom/cod): If the composite $y\circ x$ is defined, then:

$\alpha (y\circ x)=\alpha (x),\beta (y\circ x)=\beta (y),\text{and}\alpha (y)=\beta (x).$

From the condition 2, the reflexive graph $(\mathrm{\Sigma },\beta ,\alpha )$ is uniquely defined.

Inverse morphisms are not unique

Let $C^{*}$ be a multiplicative graph, if one has a $(f,f^{\prime })\in C^{*}*C^{*}$ and $f\circ f^{\prime }=\beta (f)$ (resp. $(f^{\prime },f)\in C^{*}*C^{*}$ and $f^{\prime }\circ f=\alpha (f)$), then we say that $f\in C$ admit a right (resp. left) inverse of a morphism $f^{\prime }$ in $C^{*}$. If there exists an $f^{\prime }\in C$, we say that $f$ in $C^{*}$ is invertible such that $f^{\prime }$ is the right and left inverse of $f$ in $C^{*}$, then we called $f^{\prime }$ an inverse of $f$ in $C^{*}$. If $C^{*}$ is a multiplicative graph and if $f\in C$ admit f' for right (resp. left) inverse in $C^{*}$, one has:

$\alpha (f^{\prime })=\beta (f)$ and $\beta (f^{\prime })=\alpha (f)$

While inverse morphisms in a ordinary category are unique, a morphisme of multiplicative graph $C^{*}$ can have several inverse morphisms. The law of composition are shown in the table below:

File:Inverse morphisms in a multiplicative graph.svg

Note:this is not a diagram.

	f	f'	f''	e	e'
f		e'	e'	f
f'	e				f'
f''	e				f''
e		f'	f''	e
e'	f				e'

A functor between multiplicative graphs

Let $\mathrm{\Sigma }$ and ${\mathrm{\Sigma }}^{\prime }$ be two multiplicative graph. A functor (Ehresmann called this a neofunctor. Since the functors between categories are ordinary functors, in this article, the functor between multiplicative graphs, we just write it as "functor" in italics.) $\varphi$ from $\mathrm{\Sigma }$ toward ${\mathrm{\Sigma }}^{\prime }$ is a triple $({\mathrm{\Sigma }}^{\prime },\underset{\_}{\varphi },\mathrm{\Sigma })$, where $(\underset{\_}{\varphi }$ is a mapping from $\underset{\_}{\mathrm{\Sigma }}$ into ${\underset{\_}{\mathrm{\Sigma }}}^{\prime }$ such that $\varphi (e)\in {\mathrm{\Sigma }}_o^{\prime }$ for each $e\in {\mathrm{\Sigma }}_o$ and that:

If $y\circ x$ is defined in $\mathrm{\Sigma }$, then $\underset{\_}{\varphi }(y)\circ \underset{\_}{\varphi }(x)$ is defined in ${\mathrm{\Sigma }}^{\prime }$, and

$\underset{\_}{\varphi }(y)\circ \underset{\_}{\varphi }(x)=\underset{\_}{\varphi }(y\circ x)$

We say also that $\varphi :\mathrm{\Sigma }\to {\mathrm{\Sigma }}^{\prime }$ is a functor; we write $\varphi (x)$ instead of $\underset{\_}{\varphi }(x)$ and ${\varphi }_o$ denotes the restriction $\varphi :{\mathrm{\Sigma }}_o\to {\mathrm{\Sigma }}_o^{\prime }$ of $\varphi$.

If $\varphi :\mathrm{\Sigma }\to {\mathrm{\Sigma }}^{\prime }$ and ${\varphi }^{\prime }:{\mathrm{\Sigma }}^{\prime }\to {\mathrm{\Sigma }}^{\prime \prime }$ are two functors, we denote by ${\varphi }^{\prime }\circ \varphi$, the functor from $\mathrm{\Sigma }$ to ${\mathrm{\Sigma }}^{\prime \prime }$ assigning

${\varphi }^{\prime }(\varphi (x))$ to $x$ in $\mathrm{\Sigma }$.

An ordinary functor must preserve identity morphisms and composition of morphisms, but in a multiplicative graph, the composibility of a pair of connected morphisms is not assumed.

Example

• An ordinary category is a multiplicative graph if it satisfies the following two axioms:

(composibility):all the couples $(y,x)$ where $\alpha (y)=\beta (x)$ are composable (so that $\mathrm{\Sigma }*\mathrm{\Sigma }$ is the pullback of $(\alpha ,\beta )$);

(strong associativity):the law of composition being furthermore associative.

• For the two axioms above, a notion got by adding only the associativity axiom (that is, associativity is not strong) to a multiplicative graph, that is, a notion that an ordinary category without the composibility axiom, this is called a precategory. But, this is not standard terminology, a precategory is usually synonymous with a semigroupoid and does not require each object to have an identity morphism.

See also

• Partial groupoid
• Non-associative algebra

References

• Bastiani, Andrée; Ehresmann, Charles (1972). "Categories of sketched structures" (in en). Cahiers de Topologie et Géométrie Différentielle Catégoriques 13 (2). ISSN 1245-530X. https://www.numdam.org/item/CTGDC_1972__13_2_104_0.pdf. 
• Coppey, L. (1980). "Quelques problèmes typiques concernant les graphes multiplicatifs". Diagrammes 3 (2). ISSN 0224-3911. https://www.numdam.org/item/DIA_1980__3__A2_0.pdf. 
• Coppey, L. (1990). "Actes des journées E.L.I.T. (Univ. Paris 7. 27 juin-2 juillet 1988)". Diagrammes 24: 33–76. https://www.numdam.org/item/DIA_1990__24__33_0.pdf. 
• Coppey, Laurent (2012). "Décompositions multiplicatives directes des entiers". Diagrammes 67-68: 53-100. https://www.numdam.org/item/DIA_2012__S67-68__53_0.pdf. 
• Coppey, L.; Lair, C. (1984). "Leçons de théorie des esquisses". Diagrammes 12 (4). ISSN 0224-3911. https://www.numdam.org/article/DIA_1984__12__A4_0.pdf. 
• Cury, F. (1978). Graphes multiplicatifs enrichis (Thesis) (in français).
  • Cury, Florence (2004). "Graphes multiplicatis enrichis. Partie I". Diagrammes 51: 1–46. https://www.numdam.org/item/DIA_2004__51-52__A1_0.pdf. 
  • Cury, Florence (2005). "Graphes multiplicatis enrichis. Partie II". Diagrammes 53: 47–95. https://www.numdam.org/item/DIA_2005__53-54__A1_0.pdf. 
  • Cury, Florence (2006). "Graphes multiplicatis enrichis. Partie III". Diagrammes 55: 96–120. https://www.numdam.org/item/DIA_2006__55-56__A1_0.pdf. 
  • Cury, Florence (2007). "Graphes multiplicatis enrichis. Partie IV". Diagrammes 57: 121–183. https://www.numdam.org/item/DIA_2007__57-58__A1_0.pdf. 
• Cury, F. (1979). "Systèmes de générateurs et relations pour les catégories enrichies". Diagrammes 1. https://www.numdam.org/item/DIA_1979__1__A1_0.pdf. 
• Ehresmann, Charles (1965). Catégories et structures. https://books.google.com/books?id=Q2WnAAAAIAAJ&q=%22graphe-multiplicatif%22. 
• Ehresmann, Charles (1969). "Construction de structures libres". Category Theory, Homology Theory and their Applications II. Lecture Notes in Mathematics. 92. pp. 74–104. doi:10.1007/BFb0080766. ISBN 978-3-540-04611-0. 
• Mateus, Paulo; Sernadas, Amílcar; Sernadas, Cristina (1999). "Precategories for Combining Probabilistic Automata". Electronic Notes in Theoretical Computer Science 29: 169–186. doi:10.1016/S1571-0661(05)80315-9. 

External link

• Tringali, Salvatore (2013). "Plots and Their Applications - Part I: Foundations". arXiv:1311.3524v1 [math.CT].
• Wells, Charles (2009). "Sketches: Outline with References". https://ncatlab.org/nlab/files/Wells_Sketches.pdf.