how to comput the number of equivalence relation in a finite set?

Question

Example: Let $A =\{1,2,3\}$ and $S =\{(1,1)(2,2)(3,3)(1,2)(1,3)(3,1)(1,3)(2,3)(3,2)\}$ $S$ is an equivalence relation on $A$, and it has $9$ order pairs in it. Which is the square of element in $A(3^2=9)$

Let $A=\{1,2,3,4\}$, and $S=\{(1,1)(2,2)(3,3)(1,2)(1,3)(3,1)(1,3)(2,3)(3,2)(1,4)(4,1)(2,4)(4,2)(3,4)(4,3)(4,4)\}$ $S$ is an equivalence relation on $A$, and it has $4^2=16$ order pairs in it.

By this pattern, if $A=\{1,2,3,4,5,6,7,8,9,10\}$ then there should be $10^2$ equivalence relations in $S$.

Question: If $A$ is a set of natural numbers $\{1,2,3.....,n\}$ then how many equivalence relation $S$ have on $A$?

By the above example I know there are going to be $n^2$ equivalence relations, but I just don’t know how to prove it. I was wondering if anyone can give me a hint.

Answer 1

Your examples illustrate the largest possible equivalence relation on sets with $3$ and $4$ elements. In those equivalence relations everything is related to everything else so every ordered pair is in the relation. When $A$ has $n$ elements there are indeed $n^2$ ordered pairs: $n$ choices for the first element and, independently, $n$ for the second.

The title of your question asks for the number of equivalence relations, not the number of pairs in this particular equivalence relation. I don't think that's what you are asking, but if you are, @MichealRozenberg 's answer tells you how to start thinking about it.

Answer 2

The hint:

Think about equivalence classes.

Answer 3

Based on your comment, what you are really asking is the side of the Cartesian product $|A \times A|$ given the size of $|A|$. Note that each element of $A$ can be the first element. For each one, there are $|A|$ ordered pairs because each one can have any element as the second in the pair. There are therefore $|A|^2$ elements in $A \times A$

Answer 4

Equivalence relations on a set correspond one to one with partitions of the set.

The number of partitions of a set with $n$ elements is the so-called Bell number.

Answer 5

The number of equivalence relations on a set of $n$ elements is the same as the number of partitions on a set of $n$ elements which is given by Bell numbers $B_n$. You can compute them recursively using the recurrence $$ B_{n+1}=\sum_{k=0}^n \binom{n}{k}B_k;\quad B_0=B_1=1. $$ The number of relations on a set $A$ with $n$ elements is $2^{n^2}$ as a relation is a subset of the cartesian product $A\times A$.