4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Are you talking about the cardinality of the cartesian product $A \times A$ ? $\endgroup$ – Sunyam Oct 24 '17 at 15:09
  • $\begingroup$ @confused yes, my wording was off. I just didn’t know how to explain it in the right way. $\endgroup$ – Qwert Oct 24 '17 at 15:12
  • $\begingroup$ Try prooving it by induction. $\endgroup$ – Sunyam Oct 24 '17 at 15:14
  • $\begingroup$ I think you may have a typo, I think one of the $(1,3)$ in each set should probably be $(2,1)$. You have $(1,3)$ listed twice in each set, but you don't have $(2,1)$ listed in either (so it can't be an equivalence relation since its not closed without $(2,1)$). $\endgroup$ – AJMansfield Oct 24 '17 at 21:49
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, my question was to count the largest number of equivalence relations that in a set where everything is related to everything. Sorry about the wording, I just started learning relations and I didn’t know what’s the right words to use. $\endgroup$ – Qwert Oct 24 '17 at 15:29
  • $\begingroup$ You are trying to count the number of elements in the largest equivalence relation. You are not trying to count the number of relations. Do you see the distinction? It is important to state the question accurately. $\endgroup$ – Ross Millikan Oct 24 '17 at 15:39
  • $\begingroup$ @RossMillikan if the question was “count all the equivalence relations on A” would it still be n^2 equivalence relations? Or it’s something else? $\endgroup$ – Qwert Oct 24 '17 at 16:50
  • 1
    $\begingroup$ @Qwert: That $S$ is a single equivalence relation. $T=\{(1,1),(2,2)\}$ is another equivalence relation. It turns out that $S$ and $T$ are the only possible equivalence relations on $\{1,2\}$, so for $n=2$ the answer is $2$. $\endgroup$ – Henning Makholm Oct 24 '17 at 17:19
  • 2
    $\begingroup$ $\{(1,1)\}$ isn't an equivalence relation on $\{1,2\}$ because it's not reflexive: $2$ isn't equivalent to itself in this relation. $\endgroup$ – Ethan Bolker Oct 24 '17 at 17:56
6
$\begingroup$

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$.

$\endgroup$
4
$\begingroup$

The hint:

Think about equivalence classes.

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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