# Outrageously hard equivalence relations

• Mar 19th 2009, 06:04 PM
zhupolongjoe
Outrageously hard equivalence relations
Verify it is equiv. rel.

For the set X={m,n,p,q,r,s}, let R be the relation on P(X) (power set of X) given by A R B iff A and B have the same number of elements.
Now, list all elements in {m}/R; in{m,n,p,q,r}/R. How many elements are in X/R? How many in P(X)/R?

I know I need to show it is symmetric, transitive, and reflexive. I know how to this when we have like equations and things, but this one is confusing for me. Please help. Thank you.
• Mar 20th 2009, 04:02 AM
Equivalence Classes and Quotient Sets
Hello zhupolongjoe
Quote:

Originally Posted by zhupolongjoe
Verify it is equiv. rel.

For the set X={m,n,p,q,r,s}, let R be the relation on P(X) (power set of X) given by A R B iff A and B have the same number of elements.
Now, list all elements in {m}/R; in{m,n,p,q,r}/R. How many elements are in X/R? How many in P(X)/R?

I know I need to show it is symmetric, transitive, and reflexive. I know how to this when we have like equations and things, but this one is confusing for me. Please help. Thank you.

As you have written the question, some of it doesn't make sense. I'll explain why, but it will take a little time, so stay with me.

$P(X)$, the power set of $X$, is the set of all the subsets of $X$. So:

$P(X) = \{\oslash, \{m\}, \{n\}, \dots, \{m,n\}, \{m, p\}, \dots, \{m,n,p,q,r,s\}\}$

Look carefully at the words above in italics: $P(X)$ is a set of ... subsets ...; so the elements of $P(X)$ are themselves sets - and I have listed a few of them above.

Now $R$ is a relation on $P(X)$ (not a relation on $X$) - in other words $R$ is a relation between two subsets of $X$, which is: subset $A$ is related to subset $B$ if and only if $A$ and $B$ have the same number of elements. So, for example:

• $\{m,n\}\,R\,\{n,p\}$ because they both have 2 elements
• $\{n,q,r\} \,R\, \{m,q,s\}$ because they both have 3 elements

... and so on.

Next, you need to understand the $/$ notation. If a relation $R$ is defined on a set $A$, then $A/R$ (called the quotient set of $A$ by $R$) is the set of all the equivalence classes into which $A$ is 'divided' (or partitioned) by $R$ (hence the use of the word 'quotient').

For example, if $A = \mathbb{Z}$ and $m\,R\,n \iff 2|(m - n)$ (in other words, $(m - n)$ is divisible by $2$), then $R$ partitions $\mathbb{Z}$ into two equivalence classes: {even integers} and {odd integers}, and these two sets are therefore the elements of $A/R$.

So, in the question you're asking, whereas it makes sense to talk about $P(X)/R$, it makes no sense to talk about $\{m\}/R$ or $X/R$, because $R$ is not defined on individual elements like $m$, but on sets.

OK. So let's look at the question that does make sense: How many elements are there in $P(X)/R$? This question means: when $P(X)$ is partitioned into equivalence classes by $R$, how many of these equivalence classes are there? Well, for example, all the subsets of $X$ that contain one element - that's $\{m\}, \{n\}, \{p\}, \{q\}, \{r\}, \{s\}$ - are equivalent. So they form one equivalence class. (And that, I suspect, is what the question means when it says 'list all the elements in ${m}/R$', although that is incorrect use of the notation.)

All the subsets of $X$ containing 2 elements form another equivalence class; all the subsets containing 0 elements form another, and so on. Since you can form subsets containing 0, 1, 2, 3, 4, 5 or 6 elements, there are therefore 7 equivalence classes, and therefore 7 elements in $P(X)/R$.

The proof that $R$ is an equivalence relation is trivial. Any relation that contains the words ' $A$ ... the same as $B$' usually is. If $A$ has the same number of elements as $B$, then it's obvious that $A\,R\,A$ (reflexive) and $A\,R\,B \iff B\,R\,A$ (symmetric) and $(A\,R\,B \wedge B\,R\,C) \Rightarrow A\,R\,C$ (transitive).

• Mar 20th 2009, 11:36 AM
zhupolongjoe
Ok, thank you. I don't know why the book would ask a question that doesn't make sense...I just put the question just as it appeared in the text. Maybe they want you to realize that the question is nonsensical? But thank you the same!
• Mar 20th 2009, 11:57 AM
zhupolongjoe
I just have on further question:

"All the subsets of http://www.mathhelpforum.com/math-he...2dc6b383-1.gif containing 2 elements form another equivalence class; all the subsets containing 0 elements form another, and so on. Since you can form subsets containing 0, 1, 2, 3, 4, 5 or 6 elements, there are therefore 7 equivalence classes, and therefore 7 elements in http://www.mathhelpforum.com/math-he...dca30f40-1.gif."

Why wouldn't it be the 1+6+.....+6+1..i.e. add all the elements..like there is one subset with 0 elements, 6 subsets with 1 element...6 subsets with 5 elements and so on...?
• Mar 20th 2009, 12:08 PM
Equivalence Classes
Hello zhupolongjoe[/quote]
Quote:

Originally Posted by zhupolongjoe
"...there are therefore 7 equivalence classes, and therefore 7 elements in http://www.mathhelpforum.com/math-he...dca30f40-1.gif."

Why wouldn't it be the 1+6+.....+6+1..i.e. add all the elements..like there is one subset with 0 elements, 6 subsets with 1 element...6 subsets with 5 elements and so on...?

Because this is the number of elements in $P(X)$ - and in fact it's equal to $2^6 = 64$. (Perhaps you can work out why?) On the other hand $P(X)/R$ is the set of equivalence classes, and there are 7 of these, into which the 64 elements of $P(X)$ are distributed by $R$.

In the other illustration I gave you (the $2|(n-m)$ relation on $\mathbb{Z}$) there are just two equivalence classes: {odd integers} and {even integers}, whereas, of course, there are infinitely many integers in each one.