# Is the set of submonoids of $(\Bbb N,+)$ countable?

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?

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

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

• 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? May 18 '13 at 6:04
• 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, +)$. May 18 '13 at 6:19
• 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. May 18 '13 at 14:18
• 2. See the introduction of this and its references. I don't know offhand a simple proof for the existence of embedding dimension. May 18 '13 at 14:21

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.