Solution check. How many relations of equivalence $R$ are there in $\Bbb N$ that verify silmultaneously the following properties.

Question

I'm revising some old psets while preparing an exam and going through some things that I left unverified.

How many relations of equivalence $R$ are there in $\Bbb N$ that verify silmultaneously the following properties?

• If two elements end in the same digit, they are related
• {(1,2),(101,25),(4,4),(234,20166),(22,7),(153,158),(8,100),(17,27)}$⊆R$
• (1,14),(32,8),(19,10),(309,666) $\notin R$

This would give me the following equivalence classes if I'm not wrong:

$[1] = [2] = [5] = [7]$

$[0] = [3] = [8]$

$[4] = [6]$

$[9]$

The thing is that I'm not understanding how to use the third property, so that makes me think I got the previous wrong. Can you help me out?

Answer 1

This answer starts where you stopped. We focus on the $4$ sets $[1],[0],[4],[9]$. Any equivalence relation with the mentioned properties will induce a partition such that each of its elements is a non-empty union of these sets.

We have $[1]\cup[0]\cup[4]\cup[9]=\mathbb N$, but what can be said about mutually disjointness? On this the third property applies the following information:

• $[1]\cap[4]=\varnothing$
• $[1]\cap[0]=\varnothing$
• $[0]\cap[9]=\varnothing$
• $[4]\cap[9]=\varnothing$

Note that $[1]\cap[9]\neq\varnothing$ or equivalently $[1]=[9]$ is not excluded.

Also note that $[0]\cap[4]\neq\varnothing$ or equivalently $[0]=[4]$ is not excluded.

This makes $4$ partitions possible:

• $\{[1],[0],[4],[9]\}$
• $\{[1],[0],[4]\}$ where $[1]=[9]$
• $\{[1],[0],[9]\}$ where $[0]=[4]$
• $\{[1],[0]\}$ where $[0]=[4]$ and $[1]=[9]$

The answer on the original question (number of equivalences) is $4$.