2
$\begingroup$

Let $\mathbf{CMon}$ be the category of all commutative monoids and the monoid homomorphisms and let $U:\mathbf{CMon}\to \mathbf{Set}$ be the forgetful functor. Prove that $U$ has a left adjoint.

I know that this can be done by direct construction, but I want to see if this can be done by applying the General Adjoint Functor Theorem. I have shown that $\mathbf{CMon}$ is locally small and complete, which should leave me to show that $U$ is continuous (preserves small limits) and the comma category $S\downarrow U$ has a jointly weakly initial set of objects where $S\in\mathbf{Set}$ is arbitrary.

For the first part, I know that in general, the forgetful functor would preserve the small limits, but I am having trouble checking that out manually. As for the second part, how do you actually find such a set (I haven't seen many examples of finding the weak initial set)? I appreciate your help!

$\endgroup$
2
$\begingroup$

Limits of (commutative) monoids can simply by constructed with pointwise operations from the underlying limits of sets. This shows immediately that $\mathbf{CMon}$ is complete and that $U$ is continuous. To show the solution set condition, let $M$ be a commutative monoid and let $f : S \to U(M)$ be a map. Consider the submonoid $M'$ of $M$ generated by the image of $f$. Explicitly, $M'$ consists of all $\mathbb{N}$-linear combinations of elements of the form $f(s)$, where $s \in S$. The next step is to bound the size of the underlying set of $M'$. This is usually done with cardinal numbers, but actually one does not need cardinal numbers at all for this argument. Notice that there is a surjective map*

$\coprod_{n \in \mathbb{N}} (\mathbb{N} \times S)^n \to U(M').$

which maps $((m_1,s_1)),\dotsc,(m_n,s_n))$ to $m_1 f(s_1) + \cdots + m_n f(s_n)$. It follows that $U(M')$ is isomorphic to a subset of the set $T := \coprod_{n \in \mathbb{N}} (\mathbb{N} \times S)^n$ (which only depends on $S$). By structure transport, it follows that $M'$ is isomorphic to a monoid whose underlying set is a subset of $T$. But there is only a set of such monoids. Therefore, a solution set consists of those monoids whose underlying set is a subset of $T$.

By the way, a similar argument shows that for every finitary algebraic category $\mathcal{C}$ the forgetful functor $\mathcal{C} \to \mathbf{Set}$ has a left adjoint. In fact, it is even monadic.

For commutative monoids, though, the simplest way is just a direction construction: the underlying set of the free commutative monoid on $S$ is the set of functions $S \to \mathbb{N}$ with finite support (these formalize linear combinations with $\mathbb{N}$-coefficients in $S$), and the operation comes from $\mathbb{N}$. For monoids and groups (or lie algebras etc.), direct constructions are not so straight forward anymore and the above method gives a really slick existence proof.

*Alternatively, you can use a surjective map $\coprod_{n \in \mathbb{N}} S^n \to U(M')$.

$\endgroup$
1
$\begingroup$

You cannot do this with just the adjoint functor theorem. In fact, it is necessary to somehow use the existence of $\mathbb{N}$ in your proof because the existence of $\mathbb{N}$ can be proved using the fact that free monoids exist (since $\mathbb{N}$ is the free monoid on 1 element) and the axiom of infinity is independent from the other axioms of ZFC. Note that the axiom of infinity is not necessary to prove the adjoint functor theorem, so the adjoint functor theorem alone will not be enough.

In fact, in order to prove the existence of free algebraic structures of other types, it is typical to first prove the existence of free monoids.

Of course, you'll want to use the fact that the free monoid over $S$ is just the set of finite sequences over $S$, with the operation being sequence concatenation and the identity element being the empty sequence.

$\endgroup$
4
  • $\begingroup$ Surely the existence of $\mathbb{N}$ can be used here. I don't know why we have to back to the ZFC axioms here and start from nothing? Your sentence "In fact, in order to prove the existence of free algebraic structures of other types, it is typical to first prove the existence of free monoids." is not true: maybe some authors do that, but it is not typical (in fact, I have never seen that). $\endgroup$ – Martin Brandenburg May 25 at 22:49
  • $\begingroup$ @MartinBrandenburg Your solution is correct, but it is needlessly complicated. In fact, you can instead use a surjective map $\coprod\limits_{n \in \mathbb{N}} S^n \to M'$ which maps $(s_1, s_2, ...., s_n)$ to $f(s_1) + f(s_2) + ... + f(s_n)$. But this map is exactly the free monoid map. So in the simpler and more natural version of your proof, you actually explicitly construct the free monoid and then use it to construct the free monoid. $\endgroup$ – Mark Saving May 25 at 22:57
  • $\begingroup$ Yes, this map is simpler (and I have added it to my answer), but we don't actually need any monoid structure on it for the proof. So it's not circular. Also, let's remember that the question was "I know that this can be done by direct construction, but I want to see if this can be done by applying the General Adjoint Functor Theorem.". $\endgroup$ – Martin Brandenburg May 25 at 23:23
  • $\begingroup$ @MartinBrandenburg I agree it's not circular. I'm just saying that it is unnecessarily complicated. And you cannot generalize your method to more complicated structures (eg free groups) without first constructing basic inductive sets in advance. For example, how do you show the existence of binary trees using your method (the free algebra with a single binary operation)? You need to do some work to construct this from lists explicitly. $\endgroup$ – Mark Saving May 25 at 23:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.