symmetric monoidal (∞,1)-category of spectra
monoid theory in algebra:
Given a set , the free monoid on is the set of all lists (finite sequences) of elements of , made into a monoid via concatenation.
The free functor from Set to Mon takes to . Combined with its right adjoint forgetful functor this is the list monad whose modules are monoids.
We will give three definitions, which can all be shown equivalent.
An element of consists of a natural number (possibly ) and function from to , where is the subset of . Such an element is called a list or (to specify ) -tuple of elements of . The number is called the length of the list.
The empty list is the unique list of length . It may be written , , or , perhaps with a subscript if desired.
If , then the list which assigns to may be written . For example, if are elements of , then is an element of .
Given two lists and , the former of length and the latter of length , their concatenation is a list of length , given as follows:
One can now show that concatenation is associative with the empty list as identity; hence is a monoid.
The (underlying) set may be defined as an inductive type as follows. There are two basic constructors, one with no arguments, and one with two arguments, of which one is an element of and the other is an element of . By the yoga of inductive types, that is a complete definition, but we spell it out in more detail while also giving terminology and notation.
So, a list is either the empty list or the cons (short for ‘constructor’ and deriving from Lisp) of an element of and a (previously constructed) list . The empty list may may be written , , or , perhaps with a subscript if desired; the cons of and may be written , , or . We interpret the definition recursively, so we can list the elements of in the order in which they appear:
Here, are elements of . We may continue the ‘etc’ as far as we like, but no farther; while there are lists of arbitrarily long finite length, there are no lists of infinite length. (We would get such lists, however, if we interpreted the definition corecursively, known in computer science as a stream.) We normally abbreviate the lists above as follows:
We still must define the monoidal structure on ; we define the concatenation of and recursively in . To be explicit:
One can now show that concatenation is associative with the empty list as identity; hence is a monoid.
To prove that the category Mon of monoids is a complete category, one normally shows that the forgetful functor (from to the category Set of sets) preserves all limits. Then, the adjoint functor theorem defines a left adjoint to if a size condition is met; this adjoint is the functor that takes a set to its free monoid .
To be sure, meeting the solution set condition basically requires starting the constructions in one of the other definitions above; but the proofs may all be thrown onto the adjoint functor theorem.
Another abstract approach is given in the following general theorem, which applies to more general monoids in a monoidal category:
Suppose is a monoidal category with countable coproducts for which the tensor product distributes over countable coproducts (for example, a cocomplete monoidal biclosed category). Then a left adjoint to the forgetful functor exists, taking an object to
which thereby becomes the free monoid on .
This applies immediately to , as this is a cocomplete cartesian closed category.
In a general dependent type theory where we do not assume uniqueness of identity proofs, the free monoid on a type is the 0-truncation of the type of lists of , . This is because in any dependent type theory with uniqueness of identity proofs, where every type is 0-truncated, the type of lists of is the free monoid of .
Alternatively, the free monoid on can be constructed via the James construction type of .
If is the empty set, then consists only of the empty list; it is the trivial monoid, one manifestation of the point.
If is the point, then is ; the only information in a list of indistinguishable points is the length of the list. The monoid operation on is addition.
If is , then is still a denumerable set. But note that only as sets (that is, as cardinal numbers); they are quite different as monoids.
Generalising the above, if is an infinite set, or more generally if is an inhabited set. (These theorems probably require the axiom of choice, but I haven't checked thoroughly.)
In computer science, the free monoid on a given alphabet is the categorical semantics for the data type “String” with characters in that alphabet.
If the free monoid functor is followed by the forgetful functor , then we get a monad on . This monad is very important as a monad in computer science, where it is known as the list monad.
The list monad bears the same relation to multicategories as the identity monad on bears to ordinary categories. This relation should be explained at generalized multicategory.
Every definition of free monoid makes use of some form of axiom of infinity, either directly or the ability to form general inductive types. Indeed, as , the axiom of infinity follows from the existence of free monoids.
In topos theory the equivalent of the above theorem is due to C. J. Mikkelsen:
Let be a topos and its category of internal monoids. Then has a NNO precisely if the forgetful functor has a left adjoint.
For a proof see Johnstone (1977,p.190).
Furthermore then it is a theorem due to Andreas Blass (1989) that has a NNO precisely if has an object classifier .
A consequence of this, discussed in sec. B4.2 of (Johnstone 2002,I p.431), is that classifying toposes for geometric theories over exist precisely if has a NNO.
From a different perspective then, in a topos the existence of free objects over various gadgets like e.g. algebraic theories or geometric theories often hinge on the existence of free monoids, the intuition being that the free monoids permit to construct a free model syntactically by providing for the (syntactic) building blocks needed for this process.
Notice that algebraic theories can nevertheless have free algebras even if the ambient topos lacks a NNO. This may happen for algebraic theories that have the property that the free algebra on a finite set of generators has a finite carrier e.g. in the topos of finite sets free graphic monoids exist, and free Boolean algebras exist.
In computer science, lists often appear as stacks (not to be confused with the stacks from higher sheaf theory) and queues.
Fix a monoidal category that has coproducts with the unit object . Given an object , an object of stacks on is an object equipped with morphisms and such that these diagrams commute:
The idea is that and are as close to inverses as reasonably possible, but takes us to rather than to , because of the empty stack.
Queues are a little more complicated. An object of queues on is an object equipped with morphisms (‘insert’) and (‘remove’). These operations are far from inverses; whereas popping a stack returns the last item to be pushed onto it, removing an item from a queue returns the first item to have been inserted into it.
What are the diagrams for this? I seem to recall that we need a distributive category; in particular, we need a cartesian monoidal category, so that is . But perhaps a 2-rig will be sufficient?
Jean Bénabou, Some Remarks on Free Monoids in a Topos , pp.20-29 in LNM 1488 Springer Heidelberg 1991.
Andreas Blass, Classifying topoi and the axiom of infinity , Algebra Universalis 26 (1989) pp.341-345.
Peter Johnstone, Topos Theory, Academic Press New York 1977. (Dover reprint Minneola 2014, chap. 6)
Hans-Joachim Baues, Mamuka Jibladze, and Andy Tonks, Cohomology of monoids in monoidal categories, Contemporary Mathematics 202 (1997): 137-166.
Stephen Lack, Note on the construction of free monoids, Applied categorical structures 18 (2010): 17-29.
The list monad as a monad in computer science:
Last revised on September 15, 2024 at 15:58:51. See the history of this page for a list of all contributions to it.