The composition of morphism systems in a category is simply the set of all compositions of morphisms in each set, whenever they exist. If there are no compatible morphisms then the empty set is returned. Aside from the empty compositions, the quantale of morphism systems is similar to the quantales of sets of other algebraic structures.
Semiring of morphism systems:
Let $C$ be a category and $F,G$ families of morphisms in $C$. Then $F \circ G$ is the composition of all morphisms in $F$ and $G$ whenever they exist. This can be expressed in symbols as: \[ \bigcup_{m \in F, n \in G} \left\{ \begin{array}{ll} \emptyset & \text{Input}(m) \not= \text{Output}(n) \\ \{m \circ n\} & \text{otherwise} \end{array} \right. \] The resulting structure $(\wp(Arrows(C)),\circ)$ is a monoid with identity $I$ equal to the family of all identity morphisms of the category $C$. The composition function of a category has existence associativity, so that if $(ab)c$ exists then so does $a(bc)$ and then they both coincide. Therefore, the composition of morphism systems is also associative.
A corresponding semilattice structure $(\wp(Arrows(C)), \vee)$ can be defined by the union of morphism systems. This is a unital semilattice, by the fact that $\emptyset$ is an identity with respect to unions. In order to show that $\wp(Arrows(C))$ is a semiring, we only now need to show that these two monoids are related to one another.
Theorem. $(\wp(Arrows(C)),\vee,\circ)$ is a semiring
Proof. for the sake of notation it is convenient to replace the piecewise description of the composition of two morphisms by the composition of two singleton sets $\{m\} \circ \{n\}$. Then we can simply the rewrite the definition of composition, moving around the unions a little in order to get distributivity. \[ F \circ (G \cup H) \] \[ \bigcup_{m \in F, n \in G \cup H} \{m\} \circ \{n\} \] \[=\bigcup_{m \in F} ( \bigcup_{n \in G \cup H} \{m\} \circ \{n\} )\] \[=\bigcup_{m \in F}( ( \bigcup_{n \in G } \{m\} \circ \{n\}) \cup ( \bigcup_{n \in H} \{m\} \circ \{n\})) \] \[ = F\circ G \cup F \circ H \] It follows that $F\circ(G \cup H) = F\circ G \cup F \circ H$, the other distributive law $(F \cup G) \circ H = F \circ H \cup G \circ H$ follows by exactly the same reasoning. In order to confirm the structure is a semiring, we finally need to demonstrate that the additive identity $\emptyset$ is a multiplicative zero. In fact it is, because $\emptyset \circ A = A \circ \emptyset = \emptyset$. It follows that $\wp(Arrows(C))$ is a semiring $\square$
The relationship between the semiring of a category and its partial semigroup, is that the semiring is a multi-valued extension of the ordinary composition of morphisms. In particular, the composition function of a category $(C,\circ)$ can be recovered as a partial semigroup from the subset of the composition monoid of morphism systems consisting of all singleton morphism systems.
The composition of singleton morphisms in the case where no composition exists is the empty set. The partiality of the composition function of a category can be gotten around by adjoining a zero element. This is not necessary when the category $C$ is a monoid.
Semiring of relations:
Let $K_X$ be the complete thin groupoid on $X$. Then the morphisms of $K_X$ are ordered pairs $(a,b)$ and composition of ordered pairs $(a,b)$ and $(b,c)$ is $(a,c)$. Then since morphisms are ordered pairs, morphism systems are relations. Then the composition of relations is a special case of the composition of families of morphisms in a category: \[ R \circ S = \{ (a,c) : \exists (a,b) \in S, (b,c) \in R : (a,b) \circ (b,c) = (a,c) \}\] It follows that $(\wp(Arrows(K_X)),\circ)$ is equal to the composition of relations, and so relation algebra can be recovered by the composition of families of morphisms in a category. By the preceding theorem, $(\wp(Arrows(K_X)),\vee,\circ)$ is also a semiring as a special case of a family of morphism systems of a category.
The semiring congruence of a category:
The composition of morphism systems of a category is an extension of the composition of relations. The semiring of morphism systems of a category extends relation algebra on the semiring level.
Definition. let $F \in \wp(Arrows(C))$ be a morphism system of a category $C$. Then the underlying binary relation $T(F)$ is the subset of $\wp(Ob(C)^2)$ consisting of all ordered pairs of objects in the morphisms of $F$. \[ T : \wp(Arrrows(C)) \to \wp(Ob(C)^2) \] Theorem. let $C$ be a category then the underlying binary relation forms a congruence of the composition of morphism systems.
Proof. let $F,G$ be morphism systems with underlying binary relations $R,S$. Then if $m : A \to C \in F \circ G$ we have that there exists $f : B \to C$ in F and $g : A \to B$ in G such that $m = f \circ g$. Then $(B,C) \in R$ and $(A,B) \in S$ implies $(A,C) \in R \circ S$. In the other direction, suppose that $(A,C) \in R \circ S$ then there exists $f : B \to C$ and $g : A \to B$ such that $f \circ g : A \to C$, so that $(A,C)$ is in the underlying binary relation of $F \circ G$. $\square$
Theorem. let $C$ be a category then the underlying binary relation forms a congruence of the union of morphism systems.
Proof. let $F,G$ be morphism systems with underlying binary relations $R,S$. Then if $m : A \to B$ is in $F \cup G$ then either (1) $m \in F$ in which case $(A,B) \in R$ or (2) $m \in G$ in which case $(A,B) \in S$. Therefore, $(A,B) \in R \cup S$. In the other direction, every ordered pair in $R \cup S$ is an ordered pair of $F \cup G$, so the two coincide. $\square$
Corollary. the underlying binary relation forms a congruence of the semiring of morphism systems of a category.
The fact that the underlying binary relation is a semiring congruence, means that we can say that the composition fo morphism systems in a category is an extension of relation algebra. This is formalized by a semiring homomorphism.
Theorem. $T : \wp(Arrrows(C)) \to \wp(Ob(C)^2)$ is a semiring homomorphism from the semiring of homomorphisms of a category to the semiring of relations.
Proof. the function $T$ is defined by the image functor so it is a union homomorphism. $T(\emptyset = \emptyset)$ so $T$ also preserves additive identities. Finally, each morphism in $R \circ S$ is some composite $g \circ f : A \to C$ with $f : A \to B \in S$ and $g : B \to C \in R$ such that $(A,B) \in T(S)$ and $(B,C) \in T(R)$ so $(A,C) \in T(R) \circ T(S)$. Then in the other direction, $T(R) \circ T(S)$ is all ordered pairs $(A,C)$ such that there is a morphism $f: A \to B \in R$ and a morphism $g : B \to C \in S$ then $g \circ f \in R \circ S$ so $(A,C) \in T(R \circ S)$. Therefore, $T(R \circ S) = T(R) \circ T(S)$. $\square$
The equivalence classes of $T$ do not form intervals, so the underlying binary relation cannot form a lattice congruence. It suffices then to show that they form a semiring congruence, which we have done here.
Relation algebra:
The definition of the composition of morphism systems is based upon the union of the compositions of each individual pair of morphisms, so that composition can be union decomposed. Therefore, $\wp(Arrows(C))$ clearly forms a quantale for any category $C$ but this isn't enough to recover the full relation algebra structure. In order to do that we must recall that $K_X$ is a groupoid. \[ R^{-1} = \{ m^{-1} : m \in R \} \] The inverse of a morphism system of a groupoid is simply the set of inverses of each of its morphisms. With this groupoid-theoretic characterization we have a full characterisation of the relation algebra: $(S,\vee,\wedge, 0,1,\circ,I,-)$.
- $\vee,\wedge$ are the union and intersection of relations. $0$ is the empty relation and $1$ is the complete relation.
- $\circ$ is the composition of morphism systems
- $I$ is the set consisting of all identity morphisms
- $R^{-1}$ maps each morphism to its inverse
We can relate the relation algebra to general categories by the underlying binary relation congruence. In the special case of the morphism system of a groupoid, this also forms a unary congruence of the inverse operation.
Theorem. let $C$ be a groupoid with inverse operation $^{-1} : Ob(C) \to Ob(C)$. Then $T(R^{-1}) = T(R)^{-1}$. The underlying binary relation of the inverse of a morphism system, is the inverse of its underlying binary relation.
Proof. let $f : A \to B$ be a morphism in a groupoid it has ordered pair $(A,B)$ which has inverse $(B,A)$. Its inverse is $f^{-1} : B \to A$ which has ordered pair $(B,A)$ so the two coincide. This then applies to morphism systems on the level of images by these functions. $\square$
Although the morphism systems of categories always extend relations, the special properties of the relation algebra come from their embedding in a groupoid.
Properties of relations:
The properties of relations, expressed in relation algebra, are analogous to those which can be expressed in any category. The morphism system of a subsemigroupoid can be expressed by the condition: \[ R^2 \subseteq R \] The condition $R^2 \subseteq R$ in any quantale expresses composition closure. In a monoid, this defines subsemigroups of the monoid, but in the relation algebra this defines a transitive relation. Categories are basic extensions of transitivity, so transitive relations can be defined like this. The dual condition is: \[ R \subseteq R^2 \] This means that a given morphism system is self-factorizable. The idempotents of $\wp(Arrows(C))$ are clearly all morphism systems that satisfy both conditions. Relation composition forms an ordered semigroup, so that composition is bimonotone. In a number of cases it is also increasing.
When $R$ is reflexive so that $I \subseteq R$ then clearly $R$ is increasing. The same is true of morphism systems of a category with respect to the identity $I$. We have $I \subseteq R$ means that $R \circ S \subseteq R \circ I = R$ and $S \circ R \subseteq I \circ R = R$. The dual condition $I \cap R = \emptyset$ defines irreflexivity. Finally, coreflexive relations $R \subseteq I$ form a distributive lattice subsemiring.
Theorem. coreflexive relations $R \subseteq I$ form a distributive lattice subsemiring.
Proof. (1) union closure follows from the fact that $R \subseteq I$ is a principal down set, as does the membership of $\emptyset$. (2) two loop edges (a,a) are only composable when they are equal, so the composition of coreflexive relations is intersection which is again closed because $R \subseteq I$ forms a principal down set. This means multiplication is a semilattice, so that as a semiring the coreflexive relations form a distributive lattice. $\square$
Systems of identity morphisms still form a distributive lattice subsemiring in any category. The other properties of relations require the use of the inverse, which means that they are only applicable to a groupoid.
- Symmetric : $R^{-1} = R$
- Antisymmetric : $R^{-1} \cap R \subseteq I$
- Functional : $R^{-1} \circ R \subseteq I$
- Inverse functional: $R \circ R^{-1} \subseteq I$
Corollary. the lattice $Part(A)$ is isomorphic to the family of morphism systems of the complete thin groupoid that satsify $I,R^{-1},R^2 \subseteq R$.
We see how a number of concepts like subsemigroupoids, wide subcategories, and wide subgroupoids can be defined by the algebra of morphism systems. In the case of wide thin groupoids, these create the familar classes of relations.
Subsemigroups of relations:
Every relation algebra is associated with the following composition subsemigroups: $PT_X$ consisting of all partial transformations, $PS_X$ the symmetric inverse semigroup of charts, $T_X$ the full transformation monoid, and the symmetric group $S_X$ of permutations.
Each of these subsemigroups is a suborder of $Rel$. The full transformation monoid and the symmetric group form antichains, so we can ignore them for now. On the other hand, $PT_X$ and $PS_X$ both have non-trivial partial orders so we would like to relate the order on them to their semigroups.
Recall that coreflexive relations form a distributive lattice subsemigroup. Let $E$ be the composition subsemigroup of coreflexive relations of $Rel$. The composition of coreflexive relations is decreasing, so its action preorder is a suborder of the dual of the inclusion order of relations.
Input composition by a coreflexive relation is a domain restriction and output composition is codomain restriction. Thusly, the decreasing left actions by $E$ form domain restrictions of relations, which can be used to recover the inclusion ordering of $PT_X$ and $PS_X$. The natural ordering of an inverse semigroup in this context is the same as the inclusion ordering of relations.
No comments:
Post a Comment