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?


(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

  • $\begingroup$ 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|$ $\endgroup$ – JMoravitz Dec 1 '16 at 23:55
  • $\begingroup$ Yes beginning to see it more clearly now $\endgroup$ – Freud Dec 1 '16 at 23:59

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


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


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.