Monoids, automata and related constructions in monoidal categories

Abstract

We collect the concepts and tools necessary to describe monoids, monoid acts and automata in some abstract category C. We give the details of a proof of the coherence theorem for monoidal categories suggested by Mac Lane in his book "Categories for the Working Mathematician" and develop a visual calculus for equational reasoning in monoidal categories that simplifies calculations in comparison to the naïve approach, bringing them close to the ease with which such calculations are carried out in the category Set of sets. We sum up and give proofs of results that describe limits, colimits and free objects in the various categories of monoids and monoid acts internal to our abstract category C. In fact the results we get describe these structures in any category corresponding to what would in Set be the category of a variety of algebras for which the universally quantified variables in the equations describing that variety are in the same order on both sides of every equation (this restriction leads to a more "economical" description than can be given in the general case). This description works in terms of limits and colimits in the ambient category C. Finally we relate the category of automata to the category of biacts via a functor from the former to the latter and present the construction of the tensor product of biacts over some monoid, showing that our functor takes serial composition of automata to the tensor product of biacts.

Wir sammeln die nötigen Begriffe und das nötige Handwerkszeug, um Monoide, Wirkungen und Automaten innerhalb einer abstrakten Kategorie C beschreiben zu können. Als Vorbereitung werden die Details eines Beweises des Kohärenztheorems für monoidale Kategorien nach Anleitung aus Mac Lanes Buch "Categories for the Working Mathematician" ausgearbeitet und eine Möglichkeit vorgestellt, Rechnungen in monoidalen Kategorien auf suggestive Art visuell darzustellen. In Folge werden die notwendigen Resultate gesammelt, um Limites, Kolimites und freie Objekte in den Kategorien der Monoide, Wirkungen, etc. innerhalb der abstrakten Kategorie C beschreiben zu können. Diese Beschreibung verwendet (Ko-)Limites in der Basiskategorie C (an deren Existenz und Kompatibilität wir passende Voraussetzungen stellen) und macht sich die spezielle Struktur der Gleichungen, die Monoide und Wirkungen beschreiben, zu Nutze. (Die spezielle Struktur der Gleichungen ergibt sich im Wesentlichen daraus, dass wir uns ausschließlich erlauben, die monoidale Struktur der Basiskategorie C zu verwenden, und z.B. keine symmetrische Struktur auf dieser Kategorie haben - das hieße übersetzt in die Kategorie der Mengen, dass Variablen auf den zwei Seiten einer Gleichung in der selben Reihenfolge auftreten.) Die Konstruktion ist in einem gewissen Sinne "effizienter" als dies im allgemeinen Fall möglich wäre. Schließlich stellen wir einen Zusammenhang zwischen der Kategorie der Automaten und der Kategorie der beidseitigen Wirkungen her, indem wir einen Funktor von ersterer in letztere konstruieren. Dieser Funktor ist kompatibel mit dem Bilden der seriellen Komposition von Automaten auf der einen und dem Bilden des Tensorprodukts von beidseitigen Wirkungen auf der anderen Seite.