Loading ...
Sorry, an error occurred while loading the content.

Subsemigroups of N

Expand Messages
  • Jiri Adamek
    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
    • 0 Attachment
      Where do I find a proof that every subsemigroup of the additive group
      of all natural numbers is finitely generated?


      xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
      alternative e-mail address (in case reply key does not work):
      J.Adamek@...
      xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
    • Mckenzie, Ralph N
      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
      • 0 Attachment
        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
        <adamek@...-bs.de> wrote:

        >
        > Where do I find a proof that every subsemigroup of the additive
        > group of all natural numbers is finitely generated?
        >
        >
        > xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
        > xxxxxxxxxx alternative e-mail address (in case reply key does not
        > work): J.Adamek@...
        > xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
        > xxxxxxxxxx
        >
        >
        >
        >
        > Yahoo! Groups Links
        >
        >
        >
        >
        >
        >
        >



        -----------------------------------------------------------------
        Mckenzie, Ralph N
        Vanderbilt University
        Email: ralph.n.mckenzie@...
      • Boris M Schein
        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
        • 0 Attachment
          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.
        • A. Mani
          ... 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
          • 0 Attachment
            Jiri Adamek wrote:

            >Where do I find a proof that every subsemigroup of the additive group
            >of all natural numbers is finitely generated?
            >
            >
            >xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
            >alternative e-mail address (in case reply key does not work):
            >J.Adamek@...
            >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
          • Vaclav Koubek
            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
            • 0 Attachment
              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
            • Jiri Adamek
              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
              • 0 Attachment
                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
                alternative e-mail address (in case reply key does not work):
                J.Adamek@...
                xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
              • Pavel Jiranek
                Ahoj Venco a Jirko. To je fakt legrace :-)). P
                Message 7 of 10 , Oct 12, 2004
                • 0 Attachment
                  Ahoj Venco a Jirko.
                  To je fakt legrace :-)).
                  P

                  Jiri Adamek wrote:
                  > 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
                  > alternative e-mail address (in case reply key does not work):
                  > J.Adamek@...
                  > xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
                • Boris M Schein
                  ... 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
                  • 0 Attachment
                    >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.
                  • Boris M Schein
                    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
                    • 0 Attachment
                      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.
                    • Kira Adaricheva
                      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
                      • 0 Attachment
                        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.