16
$\begingroup$

this was a question listed on my last "proofs and conjectures" midterm. It is similar to my previous post however this asks a different question which is throwing me off.

What is the number of equivalence relations on the set $\{1, 2, 3, 4\}\,$?

Do I simply list all equivalence relations and then count them? This seems rather tedious.

Is there a general rule I can use as a shortcut to determine the number?

I was wondering if anybody could help guide me or list the solution, as I'm expected to know the material for the final.

Note: standard proof procedure is required in ALL my solutions for this course so I may come back and ask to clarify if a particular solution isn't specific enough.

$\endgroup$
2
  • $\begingroup$ the answer is fifteen. $\endgroup$
    – Max
    Mar 7, 2014 at 20:31
  • 4
    $\begingroup$ Instead of asking 5 or more questions on the same topic, try asking one question about the part you don't understand, understand the answers provided, and solve the other problems for yourself. Copy-pasting each question here without any own effort will not get you through your exams. $\endgroup$
    – TMM
    Mar 7, 2014 at 20:50

6 Answers 6

27
$\begingroup$

This sort of counting argument can be quite tricky, or at least inelegant, especially for large sets. Here's one approach:

There's a bijection between equivalence relations on $S$ and the number of partitions on that set. Since $\{1,2,3,4\}$ has 4 elements, we just need to know how many partitions there are of 4.

There are five integer partitions of 4:

  • $4$,
  • $3+1$,
  • $2+2$,
  • $2+1+1$,
  • $1+1+1+1$

So we just need to calculate the number of ways of placing the four elements of our set into these sized bins.

4

There is just one way to put four elements into a bin of size 4. This represents the situation where there is just one equivalence class (containing everything), so that the equivalence relation is the total relationship: everything is related to everything.

3+1

There are four ways to assign the four elements into one bin of size 3 and one of size 1. The corresponding equivalence relationships are those where one element is related only to itself, and the others are all related to each other. There are clearly 4 ways to choose that distinguished element.

2+2

There are $\pmatrix{4\\2}/2=6/2=3$ ways. The equivalence relations we are looking at here are those where two of the elements are related to each other, and the other two are related to themselves. So, start by picking an element, say 1. Then there are three things that 1 could be related to. Once that element has been chosen, the equivalence relation is completely determined.

2+1+1

There are $\pmatrix{4\\2}=6$ ways.

1+1+1+1

Just one way. This is the identity equivalence relationship.

Thus, there are, in total 1+4+3+6+1=15 partitions on $\{1,2,3,4\}$, and thus 15 equivalence relations.

$\endgroup$
4
  • $\begingroup$ thanks for your explicit explanation. i can follow your guidelines but i stuck on "There's a bijection between equivalence relations on S and the number of partitions on that set. " i somehow dont get that bijection. the number of equivalence relations remains a mystery to me. i get that an equivalence relation forms several equivalence groups and those are a partition of A. any how i dont see how to map a bijection from the number of partitions to equivalence relations. would be very thankful for some additional explanation on that $\endgroup$
    – Mainviel
    Oct 29, 2016 at 11:27
  • $\begingroup$ Each partition $P$ defines an equivalence relationship $R$ by saying $$xRy \leftrightarrow \exists p \in P \, (x\in p) \& (y \in p).$$ In this case, the elements of the partition are precisely the equivalence classes of $R$. $\endgroup$
    – Unwisdom
    Dec 4, 2016 at 4:37
  • $\begingroup$ "Each partition $P$..." and $p \in P$: what is $p \in P$ if $P$ is the partition? If $p$ is an element in the partition then what is $x \in p$? $\endgroup$ Jan 21, 2021 at 7:51
  • $\begingroup$ A partition $P$ of $X$ is a collection of pairwise-disjoint non-empty subsets of $X$ whose union is the whole of $X$. Saying $p\in P$ means that $p$ is one of those subsets. Saying $x\in p$ means that $p$ is the (unique) element of the partition containing $x$. $\endgroup$
    – Unwisdom
    Jan 21, 2021 at 22:52
7
$\begingroup$

Total number of equivalence relations on $\{1,2,3,4\}$=Number of partitions of the set $\{1,2,3,4\}$ into equivalence classes(nonempty subsets)

Number of possible partitions of a set $A$=Bell's number, $B(m)$=$\sum_{n=1}^m S(m,n)$,

where $S(m,n)=\frac{1}{n!}\sum_{k=0}^n(-1)^k.{^n}C_{k}(n-k)^m$ are the Stirling numbers of the second kind.

$$ S(4,1)=\frac{1}{1!}\sum_{k=0}^1(-1)^k.{^1}C_{k}(1-k)^4={^1}C_{0}.1^4-{^1}C_{1}.0=1\\S(4,2)=\frac{1}{2!}\sum_{k=0}^2(-1)^k.{^2}C_{k}(2-k)^4=\frac{{^2}C_{0}.2^4-{^2}C_{1}.1^4+{^2}C_{2}.0}{2}=\frac{14}{2}=7\\ S(4,3)=\frac{1}{3!}\sum_{k=0}^{3}(-1)^k.{^3}C_k(3-k)^4=\frac{{^3}C_0.3^4-{^3}C_1.2^4+{^3}C_2.1^4-{^3}C_3.0}{6}=\frac{81-3(16)+3}{6}=\frac{36}{6}=6\\ S(4,4)=1 $$

Number of possible partitions of the set $\{1,2,3,4\}$,i.e., number of equivalence relations of the set, $$ B(4)=\sum_{n=1}^4S(4,n)=S(4,1)+S(4,2)+S(4,3)+S(4,4)=1+7+6+1=15 $$

$\endgroup$
1
  • $\begingroup$ yep this is practical and we also had the Stirling Numbers in our Lecture. But i don't understand why there is a bijection between Strirling numbers 2 and Aquivalence relations. $\endgroup$ Feb 10, 2019 at 23:44
4
$\begingroup$

Here's another method: Count the equivalent relations by number of equivalence classes and recurse through the set size (we start with set size 1 and ignore the empty set equivalence relation).

Let's denote with $a_{n,k}$ the number of equivalence classes of an $n$-element set which have $k$ equivalence classes. To avoid special cases in the formulas, let's assume $a_{0,k}=a_{n,0}=0$.

A set of one element obviously has only one equivalence relation, with one equivalence class. That is, $a_{1,1}=1$.

The equivalence relations with $k$ equivalence classes of a set with $n$ elements is obtained by combining the following two disjoint sets:

  • All equivalence relations obtained by adding the $n$-th element as separate equivalence class to the relations with $k-1$ equivalence classes in the remaining $n-1$ elements. For example, from $\{\{1,2\},\{3\}$ you get $\{\{1,2\},\{3\},\{4\}\}$. Obviously we get one $(n,k)$-relation from each $(n-1,k-1)$ relation.

  • All equivalence relations by adjoining the $n$-th element to one of the equivalence classes of a relation with $k$ equivalence classes in the remaining $n-1$ elements. For example, from $\{\{1\},\{2,\},\{3\}\}$ you get $\{\{1,4\},\{2\},\{3\}\}$, $\{\{1\},\{2,4\},\{3\}\}$ and $\{\{1\},\{2\},\{3,4\}\}$. Obviously we get $k$ $(n,k)$ relations from each $/n-1,k)$-relation

Thus $a_{n,k} = a_{n-1,k-1} + k a_{n-1,k}$.

So let's do the recursion:

  • $n=2$:

    • $a_{2,1} = a_{1,0} + 1 a_{1,1} = 1$. Indeed, we can easily see that $a_{n,1}$ is always $1$ for all $n$. Therefore from now on this calculation will be omitted.

    • $a_{2,2} = a_{1,1} + 2 a_{1,2} = 1$. Again, we can easily see that $a_{n,n}$ is always $1$. Therefore from now on this calculation will be omitted, too.

    So there are $1+1=2$ equivalence relations for $n=2$.

  • $n=3$:

    • $a_{3,2} = a_{2,1} + 2 a_{1,2} = 3$

    So there are $1+3+1=5$ equivalence relations for $n=3$.

  • $n=4$:

    • $a_{4,2} = a_{3,1} + 2 a_{3,2} = 7$

    • $a_{4,3} = a_{3,2} + 3 a_{3,3} = 6$

    So there are $1+7+6+1=15$ equivalence relations for $n=4$.

This can be put into a nice schema which has some resemblance of Pascal's triangle:

n\k  1   2   3   4   5   6
1    1                       ->   1
2    1   1                   ->   2
3    1   3   1               ->   5
4    1   7   6   1           ->  15
5    1  15  25  10   1       ->  52
6    1  31  90  65  15   1   -> 203

Each number is the column number times the number above it plus the number left from that.

$\endgroup$
2
$\begingroup$

This type of question can be easily solved by bell's triangle.

1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203

Here in the set we have 6 elements so we go to line number 6 and last element is answer i.e, 203.

$\endgroup$
2
  • 2
    $\begingroup$ Hi Ritik Jain RJ. Welcome to MSE! A good answer to a mathematics question not only provides a direct answer to the askers question, but also explains how/why your solution works. Could you edit your question to include more about Bell's triangle and why it's useful for answering the OP's question? I think doing so would make your answer a lot more valuable. Also the OP's set has $4$ elements so the answer should be $15$ $\endgroup$
    – eepperly16
    Jan 6, 2018 at 6:56
  • $\begingroup$ Please, give more details in order to explain why your answer solve the problem. $\endgroup$ Jan 6, 2018 at 7:03
1
$\begingroup$

Number of equivalence relations or number of partitions is given by $$S(n,k)\;=\;S(n-1,k-1)+kS(n-1,k),$$ where $n$ is the number of elements in a set and $k$ is the number of elements in a subset of partition, with initial condition $S(n,1)=S(n,n)=1.$

e.g., $A=\{1,2,3,4\}$ (here $n=4$):

$k=4:\quad \quad S(4,4)=1.$

for $k=3:$

$$S(4,3)=S(3,2)+3*S(3,3) =S(2,1)+2*S(2,2)+3*S(3,3) =1+2+3=6.$$

for $k=2:$

$$S(4,2)=S(3,1)+2*S(3,2) =S(3,1)+2*[S(2,2)+2*S(2,2)] =1+2*[1+2*1] =7.$$

for $k=1:\quad \quad S(4,1)=1.$

So, the total number of equivalence relations $$= S(4,4)+S(4,3)+S(4,2)+S(4,1)=1+6+7+1=15.$$

$\endgroup$
0
$\begingroup$

Hint:

  • How many equivalence relations split the set into one equivalence class?

  • How many equivalence relations split the set into two equivalence classes?

  • How many equivalence relations split the set into three equivalence classes?

  • How many equivalence relations split the set into four equivalence classes?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .