8
$\begingroup$

Having the monoid $(\Bbb N,+)$, I wonder if there are countable many submonoids. There are obviously infinitely many since $S_n = \{kn \mid k \in \Bbb N\}$ is a submonoid for any $n \in \Bbb N$.

My conjecture is that the set of all submonoids is countable, because I think the following statements (which I failed to prove so far) hold for any submonoid $S$ of $(\Bbb N,+)$:

  • there is an odd element in $S$ $\Rightarrow \exists e \forall f: (f \ge e \rightarrow f \in S)$ $\Rightarrow \Bbb N \setminus S$ is finite

  • all elements of $S$ are even $\Rightarrow \exists e \forall f: (2f \ge e \rightarrow 2f \in S)$ $\Rightarrow \Bbb N \setminus (S \cup \{1,3,5,...\})$ is finite

In both cases we can identify the submonoid by a finite set of numbers which are not elements of the submonoid. Therefore we have only countable many possibilities.

Can you complete this approach or provide a better one?

$\endgroup$
  • 1
    $\begingroup$ Your proposed dichotomy isn't correct; consider $\{0, 3, 6, 9, \dots\}$ which contains an odd element but is not cofinite. $\endgroup$ – Nate Eldredge May 18 '13 at 4:09
  • $\begingroup$ You are right. The first case should be something like "contains two numbers with gcd=1" and the second case must be generalized. $\endgroup$ – Simon S May 18 '13 at 6:15
4
$\begingroup$

Yes, it is countable. Let $\mathcal{F}(\mathbb{N})$ be the set of finite subsets of $\mathbb{N}$. Let $\mathcal{M}(\mathbb{N})$ be the set of submonoids of $\mathbb{N}$. There is a map $f: \mathcal{F}(\mathbb{N}) \to \mathcal{M}(\mathbb{N})$ which, for any finite set of natural numbers returns the submonoid generated by those natural numbers. The lemma below proves that $f$ is a surjection; since $\mathcal{F}(\mathbb{N})$ is countable it follows that so is $\mathcal{M}(\mathbb{N})$. $\square$

Lemma: any submonoid of $\mathbb{N}$ is finitely generated.

Proof: Let $A$ be a submonoid of $(\mathbb{N}, +)$. Let $d$ be the GCD of all the elements of $A$. Dividing out by $d$ we obtain an isomorphic submonoid $A'$ with GCD $1$. So there exist elements $a_1, a_2, \ldots, a_k \in A'$ with $\gcd(a_1, \ldots, a_k) = 1$.

It is simple to show that for any set of positive integers with GCD 1, there are only finitely many positive integers which cannot be written as a finite sum of elements of the set. This follows from Generalized Bezout's identity with a little work. The case with a set of two relatively prime integers $a,b$ is well-known (sometimes called the Chicken McNugget Theorem), with the largest integer that cannot be written as a finite sum being $ab - a - b$. In general, finding the largest integer that cannot be written as a finite sum is harder, and is known as the Coin problem.

This is all to show that $A'$ is generated by the finite set $\{a_1, a_2, \ldots, a_k, b_1, b_2, \ldots, b_m\}$ where $b_1, b_2, \ldots, b_m$ are the finitely many integers that cannot be expressed as a finite sum of the $a_i$s. So $A'$ is finitely generated, and since $A$ is isomorphic to $A'$, $A$ is finitely generated.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

All numerical monoids have finitely many generators (called the embedding dimension), and the set of finite subsets of $\mathbb{N}$ is countable.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you. From the article: "It is known that every numerical semigroup S has a unique minimal system of generators and also that this minimal system of generators is finite." Could you provide a proof or a reference to a proof of this? $\endgroup$ – Simon S May 18 '13 at 6:04
  • $\begingroup$ I just realized that the complement of a numerical semigroup must be finite by definition. This does not hold for all submonoids of $(\Bbb N, +)$. $\endgroup$ – Simon S May 18 '13 at 6:19
  • $\begingroup$ 1. If an additive submonoid of $\mathbb{N}$ has infinite complement, then every element has a common divisor. Dividing by that divisor gives a numerical monoid. $\endgroup$ – vadim123 May 18 '13 at 14:18
  • $\begingroup$ 2. See the introduction of this and its references. I don't know offhand a simple proof for the existence of embedding dimension. $\endgroup$ – vadim123 May 18 '13 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.