[Math] Equivalence relation on $\mathbb{N}$ with infinitely many equivalence classes

Question

Does there exist an equivalence relation, defined on $\mathbb{N}$, with infinitely many equivalence classes, all of which contain infinitely many elements?

I see no reason for such a relation not to exist, but I'm having trouble finding an example.

Answer 1

Yes. First note that $\lvert\mathbb N\rvert=\lvert\mathbb N\rvert^2$ so it would be strange if there weren't.

For instance let $\sim$ be the equivalence relation defined by $p^n\sim p^k$ for all $p$ prime and $n,k\ge 1$, and let all numbers which aren't of the form $p^n$ be equivalent.

So $$1\sim 6\sim 10\sim 12\sim 14\sim 15\sim\cdots$$ $$2\sim 4\sim 8\sim 16\sim\cdots$$ $$3\sim 9\sim 27\sim\cdots$$

and so on.

Edit: To elaborate on my first point. Let $f:\mathbb N^2\to\mathbb N$ be any bijection. Then set $f(n,k)\sim f(n,l)$ for all $n,k,l$ to get an equivalence relation as wanted.