0
$\begingroup$

(Question too long to post as title) The question is, Let S = {1,2,3,4,5,6,7,8,9} and let T = {2,4,6,8}. Let R be the relation on P(S) defined by for all X, Y ∈ P (S), (X, Y ) ∈ R if and only if |X − T| = |Y − T| and i have to find the number of equivalence classes. I had to initially prove it was an equivalence relation which i dont think i had trouble with but i'm struggling to understand how to approach solving this? I looked up what an equivalence class is again and it makes sense when it was such a simple example like for instance when a set of the relation was given to me and all i had to do was check for each x in the original set which other x did it have a relation with and then find the distinct relations. However, i am struggling to understand how to apply it here to such a larger scale and more complex problem.

In this case two elements or subsets of S in P(S) are related if the elements in X and not T give a cardinality equal to the elements in Y and not T? is this the correct understanding? Then to find the number of equivalence classes i have to do what? I dont really get how to start the process any help is appreciated thank you!

Could someone perhaps explain what an equivalence class would mean in this case?

$\endgroup$
1
$\begingroup$

Hint: for any subset $X, |X-T|$ is the number of odd elements of $X$. How many choices are there among the subsets of $S$ for the number of odd elements?

$\endgroup$
  • $\begingroup$ Okay so there are 5 different choices since there are 5 odd numbers $\endgroup$ – ssal Apr 4 at 5:08
  • 1
    $\begingroup$ True there are $5$ odd numbers, but there are $6$ choices because you could have none. $\endgroup$ – Ross Millikan Apr 4 at 5:09
  • $\begingroup$ Wait thats it? I am so confused that makes sense but could you explain how that is an equivalence class? Oh wait is each equivalence class would be like an equivalence class with only 1 odd number another with only 2 etc until 5 and then like you said a class with none. In this case the types of odd numbers is not important like the amount of odd numbers is? Why $\endgroup$ – ssal Apr 4 at 5:11
  • 1
    $\begingroup$ That is right because of the definition in terms of the size of the set. You segregate all the elements of $P(S)$ by the number of odd elements, which gives us six piles. Once you see that, the proof that it is an equivalence relation and each pile is an equivalence class is easy. $\endgroup$ – Ross Millikan Apr 4 at 5:15
  • 1
    $\begingroup$ $\{1,2,3,4\}$ has two odd elements, so it is in the class of subsets with two odd elements. Any other subset with exactly two odd elements is related to it. You choose any two odd numbers and any combination of even numbers to make one. There are ${5 \choose 2}=10$ choices for the pair of odd numbers and $2^4$ choices for the even numbers, so $160$ subsets in the class of two odd numbers. $\endgroup$ – Ross Millikan Apr 4 at 5:47

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.