Nielsen-Schreier theorem for monoids

For the question of finite generation, here's a a counterexample that appears in D.B. McAlister and L. O'Carroll, Finitely generated commutative semigroups. Glasgow Math. J. 11 1970 134–151. MR0269765 (42 #4660:

If $S$ is the free commutative semigroup on $a$ and $b$, and $K=\{a^nb^m\mid n,m>0\}$, then $K$ is not finitely generated: note that elements of the form $ab^k$ and of the form $a^kb$ cannot be the product of two or more elements of $K$ (since a product with $m$ factors will have both exponents greater than or equal to $m$), so you need all of them in any generating set for $K$.

Nielsen-Schreier ("subsemigroup of free is free") fails for even the cyclic free semigroup, as noted; and in general does not hold for non-commutative semigroups either. L.N. Shevrin proved, inter alia, that a subsemigroup $T$ of a free semigroup $S$ is free if and only if for every $a\in T$ and $s\in S$, if $as$ and $sa$ are both in $T$, then $s\in T$. (L.N. Shevrin, On subsemigroups of free semigroups, Dokl. Akad. Nauk SSSR 133 (1960), 537-539 (Russian) Soviet Math. Dokl.1 (1960), 892-894.)

Alternatively, P.M. Cohn proved that a subsemigroup $T$ of a free semigroup $S$ is free if and only if for any $a,a',b,b'\in T$, if $ab'=ba'$ then $a=bx$ or $b=ax$ for some $x\in T$. ( P.M. Cohn, On Subsemigroups of Free Semigroups Proceedings of the American Mathematical Society Vol. 13, No. 3 (Jun., 1962), pp. 347-351 DOI: 10.2307/2034935). Though these are for non-commutative semigroups, I expect similar conditions would be needed to guarantee that a subsemigroup si free. In any case, the easy example given by Todd Trimble shows you cannot hope to have a submonoid/subsemigroup of a free commutative monoid/semigroup always be free.


The question of whether a (finitely generated) submonoid of a free commutative monoid is free has been asked and answered. The answer is No. One can then ask: how far will it be from being free? This refinement of the question is answered by a theorem of Rédei from 1965: any finitely generated commutative monoid is finitely presentable.

If you drop commutativity, Rédei's Theorem becomes false. One can even find finitely generated submonoids of free monoids that are not finitely presentable, such as the submonoid of the free $4$-generated monoid $F_{\textrm{Mon}}(a,b,c,d)$ generated by $u=a$, $v=b$, $w=ac$, $x=cb$, $y=cd$, $z=dc$. It has the presentation $$\langle u, v, w, x, y, z\;|\;uy^kx=wz^kv, \;\;k=0,1,2, \ldots\rangle$$ and none of the relators can be omitted.


Here is (partially) what is known about commutative monoids and their submonoids.

  1. The elementary theory of every finitely generated commutative semigroup (monoid) is decidable (Taiclin).

  2. The isomorphism problem for finitely generated commutative semigroups (monoids) is decidable (Taiclin).

  3. Every finitely generated commutative monoid is representable by matrices over $\mathbb Z$, hence is residually finite and Hopfian (Malcev).

  4. Every finitely generated commutative monoid is finitely presented (Redei) moreover it admits a finite Church-Rosser presentation and for every finite presentation, the Knuth-Bendix algorithm terminates (all these essentially follow from the Hilbert Finite Basis theorem).

  5. The lattice of subsemigroups of the infinite cyclic semigroup does not satisfy any non-trivial identity (Repnitskii, Katsman). In contrast, the lattice of subgroups of any commutative group is modular.