Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Uncountably infinitely many, obviously. Is this the answer you are after? –  Did Jan 6 '13 at 14:15
    
The answer is a particular case of my answer here. –  Asaf Karagila Jan 6 '13 at 14:25

2 Answers 2

up vote 2 down vote accepted

There are $2^{\aleph_0}$ many. As mentioned above, equivalence relation corresponds to partition of $\mathbb{N}$. For each $f \in 2^{\mathbb{N}}$, i.e. a function $f : \mathbb{N} \rightarrow \{0,1\}$. Define a partition, $P_f$, such that, $P_f$ has a subset of size $n$ if and only if $f(n) = 1$. Then if $f \neq g$, then $P_f \neq P_g$. Hence the number of equivalence relations on $\mathbb{N}$ is at least as many as $2^{\aleph_0}$. It can not be bigger because the power set $\mathcal{P}(\mathbb{N})$ has cardinality $2^{\aleph_0}$.


Explicitly, you can have construct $P_f$ as follows: If $f(i) = 1$, then put into $P_f$, the subset $(\sum_{k < i \ st \ f(k) = 1} k + 1, \sum_{k < i \ st \ f(k) = 1} k + 1 + i)$.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.