I have the following equivalence relation problem.

$Let \ R\subseteq 2^S*2^S = \{(A,B):|A\cap T|=|B \cap T|\}\ where\ S=\{0,1,2\} \ and \ T=\{1,2\} \ Show \ that \ R \ is \ a \ equivalence \ relation \ to \ 2^S \ and \ describe \ the \ equivalence \ classes\ $

I understand that in order to show that $R$ is an equivalence relation I need to show that is $R$ is symmetric, reflexive and transitive.

Though I have two questions.

  1. What the result of $2^S$ will be?
  2. What steps do I need to follow to find the equivalence classes of an equivalence relation?
  • $\begingroup$ I think you meant $\;2^s= P(S)=$ the set of all subsets of $\;S\;$, and then $\;R\subset 2^S\times 2^S\;$ . What you mean by (1) is beyond my understanding, and about (2): there are only $\;8\;$ elements in $\;2^S\;$ so it shouldn't be that hard to do the actual partition of $\;2^S\;$ by equivalence classes. For example, $\;[\emptyset]=\{\emptyset\,,\,\{2\}\}\;$ $\endgroup$ – Timbuc Feb 8 '15 at 13:34
  • $\begingroup$ I thought 2^S to be power. I guess I missed the symbolism of the power Set. 1 is now understood. About 2 I still have a hard time understanding how you found [0]={0,{2}} $\endgroup$ – Dimitri C Feb 8 '15 at 13:38
  • $\begingroup$ Nice, now try to separate all the elements in $\;2^S=P(S)\;$ in different equivalence classes. $\endgroup$ – Timbuc Feb 8 '15 at 13:40
  • $\begingroup$ How can I do that? $\endgroup$ – Dimitri C Feb 8 '15 at 13:46

I already gave you an example in the comment. For another one:

$$|\{1\}\cap T|=1\implies X\in\left[\,\{1\}\,\right]\iff |X\cap T|=1$$

so for example, we have in this case


Now you try other cases.

  • $\begingroup$ I think I got it. Will the answer(to my problem) be [0]={{e},{0}} [1]={{1},{2},{0,1},{0,2}} [2]={{1,2},{0,1,2}} ? $\endgroup$ – Dimitri C Feb 8 '15 at 13:55
  • $\begingroup$ Observe that $\;[1]=[2]\;$ so your last one cannot be right, and in fact observe that $$|\{0,1,2\}\cap T|=2\neq 1=|\{1,2\}\cap T|$$ $\endgroup$ – Timbuc Feb 8 '15 at 14:58
  • $\begingroup$ You are right. T is actually {1,2} and not {0,1} . $\endgroup$ – Dimitri C Feb 8 '15 at 15:02

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.