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?

  • $\begingroup$ "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. $\endgroup$ – Thomas Andrews Feb 1 '16 at 16:04
  • $\begingroup$ @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. $\endgroup$ – GarethAS Feb 1 '16 at 16:38
  • $\begingroup$ No, that's not true. @Gareth. An equivalence relation on $A$ does not mean an equivalence relation on $P(A)$. $\endgroup$ – Thomas Andrews Feb 1 '16 at 16:40
  • $\begingroup$ Oh... So would R not be an equivalence relation on S as @Jackswastedlife says below? $\endgroup$ – GarethAS Feb 1 '16 at 16:49
  • $\begingroup$ 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$. $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – GarethAS Feb 1 '16 at 19:56
  • $\begingroup$ @Gareth The answer defines fibres immediately after using the term. $\endgroup$ – BrianO Feb 1 '16 at 23:40
  • $\begingroup$ @BrianO I don't understand it, honestly $\endgroup$ – GarethAS Feb 2 '16 at 0:16
  • $\begingroup$ @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\}$ ...". $\endgroup$ – BrianO Feb 2 '16 at 0:18
  • $\begingroup$ What I mean to say is that I don't understand the equation. $\endgroup$ – 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.

  • $\begingroup$ Oh of course, $a$ and $b$ are the same length there still. I see my error. Thank you. $\endgroup$ – GarethAS Feb 1 '16 at 16:11
  • $\begingroup$ You and @ThomasAndrews seem to have differing opinions on whether R is an equivalence relation of P(A) $\endgroup$ – GarethAS Feb 1 '16 at 18:25
  • $\begingroup$ $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\})$. $\endgroup$ – Jack's wasted life Feb 1 '16 at 18:31
  • $\begingroup$ @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. $\endgroup$ – GarethAS Feb 2 '16 at 2:14
  • $\begingroup$ 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)$.... $\endgroup$ – Jack's wasted life Feb 2 '16 at 3:55

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.