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

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?

• What is your definition of "congruence relation"? – Greg Martin Mar 13 '17 at 21:05
• Does your definition of $\mathbb{N}$ include $0$? – benguin Mar 13 '17 at 21:11
• – arctic tern Mar 13 '17 at 21:14

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?

• 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$ ?? – Hofmusicus Mar 13 '17 at 22:32
• 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$. – Berci Mar 13 '17 at 22:37
• @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$ ? – thehardyreader May 5 '18 at 12:55
• 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$. – Berci May 5 '18 at 13:03