# Is a relation, R, an Equivalence Relation of a Power Set?

Where $A = \{1,2,3,4,5,6\}$ and $S = P(A)$ is the power set, for $a,b \in S$ define a relation $R: (a,b) \in R$ where $a$ and $b$ have the same number of elements.

Is $R$ an equivalence relation on $S$ and if so how many equivalence classes are there?

I've defined my $R$ as being $\{(\{1,2\},\{3,4\}),(\{1,2\},\{5,6\}),(\{1,2\},\{1,2\}),(\{3,4\},\{1,2\}),(\{3,4\},\{3,4\}),(\{3,4\},\{5,6\}),(\{5,6\},\{1,2\}),(\{5,6\},\{3,4\}),(\{5,6\},\{5,6\})\}$

because of the part of the question mentioning $a$ and $b$ have the same number of elements. Was that wrong to do?

• "I've defined my $R$ as being..." There, you've already started making a mistake. You aren't defining $R$ - the problem defined $R$. The $R$ you've defined is very different from the $R$ that the problem defined. – Thomas Andrews Feb 1 '16 at 16:04
• @ThomasAndrews I've recognised my problem there, and have since realised that if it is an equivalence relation of $A$, then it must also be of $P(A)$ since $A \in P(A)$. I'm now struggling though to prove how many equivalence classes there are. – GarethAS Feb 1 '16 at 16:38
• No, that's not true. @Gareth. An equivalence relation on $A$ does not mean an equivalence relation on $P(A)$. – Thomas Andrews Feb 1 '16 at 16:40
• Oh... So would R not be an equivalence relation on S as @Jackswastedlife says below? – GarethAS Feb 1 '16 at 16:49
• No, $R$ is defined precisely above as an equivalence relation on $S$ - it is a subset of the set of pairs of elements of $S$, not of pairs of elements of $A$. "For each $a,b\in S$, define ... $R$..." There is no relation defined on $A$. – Thomas Andrews Feb 1 '16 at 16:50

In general if $f:X\to Y$ is a function then the relation $R$ on $X$ defined by: $$uRv\iff f(u)=f(v)$$ is an equivalence relation on $X$.

Equality $f(u)=f(u)$ guarantees reflexivity.

Implication $f(u)=f(v)\implies f(v)=f(u)$ guarantees symmetry.

Implication $f(u)=f(v)\wedge f(v)=f(w)\implies f(u)=f(w)$ guarantees transitivity.

It is always possible (and handsome) to let $f$ be surjective by restricting its codomain. Then equivalence classes are the fibres $f^{-1}(\{y\}):=\{x\in X\mid f(x)=y\}$ for $y\in Y$ and consequently the cardinality of $Y$ equals the number of equivalence classes.

You can apply this here on function $f:S\to\{0,1,2,3,4,5,6\}$ prescribed by:$$s\mapsto\text{number of elements of }s$$

This function is surjective and the cardinality of $\{0,1,2,3,4,5,6\}$ is $7$. So there are $7$ equivalence classes.

• I understand what gives a relation equivalence. What are fibres? I think if I understand that then I'll understand why there are 7 equivalence classes. – GarethAS Feb 1 '16 at 19:56
• @Gareth The answer defines fibres immediately after using the term. – BrianO Feb 1 '16 at 23:40
• @BrianO I don't understand it, honestly – GarethAS Feb 2 '16 at 0:16
• @Gareth The identity immediately following defines the term. Never mind. Just ditch the term "fibre", and assume the sentence reads "... equivalence classes are the inverse images $f^{-1}(\{y\}):=\{x\in X\mid f(x)=y\}$ ...". – BrianO Feb 2 '16 at 0:18
• What I mean to say is that I don't understand the equation. – GarethAS Feb 2 '16 at 1:59

Yes that was wrong to do since you missed a lot of sets for example $$(\{1,2,3\},\{2,3,4\})\in R$$

$R$ is indeed an equivalence relation (appeal to the definition) and any two members of an equivalence class have same number elements. There are $7$ possible cardinalities including $0$ and hence there are $7$ equivalence classes.

• Oh of course, $a$ and $b$ are the same length there still. I see my error. Thank you. – GarethAS Feb 1 '16 at 16:11
• You and @ThomasAndrews seem to have differing opinions on whether R is an equivalence relation of P(A) – GarethAS Feb 1 '16 at 18:25
• $R$ is a subset of $P(A)^2$, wouldn't you agree? So $R$ is a relation on $S=P(A)$ as ThomasAndrews says, it's not a relation on $A$. A relation on $A$ would be a subset of $A^2$ and have elements like $(1,2)$ instead of elements like $(\{1,2\},\{2,3\})$. – Jack's wasted life Feb 1 '16 at 18:31
• @Jackswastedlife oh I see, okay. So we've established $R$ contains a whole bunch of sets, so many I couldn't write them all out...And those sets have elements of $P(A)$ in them... I still don't know how to show $R$ is an equivalence relation of $P(A)$ without writing out the entire thing. – GarethAS Feb 2 '16 at 2:14
• If $\#$ denotes the number of elements you could do something like this. $\#(x)=\#(x)\implies(x,x)\in R\;\forall x\in P(A)$. $(x,y)\in R\implies \#(x)=\#(y)\implies (y,x)\in R\;\forall\;(x,y)\in P(A)$.... – Jack's wasted life Feb 2 '16 at 3:55