Equivalence relations on natural numbers How many equivalence relations are there on $\mathbb{N}$, where $\mathbb{N}$ is the set of natural numbers? How can one compute it?

An equivalence relation on any set partitions that set. 
So we can approach your question by asking, equivalently: How many ways are there to partition $\mathbb{N}$?


*

*A partition of $X$ with is a set P of nonempty subsets of X, such that every element of X is an element of a single element of P. Each element of P is a cell of the partition. Moreover, the elements of P are pairwise disjoint and their union is X.

*$|\mathbb{N}| = \aleph_0$. There are uncountably many possible distinct partitions of $\mathbb{N}: 2^{\aleph_0}$ distinct partitions. (See this post for a nicely detailed proof of this - not just a sketch of a proof.)

*Since there is a natural bijection from the set of all possible equivalence 
relations on a set $\mathbb{N}$ and the set of all partitions of $\mathbb{N}$, there are   $2^{\aleph_0}$ equivalence relations on $\mathbb{N}$.



*

*For counting the number of partitions on a finite sets, see Counting Partitions.

*For an elaboration on the relationship between an equivalence relation on a set and the partition of the set induced by that relation, vice versa, see this previous post
