Equivalence Relation-each eq class is infinite and there are infinitely many eq classes. 
*

*Find an equivalence relation on $\mathbb{N}$ such that each eq class is infinite and there are infinitely many eq classes. 


My trying: $a\equiv b \iff a-b\in n\mathbb{N}$ as $n$ is natural number. In this each class is infinite but there are finite many eq classes. Can you help?
 A: Here's a fun trick.
Define an equivalence relation $\sim$ on $\mathbb{N} \times \mathbb{N}$ by letting $(a,b) \sim (c,d)$ if and only if $a=c$. Then the equivalence classes of $\sim$ are the sets of the form $E_n = \{ (n,k) \mid k \in \mathbb{N} \} \subseteq \mathbb{N} \times \mathbb{N}$, for (fixed) $n \in \mathbb{N}$.
Evidently there are infinitely many equivalence classes—one for each $n \in \mathbb{N}$—and each equivalence class $E_n$ is infinite.
Now transport this along your favourite bijection $f : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$.
Specifically, and define a new equivalence relation $\approx$ on $\mathbb{N}$ by $a \approx b$ if and only if $f^{-1}(a) \sim f^{-1}(b)$. You can then check that $\approx$ is an equivalence relation, and the equivalence classes of $\approx$ are the preimages under $f$ of the equivalence classes of $\sim$. Hence there are infinitely many of them, and they're all infinite!
A: Similar to previous answers, but easier to understand: two numbers are equivalent iff they end in the same number of $0$s. Obviously this satisfies all of the conditions for equivalence relations; furthermore, there are infinitely many classes each with infinitely many members.
A: You can take, say, $a\mathrel Rb$ if and only if the greatest power of $2$ that divides $a$ is equal to the greatest power of $2$ that divides $b$.
