# $x,y$ related if and only if $x\cap\{{1,3,5\}}=y\cap\{{1,3,5\}}$.

Let A be the power set of $\{1,2,3,4,5\}$, let $z= \{1,2,3\}$, and let $(x,y) \in R$ if and only if

$$x \cap \{1,3,5\} = y \cap \{1,3,5\}$$

I'm supposed to find the equivalence class, number of equivalence class and determine which equivalence class the element $z$ belongs to.

This is not homework. It's a practice textbook question, and I have no idea how to even start on this problem. Mainly, I don't understand the relation.

-
Well, I'll explain the relation. Taken an element $x$ of $A$ --- that is, $x$ is a subset of $\{{1,2,3,4,5\}}$. Find the intersection of $x$ with $\{{1,3,5\}}$. Take another element $y$ of $A$. Find the intersection of $y$ with $\{{1,3,5\}}$. Are your two answers the same? If they are, $x$ and $y$ are related; if not, not. –  Gerry Myerson Nov 6 '12 at 1:54
I don't understand the part "find the intersection of x with {1,3,5} " –  Aaron Nov 6 '12 at 2:08
Sorry, you don't understand how to find the intersection of a subset of $\{{1,2,3,4,5\}}$ with $\{{1,3,5\}}$? It just means, find all the elements of ther subset that are also elements of $\{{1,3,5\}}$. E.g., if $x=\{{1,2,3\}}$ then the intersection is $\{{1,3\}}$ since those are the things that are in both $\{{1,2,3\}}$ and $\{{1,3,5\}}$. –  Gerry Myerson Nov 6 '12 at 4:53

Since I have the time, here is a pretty thorough explanation of how you might attack the problem by brute force, followed by some pointers on how the amount of brute force could be reduced.

Since $\{1,2,3,4,5\}$ has $5$ elements, it has $2^5=32$ subsets. That’s a small enough number that if you can’t find a nicer approach, you can simply list them all, find their intersections with $\{1,3,5\}$, and use that to sort them into equivalence classes.

$$\begin{array}{c} \text{Set}&\text{Intersection with }\{1,3,5\}\\ \hline \varnothing&\varnothing\\ \{1\}&\{1\}\\ \{2\}&\varnothing\\ \{3\}&\{3\}\\ \{4\}&\varnothing\\ \{5\}&\{5\}\\ \{1,2\}&\{1\}\\ \{1,3\}&\{1,3\}\\ \{1,4\}&\{1\}\\ \color{red}{\{1,5\}}&\{1,5\}\\ \{2,3\}&\{3\}\\ \{2,4\}&\varnothing\\ \{2,5\}&\{5\}\\ \{3,4\}&\{3\}\\ \{3,5\}&\{3,5\}\\ \{4,5\}&\{5\}\\ \{1,2,3\}&\{1,3\}\\ \{1,2,4\}&\{1\}\\ \color{red}{\{1,2,5\}}&\{1,5\}\\ \{1,3,4\}&\{1,3\}\\ \{1,3,5\}&\{1,3,5\}\\ \color{red}{\{1,4,5\}}&\{1,5\}\\ \{2,3,4\}&\{3\}\\ \{2,3,5\}&\{3,5\}\\ \{2,4,5\}&\{5\}\\ \{3,4,5\}&\{3,5\}\\ \{1,2,3,4\}&\{1,3\}\\ \{1,2,3,5\}&\{1,3,5\}\\ \color{red}{\{1,2,4,5\}}&\{1,5\}\\ \{1,3,4,5\}&\{1,3,5\}\\ \{2,3,4,5\}&\{3,5\}\\ \{1,2,3,4,5\}&\{1,3,5\} \end{array}$$

As an example, the sets shown in are the sets that have $\{1,5\}$ as their intersection with $\{1,3,5\}$, so they form one equivalence class of the relation.

Very likely you would realize part of the way through that it would be simpler to start with the possible intersections with $\{1,3,5\}$ and systematically list the subsets of $\{1,2,3,4,5\}$ having each possible intersection, like this:

$$\begin{array}{c|l} \text{Intersection with }\{1,3,5\}&\text{Subsets having that intersection}\\ \hline \varnothing&\varnothing,\{2\},\{4\},\{2,4\}\\ \{1\}&\{1\},\{1,2\},\{1,4\},\{1,2,4\}\\ \{3\}&\{3\},\{2,3\},\{3,4\},\{2,3,4\}\\ \{5\}&\{5\},\{2,5\},\{4,5\},\{2,4,5\}\\ \{1,3\}&\{1,3\},\{1,2,3\},\{1,3,4\},\{1,2,3,4\}\\ \{1,5\}&\color{red}{\{1,5\},\{1,2,5\},\{1,4,5\},\{1,2,4,5\}}\\ \{3,5\}&\{3,5\},\{2,3,5\},\{3,4,5\},\{2,3,4,5\}\\ \{1,3,5\}&\{1,3,5\},\{1,2,3,5\},\{1,3,4,5\},\{1,2,3,4,5\} \end{array}$$

In constructing this table you should notice that each row can be obtained from the top row in a very simple way. For example, the equivalence class of $\{1,5\}$, again in red, is obtained by taking the union of $\{1,5\}$ with each of the sets having empty intersection with $\{1,3,5\}$. You should think about why this must be the case: if $A\cap\{1,3,5\}=\{1,5\}$, then it must be possible to split $A$ into two disjoint pieces, $\{1,5\}$ and the set $A'$ of elements of $A$ that are not in $\{1,5\}$. This $A'$ is disjoint from $\{1,3,5\}$, so it must be one of the four sets having intersection $\varnothing$ with $\{1,3,5\}$. Thus, the red line is just

$$\{1,5\}\cup\varnothing,~\{1,5\}\cup\{2\},~\{1,5\}\cup\{4\},~\{1,5\}\cup\{2,4\}\;,$$

and each of the other lines below the first is obtained similarly.

Now recall that $x\sim y$ if and only if $x\cap\{1,3,5\}=y\cap\{1,3,5\}$. The four sets shown in red all have the same intersection with $\{1,3,5\}$, so they are all related: $\{1,5\}\sim\{1,4,5\}$, $\{1,5\}\sim\{1,5\}$, $\{1,2,4,5\}\sim\{1,4,5\}$, etc. The collection $$\Big\{\{1,5\},\{1,2,5\},\{1,4,5\},\{1,2,4,5\}\Big\}$$ is one equivalence class of the relation $\sim$; all of them are shown in the table above. As you can see, there are eight of them, each with four elements.

Having done everything else, I’ll leave it to you to identify the equivalence class to which $\{1,2,3\}$ belongs.

-
Thank you so much, I'll read this through and give you feedback. –  Aaron Nov 7 '12 at 3:24
@Aaron: You’re welcome. –  Brian M. Scott Nov 7 '12 at 3:28
Thank you genius, how did you become one? Or a better question, How can I do math better? LOL –  Aaron Nov 7 '12 at 3:33
@Aaron: :-) Seriously, two things that can help are (1) paying careful attention to definitions and trying to illuminate them with examples of your own, and (2) being willing to do some grubby pencil-and-paper work, like my first table in the answer, when you attack a problem, to try to get an idea of what’s going; you don’t always have to have a clever idea, or see your way to the solution immediately. –  Brian M. Scott Nov 7 '12 at 3:37
Thank you again, this explanation just made me understand a whole section and probably no one else would have explained it like you did. Much respect –  Aaron Nov 7 '12 at 3:41

Just to help a bit. The set $A$, is the set of all subsets of $\Omega = \{1,2,3,4,5\}$. So for example as an element you would have $\{1,2\} \in A$ or the empty set $\emptyset\in A$.

Now you say that two such elements $X,Y\in A$ are equivalent (maybe written $X\sim Y$) if (and only if) $X\cap \{1,3,5\} = Y\cap \{1,3,5\}$.

So you would for example have that $\{1,2,3\} \sim \{1,3,4\}$ because $$\{1,2,3\}\cap \{1,3,5\} = \{1,3\} \\ \{1,3,4\}\cap \{1,3,5\} = \{1,3\}.$$ That would mean that the elements $\{1,2,3\}\in A$ and $\{1,3,4\}$ are in the same equivalence class.

So one approach to this problem that might be helpful for you would be to

1. Write down all the elements of $A$
2. Write down what the intersection of each element in $A$ with $\{1,3,5\}$ is.
3. The elements that have the same intersection are in the same equivalence class.

(There are "rules" that could help you do this, but I think that the best thing would be to just write it all down. Maybe you see some things about the number of equivalence classes and such...)

-
I'm stuck at your #2 T_T –  Aaron Nov 6 '12 at 4:05
@Aaron: So for example if an element if $\{1,2,4,5\}$, then you write down that the intersection of that element with $\{1,3,5\}$ is $\{1,5\}$. If you do this for each element, then hopefully you should be able to see which of the elements are equivalent. –  Thomas Nov 6 '12 at 4:09

X,Y are elements of the power set A.

the equivalent relation should be X~X $\cup${2}~X$\cup${4}~X $\cup${2,4}.