Number of equivalence relation on $A=\{1,2,...,11\}$ such that $|A\setminus R| = 2$.

37 Views Asked by At

I am still trying to understand the question, I know that if a relation is reflexive (and equivalence relation is surely reflexive), then for every $a\in A$ , $(a,a)\in R$. But that means every equivalence relation on $A$ has atleast $11$ elements, which makes $|A \setminus R=0|$, because the cardinality of $R$ is surely $11$ or more.
The final answer was $2^{10}-1$, so seems like I have some big misunderstanding that I don't understand where it comes from, I would really appreciate any explanation.
Thanks in advance.

1

There are 1 best solutions below

8
On BEST ANSWER

The notation $A/R$ represents the set of equivalence classes (with respect to $R$). So, the question is: how many equivalence relations can you define on $A$ such that there are exactly two equivalence classes? And the answer is: it's half the number of subsets $B$ of $A$ such that neither $B$ nor $A\setminus B$ is empty, because, for any such set $B$, you can define the equivalence relation$$a_1\mathrel Ra_2\iff a_1,a_2\in B\text{ or }a_1,a_2\notin B$$and the equivalence classes of $R$ and $B$ and $A\setminus B$; besides, $B$ and $A\setminus B$ induce the same equivalence relation. There are $2^{11}-2$ such sets, and therefore the answer is $2^{10}-1$.