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?

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.
