While trying to solve a somewhat bigger problem, I realized that I don't know what the subsemigroups of one of the most important semigroups, $(\mathbb N,+)$, are. (I assume $0\not\in\mathbb N$.) I've tried to characterize them but I haven't managed to do it fully. What follows are the facts I have proven so far, without most of the proofs but with lemmas, which hopefully show how the proofs go. I'm not posting all the proofs not because I'm sure my proofs are correct, but because I don't want to make this post too long. I will add the proof of anything below on request.
Notation. $\langle a_1,\ldots,a_n\rangle$ will denote the subsemigroup generated by $a_1,\ldots,a_n\in\mathbb N$. If $X\subseteq \mathbb N$, then $\langle X\rangle$ willl denote the subsemigroup generated by $X$.
Lemma 1. $\langle a_1,\ldots,a_n\rangle = \{k_1a_1+\ldots+k_na_n\,|\,k_i\geq 0,\,\sum k_i>0\}.$
Lemma 2. If $a_1,\ldots,a_n\in\mathbb N$ and $\gcd(a_1,\ldots,a_n)=1,$ then there exists $x\in \langle a_1,\ldots,a_n\rangle$ such that for every $n\geq x,\,n\in\mathbb N,$ we have that $n\in \langle a_1,\ldots,a_n\rangle.$
Notation. For $n\in\mathbb N$ and $X\subseteq \mathbb N$, $nX$ will denote $\{nx\,|\,x\in X\}.$
Lemma 3. For every finitely generated subsemigroup $S=\langle a_1\ldots,a_n\rangle$ of $\mathbb N$, there exists a finitely generated subsemigroup $T$ of $\mathbb N$ whose generators are coprime and such that $S=\gcd(a_1,\ldots,a_n)\,T$.
Proposition 4. Every finitely generated subsemigroup $S=\langle a_1,\ldots,a_n\rangle$ of $\mathbb N$ eventually becomes an infinite arithmetic progression with difference $d=\gcd(a_1,\ldots,a_n)$. That is, there exists $x\in S$ such that $S\cap\{n\in\mathbb N\,|\,n\geq x\}=\{x+kd\,|\,k\geq 0\}.$ (It has to be noted that $d|x.$)
Lemma 5. If $X\subseteq \mathbb N$, then there exists a unique $\gcd(X),$ that is a number $d\in\mathbb N$ such that for all $x\in X$ we have $d|x,$ and if for all $x\in X$ we have $c|x$, then $c|d.$ There also exists a finite subset $Y\subseteq X$ such that $\gcd (Y)=\gcd(X).$
Proposition 6. Every subsemigroup of $\mathbb N$ is finitely generated.
Proof. Let $S$ be a subsemigroup of $\mathbb N$. Let $d=\gcd (S).$ Then there exists $Y\subseteq S$ such that $\gcd(Y)=d.$ Surely $\langle Y\rangle\subseteq\mathbb N.$ There exists $x\in\langle Y\rangle$ such that $$\langle Y\rangle\cap\{n\in\mathbb N\,|\,n\geq x\}=\{x+kd\,|\,k\geq 0\}.$$
Thus, beginning from $x$, all numbers divisible by $d$ are in $\langle Y\rangle.$ Therefore, in particular, all elements of $S$ greater than or equal $x$ are in $\langle Y\rangle.$ It follows that $S=\langle Y\cup (S\cap \{n\in\mathbb N\,|\,n<x\})\rangle.$ So $S$ is finitely generated. $\square$
QUESTION. From the above facts (which are hopefully true), I know what subsemigroups of $\mathbb N$ look like eventually. They become arithmetic progressions whose difference divides its elements. But can we describe their initial behavior in a usable way? For example, this is a subsemigroup:
$$\{3,5,7,8,9,\ldots\};$$
this is a subsemigroup:
$$\{3,5,8,9,\ldots\};$$
but this is not:
$$\{3,5,7,9,\ldots\}.$$
My general question is this: can we usefully characterize subsemigroups of $\mathbb N$ among subsets of $\mathbb N$?
Best Answer
You are looking at what is sometimes called the Frobenius problem. The two-generator case is already interesting: if $a,b$ are coprime then the semigroup they generate has every positive integer from $N=(a-1)(b-1)$ on, and exactly half of the integers between zero and $N-1$, inclusive; moreover, it contains $m$ in that range if and only if it doesn't contain $N-1-m$. These are all good exercises to prove, if this is new to you.
The $n=3$ case is much harder, bigger values of $n$ are harder still.