The monoid of integers is not free

Question

I am reading the introductory lessons on Category Theory on wikiversity, and they discuss free monoids here: https://en.wikiversity.org/wiki/Introduction_to_Category_Theory/Monoids

At the bottom they prove that the monoid of integers is not free, and their definition of a free monoid is that whose every arrow can be uniquely represented as a composition of arrows from a finite collection S of arrows. So, to disprove that the integers are a free monoid, they try to show that the arrow 1 can be generated by two distinct compositions of generators:

"If the set of generators contains the number 1, then it can't contain any other positive integer, since every positive integer is a finite sum of 1's. It can't contain any negative numbers either, since any negative number plus a finite sum of 1's is 1.

On the other hand every set of generators must generate number 1, so 1 is the finite sum $(s_1 + s_2 + ... + s_n)$ of generators. But a finite sum of finite sums is a finite sum, so every positive generator $s_0$ can be composed as $s_0 = (s_1 + ... + s_n)_1 + (s_1 + ... + s_n)_2 + ... + (s_1 + ... + s_n)_{s_0}$

For a negative generator $-s_0$ we have $-s_0 + (s_1 + ... + s_n)_1 + (s_1 + ... + s_n)_2 + ... + (s_1 + ... + s_n)_{s_0+2} = 1 = (s_1 + ... + s_n)$

that gives two different compositions for the number 1."

EDIT: As the comments point out my source of knowledge is not ideal, so if there is a proof with better (standard?) notation I'd appreciate it if anyone can share it or can offer any hints to it.

Answer 1

Suppose that $(\mathbb{Z}, +, 0)$ is isomorphic to the free monoid $A^*$ of basis $A$. Since $A^*$ is not commutative if $A$ contains at least 2 elements, $A$ is a singleton $\{a\}$. This means that $(\mathbb{Z}, +, 0)$ is equal to the additive monoid generated $M$ by some $a \not= 0$, which is not possible since $M$ does not contain $-a$.

One can also show that $(\mathbb{Z}, +, 0)$ is not free in the category of commutative monoids. To make it free, you need to consider the category of groups. Then indeed, $(\mathbb{Z}, +, 0)$ is a free group.

Answer 2

This is really just a fact about monoids, not about category theory except insofar as the very notion of freeness is categorical. So, why is $\mathbb{Z}$ not a free monoid? The first point is that it needs at least two generators: given a generator $a$, the monoid operations only suffice to generate $a\mathbb{N}$, which can't possibly be all of $\mathbb{Z}$. So it suffices to show that any two generators must satisfy a relation, i.e. that the submonoid $\langle a,b\rangle$ generated by two nonzero integers $a,b$ can't be free.

It seems necessary to do this in cases, since the monoid axioms only permit positive linear combinations, but this comes down essentially to the relation $ab=ba$.

Suppose $a$ and $b$ are of different signs, without loss of generality, $b<0<a$. Then $\underbrace{(a+a+...+a)}_{-b\text{ times}}+\underbrace{(b+b+...+b)}_{a\text{ times}}=ab-ba=0$ shows $\langle a,b\rangle$ isn't free.

Suppose on the other hand $a$ and $b$ are both positive (negative.) Then we get directly the relation $ab=ba$ ($(-a)b=(-b)a$) in $\langle a,b\rangle$.

In other words, no copy of $\mathbb{N}^2$ fits inside $\mathbb{Z}$, so the latter can't be free.