# Equivalence relations, counting equivalence classes between sets

Let $S=\{1,2,3..,9\}$ and $T=\{1,2,3,4,5\}$ . Let $R$ be the relation on the power set of S ie P(S) defined by

For all elements X, Y in P(S), X$R$Y iff |X ∩ T| = |Y ∩ T|.

I wanted to confirm my answers. Because this is an equivalence relation (I proved it via showing reflexivity, symmetry and transitivity), I rewrote it another way as X$R$Y iff |X| = |Y| to simplify the following.

(a) how many equivalence classes are there?

6 or 10, leaning more towards 10 (as there are 10 possible sizes of elements in P(S))

(b) how many elements does [∅] have?

1

(c) how many elements does [T] have?

9 choose 5 or 5 choose 5, leaning more towards 9 choose 5

(d) how many elements does [{1,2}] have?

9 choose 2 or 5 choose 2, leaning more towards 9 choose 2

• Note that $X=\{1,2,6,7,8\}$ is related to $Y=\{3,4\}$ despite $|X|\neq |Y|$. What is important is that $|X\cap T|=2=|Y\cap T|$ – JMoravitz Dec 1 '16 at 23:55
• Yes beginning to see it more clearly now – Freud Dec 1 '16 at 23:59

## 3 Answers

(a) Note that each equivalence class has a $1\text{-}1$ mapping with the set $\{0,1,2,3,4,5\}$, via the mapping $f([A]) = \left| A\cup T\right|$. Thus, there is a total of 6 equivalence classes.

(b) A set $U$ belongs to $[\{\emptyset\}]$ if and only if $|U\cap T|=\emptyset$. That is, any subset of $\{6,7,8,9\}$ will do. There is a total of $2^4=16$ such sets.

(c) Using almost the same rationale as in (b), we see that There is a total of $2^4=16$ such sets, since the subsets are $T\cup U$, where $U\subseteq \{6,7,8,9\}.$

(d) As in (c), we select a subset of $\{6,7,8,9\}$, and take its union with some subset of $T$, of size $2$. So the answer is $16\cdot\binom{5}{2}=160$.

"XRRY iff |X| = |Y|" is wrong.

(a) there are 6 equivalence classes since $|X|\cap T\in\{0,\dots,5 \}$ for any set $X \in P(S)$ and every case does occur.

(b) All elements in $[\emptyset]$ either contain 6,7,8,9 or not. So there are $2^4=16$ many.

(c) 16 (see (b) for reasoning)

(d) $16\cdot\binom{5}{2} =160$

Indeed, this $\def\R{\mathscr R} \R$ is an equivalence relation on $P(S)$.
However, it is different from the one you replaced it with.

Hints:

(a) There are 6 equivalence classes, because $|X\cap T|$ can have 6 different values.
(b) $Y\R \emptyset\ \iff\ Y\cap T=\emptyset\ \iff\ Y\subseteq\{6,7,8,9\}$
(c) $Y\R T\ \iff\ Y\supseteq T$; in this case $Y$ can be written as any set $\subseteq\{6,7,8,9\}$ plus $T$.
(d) $Y\R\{1,2\}\ \iff\ |Y\cap T|=2$, so the number of such sets $Y$ is $\,\binom52\cdot 2^4$.