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?


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.

  • 1
    $\begingroup$ Yep, $0 \in \mathbb{N}$. So I guess I should arrive at sth. like this: let $n, d \in \mathbb{N}$. Then we have that $m$ ~ $l$ $\Leftrightarrow$ 1.case) $m = l$ or 2.case) $\exists e < d \exists i,j \in \mathbb{N} \colon n+di + e = m \wedge n + dj + e = l$ ?? $\endgroup$ – Hofmusicus Mar 13 '17 at 22:32
  • 1
    $\begingroup$ Yes, this formulation seems right.. In case 2., with the $n,d,m$ as introduced there, we will have $n+di\,\vartheta\,n$ in the quotient, so $n+di+e \,\vartheta\, n+e$ if $e<d$. Same applies to the other one, $n+dj+e\,\vartheta\,n+e$. $\endgroup$ – Berci Mar 13 '17 at 22:37
  • $\begingroup$ @Berci I know you wrote this answer over a year ago but I have a similar problem right know. Do you really mean $=$ and not $\theta$ in the expressions $1+1+1+\ldots +1 =0$ and $n=n+d=\ldots$ ? $\endgroup$ – thehardyreader May 5 '18 at 12:55
  • 1
    $\begingroup$ What's $\vartheta$ in a structure $A$ is strict equality in $A/\vartheta$. That's what quotient structure is. And that's why cosets make a good representation: if $a\, \vartheta\, b$ in $A$, then their equivalence classes are equal: $[a] _\vartheta =[b]_\vartheta$. $\endgroup$ – Berci May 5 '18 at 13:03
  • $\begingroup$ ah, thank you very much - so the expressions left and right of the equality represent the equivalence classes. $\endgroup$ – thehardyreader May 5 '18 at 13:18

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.