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.

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.

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

$\displaystyle 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: $\displaystyle P(X)$ is a *set of ... subsets ...*; so the elements of $\displaystyle P(X)$ are themselves sets - and I have listed a few of them above.

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

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

... and so on.

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

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

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

OK. So let's look at the question that does make sense: How many elements are there in $\displaystyle P(X)/R$? This question means: when $\displaystyle P(X)$ is partitioned into equivalence classes by $\displaystyle R$, how many of these equivalence classes are there? Well, for example, all the subsets of $\displaystyle X$ that contain one element - that's $\displaystyle \{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 $\displaystyle {m}/R$', although that is incorrect use of the notation.)

All the subsets of $\displaystyle 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 $\displaystyle P(X)/R$.

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

Grandad