Let $S$ be a finitely generated free abelian semigroup (or monoid), and let $T \subset S$ be a sub-semigroup (sub-monoid). Does the Nielsen-Schreier theorem hold in this case, that is, will $S$ still be free? Moreover, will $S$ be finitely generated as in the groups case?
$\begingroup$
$\endgroup$
6
-
7$\begingroup$ This fails even for $S = \mathbb{N}$. The submonoid generated by $2, 3$ isn't free. $\endgroup$– Todd TrimbleCommented Dec 7, 2017 at 18:48
-
$\begingroup$ how about finitely generated? $\endgroup$– Alesandro LeviCommented Dec 7, 2017 at 18:51
-
$\begingroup$ I have a feeling that fails too, although it might take more work. For example, if you can find an infinite sequence of primes $p_n$ so that each $p_n$ is not an $\mathbb{N}$-linear combination of primes earlier in the sequence. $\endgroup$– Todd TrimbleCommented Dec 7, 2017 at 18:57
-
2$\begingroup$ @ToddTrimble isn't it the case, that if $a$ and $b$ are coprime, then the submonoïd they span contains all integers beyond some integer $c$ ? $\endgroup$– Olivier BégassatCommented Dec 7, 2017 at 19:00
-
1$\begingroup$ To summarize, it's straightforward that in a free abelian semigroup/monoid on $r$ generators (a) there are non-free finitely generated subsemigroups/submonoids iff $r\ge 1$ (b) there are infinitely generated subsemigroups/submonoids iff $r\ge 2$ (which for $r$ finite are automatically non-free). $\endgroup$– YCorCommented Dec 8, 2017 at 0:16
|
Show 1 more comment
3 Answers
$\begingroup$
$\endgroup$
3
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.
answered Dec 7, 2017 at 20:19
-
$\begingroup$ 1. It is Shevrin, not Sevrin. 2 .The theorem similar to that of Shevrin was published somewhat earlier by M.P. Schützenberger. 3. Free abelian monoids (sets of vectors with non-negative integral coordinates under addition) have very little in common with free monoids (sets of words under concatenation). $\endgroup$– user6976Commented Dec 9, 2017 at 13:25
-
$\begingroup$ @MarkSapir: Thank you; I was using the spelling as it appeared in P.M. Cohn's paper. Presumably, the romanization has changed. $\endgroup$ Commented Dec 9, 2017 at 20:43
-
$\begingroup$ An alternative spelling would be \v Sevrin as in MR0111795. $\endgroup$– user6976Commented Dec 9, 2017 at 23:41
$\begingroup$
$\endgroup$
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.
answered Dec 10, 2017 at 4:28
$\begingroup$
$\endgroup$
Here is (partially) what is known about commutative monoids and their submonoids.
The elementary theory of every finitely generated commutative semigroup (monoid) is decidable (Taiclin).
The isomorphism problem for finitely generated commutative semigroups (monoids) is decidable (Taiclin).
Every finitely generated commutative monoid is representable by matrices over $\mathbb Z$, hence is residually finite and Hopfian (Malcev).
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).
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.