partitions are the elements of the free abelian monoid on $\aleph_0$ generators

Question

although the following insight may not be particularly profound, it is always of interest when we see a canonical isomorphism between objects of apparently different types.

it is a commonplace that the set of partitions of a natural number $n$ are in 1-1 correspondence with the conjugacy classes of the symmetric group $S_n$. what i have not seen pointed out (though doubtless this is due to my scanty acquaintance with the mathematical literature) is the fact that the natural place where these entities are to be found - if we include the empty partition for completeness - is as elements of the free abelian monoid on $\aleph_0$ generators.

if we denote the generators of this monoid by $\{x_n\}_{n=1,2,3...}$ then a partition of rank $k$ (meaning that exactly $k$ different numbers occur at least once in the partition) has a unique representation as the element: $$ x = \sum_{j=1}^k a_j x_{b_j} $$ where $a_j \ge 1$ and $i \lt j \rightarrow b_i \lt b_j$

it may be that the lack of attention to this obvious identification is due to two causes,

(a) historical reasons, and the rather unsystematic, heuristic-dominated nature of combinatorial analysis as a branch of math.

(b) that the identification just noted has no obvious application of any depth.

but clarity in notation is always worth pursuing. so my question is: if we feel that a spade should be called a spade, why should not a free abelian monoid be recognized for what it is, and all the more so considering the great service the partitions render to us in many sub-disciplines of our subject?

even if this question is thought too trivial to be worth consideration, it serves to introduce a notation which will be of use in formulating one or two other queries i have concerning partitions. any useful information relevant to the theme will be appreciated.

thank you

Answer 1

I'm not quite sure what the question is, but you're 100% correct. The way I look at it:

There's a category $\mathbf{CMon}$ of commutative monoids. The underlying set functor $U:\mathbf{CMon} \rightarrow \mathbf{Set}$ has a left-adjoint $F:\mathbf{Set} \rightarrow \mathbf{CMon}$. Write $\varepsilon$ for the counit of the adjunction $F \dashv U.$ Now observe that for any commutative monoid $A$, we get a homomorphism $\varepsilon_A : FUA \rightarrow A$. This allows us to define that a partitioning of $a \in A$ is just an element of $\varepsilon^{-1}_A(a)$. We recover the usual definition by taking $A$ to denote the commutative monoid $(\mathbb{N},+,0)$. But in fact, we may speak of the partitionings of the elements of any commutative monoid.

Okay. What happens if we replace $\mathbf{CMon}$ by $\mathbf{Mon}$? If you think about it, you'll see that we instead obtain the notion of a composition of a natural number.

In general (this is my own terminology), if $A$ is an object of a concrete category whose underlying set functor $U$ has a left adjoint $F$, then by a dispersion of $a \in A,$ I mean an element of $\varepsilon^{-1}_A(a)$, where $\varepsilon$ is the counit of $F \dashv U$. Of course, this is sensitively dependent on the concrete category that we're regarding the structure $X$ as an object of. This was seen in the previous paragraph, where the notion of a dispersion of $n \in \mathbb{N}$ means one thing (namely, a partitioning) if $\mathbb{N}$ is being viewed as a commutative monoid, and another thing (namely, a composition) if it is being viewed as an (ordinary) monoid.

Hopefully that was helpful :)