How many equivalence relations on a 4 element set with a case

390 Views Asked by At

How many equivalence relations are there on the set $\ A=\{ x,y,z,w\} $ such that $xRw$

At first i though the answer would be $Bell_4 = 15$ but I don't think this accounts for the "such that $xRw$. My current approach is to list out the 15 partitions of $A$ and count the number of sets where $X$ and $W$ are in the same subset.

Is this the correct approach to this problem?

1

There are 1 best solutions below

0
On BEST ANSWER

You are correct. The equivalence relations such that $xRw$ is strictly less than $Bell_4 = 15$.

Let $X$ be the set of the partition of $A$ containing $x$ and $w$ and consider three cases: $|X|=2$, $|X|=3$, and $|X|=4$.

If $|X|=2$ then we can partition the remaining part in $2$ ways.

If $|X|=3$ then remaining one-element set can be chosen in $2$ ways.

If $|X|=4$ then $X=A$, that is just $1$ case.

Hence the total number is $2+2+1=5$ which is, by the way, equal to $Bell_3$ (see user247327's comment).