nLab free commutative monoid

Redirected from "formal linear combination".
Contents

Context

Algebra

Monoid theory

Contents

1. Idea

The free commutative monoid [S]\mathbb{N}[S] on a set SS is the commutative monoid whose elements are formal \mathbb{N}-linear combinations of elements of SS.

2. Definition

Definition 2.1. Let

U:CMonSet U \colon CMon \longrightarrow Set

be the forgetful functor from the category CMon of commutative monoids, to the category Set of sets. This has a left adjoint free construction:

[]:SetCMon. \mathbb{N}[-] \colon Set \longrightarrow CMon \,.

This is the free commutative monoid functor. For SS \in Set, the free commutative monoid [S]\mathbb{N}[S] \in CMon is the free object on SS with respect to this free-forgetful adjunction.

Of course, this notion is meant to be invariant under isomorphism: it doesn’t depend on the left adjoint chosen. Thus, if a functor of the form hom Set(S,U):CMonSet\hom_{Set}(S, U-): CMon \to Set is representable by a commutative monoid MM, then we may say MM is a free commutative monoid on SS. A specific choice of isomorphism

hom CMon(M,)hom Set(S,U)\hom_{CMon}(M, -) \cong \hom_{Set}(S, U-)

corresponds, via the Yoneda lemma, to a function SUMS \to U M which exhibits SS, or rather its image under this function, as a specific basis of MM. If MM is so equipped with such a universal arrow SUMS \to U M, then it is harmless to call MM “the” free commutative monoid on SS.

Explicit descriptions of free commutative monoid are discussed below.

3. Properties

In terms of formal linear combinations

Definition 3.1. A formal linear combination of elements of a set SS is a function

a:S a : S \to \mathbb{N}

such that only finitely many of the values a sa_s \in \mathbb{N} are non-zero.

Identifying an element sSs \in S with the function SS \to \mathbb{N} which sends ss to 11 \in \mathbb{N} and all other elements to 0, this is written as

a= sSa ss. a = \sum_{s \in S} a_s \cdot s \,.

In this expression one calls a sa_s \in \mathbb{N} the coefficient of ss in the formal linear combination.

Remark 3.2. Definition 3.1 of formal linear combinations makes sense with coefficients in any commutative monoid MM, not necessarily the natural numbers.

M[S][S]M. M[S] \coloneqq \mathbb{N}[S] \otimes M \,.

Definition 3.3. For SS \in Set, the monoid of formal linear combinations [S]\mathbb{N}[S] is the monoid whose underlying set is that of formal linear combinations, def. 3.1, and whose monoid operation is the pointwise addition in \mathbb{N}:

( sSa ss)+( sSb ss)= sS(a s+b s)s. (\sum_{s \in S} a_s \cdot s) + (\sum_{s \in S} b_s \cdot s) = \sum_{s \in S} (a_s + b_s) \cdot s \,.

Proposition 3.4. The free commutative monoid on SSetS \in Set is, up to isomorphism, the monoid of formal linear combinations, def. 3.3, on SS.

Proposition 3.5. For SS a set, the free commutative monoid [S]\mathbb{N}[S] is the biproduct in CMon of |S|{|S|}-copies of \mathbb{N} with itself:

[S] sS. \mathbb{N}[S] \simeq \oplus_{s \in S} \mathbb{N} \,.

4. Examples

Last revised on May 21, 2021 at 22:29:48. See the history of this page for a list of all contributions to it.