## Subsemigroups of N

Expand Messages
• Where do I find a proof that every subsemigroup of the additive group of all natural numbers is finitely generated?
Message 1 of 10 , Oct 8, 2004
Where do I find a proof that every subsemigroup of the additive group
of all natural numbers is finitely generated?

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
• Hi, I guess that some elementary number theory texts have this; I m not sure. I published a paper in JSL around 1971 (vol. 36) showing that the first order
Message 2 of 10 , Oct 8, 2004
Hi,

I guess that some elementary number theory texts have this;
I'm not sure. I published a paper in JSL around 1971 (vol. 36)
showing that the first order theory of the set of all subsemigroups
of (N,+) is undecidable. I may have referenced some proof of your
fact in there.

Ralph

--On Friday, October 08, 2004 3:52 PM +0200 Jiri Adamek

>
> Where do I find a proof that every subsemigroup of the additive
> group of all natural numbers is finitely generated?
>
>
> xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
> xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
> xxxxxxxxxx
>
>
>
>
>
>
>
>
>
>
>

-----------------------------------------------------------------
Mckenzie, Ralph N
Vanderbilt University
Email: ralph.n.mckenzie@...
• This fact goes back to Frobenius (and Weierstrass). The problem is to recall who and where mentioned it in print. This is more difficult than just proving the
Message 3 of 10 , Oct 8, 2004
This fact goes back to Frobenius (and Weierstrass). The problem is to
recall who and where mentioned it in print. This is more difficult
than just proving the fact.

Boris.
• ... You can also prove it using partial algebras. Starting from relative partial subsemigroups of N. The main construction is in a paper due to Mikenberg, I
Message 4 of 10 , Oct 8, 2004

>Where do I find a proof that every subsemigroup of the additive group
>of all natural numbers is finitely generated?
>
>
>xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
>xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
>
>
>
>
>
You can also prove it using partial algebras. Starting from relative
partial subsemigroups of N.
The main construction is in a paper due to Mikenberg, I (1984?)

A. Mani
Member, Cal. Math. Soc
• Obavam se Jirko, ze s nalezenim tohoto faktu budes mit problemy. Je to folklor, takze se da ocekavat v nejake zakladni ucebnici algebry. Ale moc bych neveril
Message 5 of 10 , Oct 11, 2004
Obavam se Jirko, ze s nalezenim tohoto faktu budes mit problemy. Je to
folklor, takze se da ocekavat
v nejake zakladni ucebnici algebry. Ale moc bych neveril na pologrupy,
protoze se to tam prakticky nepouziva. Kde to hledat nevim, mam to z
nejake prednasky jeste ze studia fakulty.
Vasek
• Ahoj Venco, no to je legrace, zespolu komunikujeme takhle!!! Dostal jsem par odpovedi, jako ze uz to vedel Weierstrass..., ale kupodivu i konkretni clanek, kde
Message 6 of 10 , Oct 12, 2004
Ahoj Venco,
no to je legrace, zespolu komunikujeme takhle!!! Dostal jsem par odpovedi,
jako ze uz to vedel Weierstrass..., ale kupodivu i konkretni clanek, kde
to stoji, tak to mam radost.
Cau, Jirka

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
• Ahoj Venco a Jirko. To je fakt legrace :-)). P
Message 7 of 10 , Oct 12, 2004
Ahoj Venco a Jirko.
To je fakt legrace :-)).
P

> Ahoj Venco,
> no to je legrace, zespolu komunikujeme takhle!!! Dostal jsem par odpovedi,
> jako ze uz to vedel Weierstrass..., ale kupodivu i konkretni clanek, kde
> to stoji, tak to mam radost.
> Cau, Jirka
>
> xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
> xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
• ... Sorry, my previous reaction was too vague (laziness, common laziness...) There was a reference to related results (provided by Melvin Henriksen). The Redei
Message 8 of 10 , Oct 12, 2004
>Where do I find a proof that every subsemigroup of the additive group
>of all natural numbers is finitely generated?

Sorry, my previous reaction was too vague (laziness, common laziness...)

There was a reference to related results (provided by Melvin Henriksen).

The Redei theorem says: congruences on a finitely generated free
commutative semigroup satisfy the ascending chain condition (= are
themselves finitely generated = a finitely generated comm. semigroup
is finitely presentable). Take the free comm. semigroup with a single
generator and...

L. R\'edei, Theorie der endlich erzeugbaren kommutativen Halbgruppen,
Physica Verlag, W\"urzburg, 1963 (English edition
appeared in 1965).

There are quite a few proofs, it's a kind of sport in which people
tried to make the proof as short as possible. There are 1-page proofs
and, by now, probably even shorter proofs. I can give some
references, if needed.

However, this is not exactly Jiri's question.

Concerning Weierstrass, Hurwitz etc. see, for example, J. Komeda's
papers and a big crowd of similarly minded people.

The structure of EVERY subsemigroup S of the additive sgp of
natural numbers is this: It has finitely many numbers followed (in
the natural order sense) by an infinite arithmetic progression with
some difference (=step of the progression) d. This d is the
greatest common divisor of all elements of S. If we divide all the
elements of S by d, we get an isomorphic semigroup S' that has
finitely many initial numbers followed by ALL natural numbers
beginning from a certain number n + 1.

I think this was known to the "ancients". If I remember correctly, it
was Dedekind who was interested in the size of n provided the
finitely many generators (in the irregular initial part of S') are
known. This is a tough problem. There were some papers (and tech
reports) on that published in Norway.

Now, Dedekind published papers and also wrote letters and also gave
talks and also... So if it was him indeed, the historians may know
the reference.

I guess if we look at things in a sufficiently creative way,
we can find this fact mentioned in the Bible.

Boris.
• A comment to my previous comments. I asked a friend who was interested in the subsemigroups of free commutative monoids. He is far from home and cannot look up
Message 9 of 10 , Oct 13, 2004
A comment to my previous comments.

I asked a friend who was interested in the subsemigroups of free
commutative monoids. He is far from home and cannot look up his
sources but he told me that the number n I called the Dedekind
number is called the Frobenius number. So substitute Frobenius for
Dedekind.

Boris.
• Dear Ralph, I think I will send you some math questions over the holidays, when I read what JB sent us. Now, I just wonder if you (or a secretary) sent me any
Message 10 of 10 , Nov 23, 2004
Dear Ralph,
I think I will send you some math questions over the
holidays, when I read what JB sent us. Now, I just
wonder if you (or a secretary) sent me any
correspondence concerning the AMS meeting in Nashville
(I submitted some form to you about the flight). I am
asking since I believe I could miss some mail
recently.

Best regards,
have a nice long weekend,
Kira.
Your message has been successfully submitted and would be delivered to recipients shortly.
»
«