Finding all non trivial congruence relations on (N, +)

Question

I want to find all congruence relations on ($\mathbb{N}, +$). Clearly, we have $\bigtriangledown_\mathbb{N} = \mathbb{N} $ x $ \mathbb{N} $ and $\bigtriangleup_\mathbb{N} = \{(x,x)| x \in \mathbb{N}\}$. How do I determine non-trivial ones? How can I prove that these, then, are all of them?

Answer 1

Assuming $0\in\Bbb N$, we can say that $\Bbb N$ is the free monoid generated by one element. (On the other hand, if you assume $0\notin\Bbb N$, then it's the free semigroup on one element.)

Its quotients are precisely all the monoids [semigroups] generated by one element.

Let $\def\th{\,\vartheta\,} \th$ be a congruence relation on $(\Bbb N,+)$.

1. Take the least $n>0$ such that $n\th 0$. If such $n$ exists, we will have $1+1+\dots+1=0$ in the quotient, so that's going to be a cyclic group of order $n$.
2. Otherwise - Take the least $n$ that is congruent to somebody else than itself, and take the least such somebody else, $m=n+d$.
   Then, in the quotient, we will have $n=n+d=n+2d=n+3d=\dots$, i.e. it's a cycle of $d$ elements over a tail of the first $n$ elements.
   

Can you explicitly write up the congruences?

See also monogenic semigroups.