symmetric monoidal (∞,1)-category of spectra
Given a set , the free monoid on is the set of all lists (finite sequences) of elements of , made into a monoid using concatenation. The free functor from Set to Mon takes to .
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.
If the free monoid functor is followed by the forgetful functor , then we get a monad on . This monad is very important 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.
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)
Last revised on June 7, 2019 at 08:18:36. See the history of this page for a list of all contributions to it.