Let $A$ be a set and $R$ an equivalence relation on $A$. Prove or disprove:

  1. If $A$ is countable then all the equivalence classes of $R$ are countable.
  2. If $A$ isn't countable then the quotient group $A/R$ isn't countable.
  3. If $A$ isn't countable and $A/R$ is countable, then there is an equivalence class in $R$ that isn't countable.
  1. Well, I thought of going from the definitions and say that two equivalence class is either identical or foreign, also, the equivalence relation (that is transitivity, reflexivity and symmetry) can add only a finite number of elements so at most it will be countable. So it's true.

  2. False: $A=\Bbb R , \ R=mod (2) $ so there are only two equivalence class and the quotient group consists of only $1$ and $0$.

  3. I'm pretty sure it's true, $A/R$ at most has the cardinality $\aleph_0$ and it's possible to have an equivalence class that is in one to one correspondence with $A$. But I don't really have an idea on how to prove it.

Please share your thoughts on how to solve this.


Note: This is from set theory intro course so I probably won't understand solutions that utilize knowledge from abstract algebra, rings or group theory.

  • $\begingroup$ @Ragnar, but integers are countable, I chose the reals because they aren't countable. $\endgroup$ – GinKin Dec 20 '13 at 18:36
  • 1
    $\begingroup$ Oh, sorry, you're right, but then, your '$\mod 2$' wasn't right either. You could say $xRy$ if and only if $\lfloor x\rfloor=\lfloor y\rfloor$ $\endgroup$ – Ragnar Dec 20 '13 at 18:41
  • $\begingroup$ @Ragnar That is in $A=\mathbb R$ ? $\endgroup$ – GinKin Dec 20 '13 at 18:47
  • 1
    $\begingroup$ Yes, $A=\mathbb R$. $\endgroup$ – Ragnar Dec 20 '13 at 18:49
  • 1
    $\begingroup$ that's right...(at least 12 characters....) $\endgroup$ – Ragnar Dec 20 '13 at 19:00

First note that equivalence classes $R$ are subsets of $A$. Because the size of any subset of a countable set is countable, all equivalence classes are countable.

For part $3$, suppose all equivalence classes are countable. The order of a union countable sets is also countable, so the order of $A$ (which is the order of the union of all equivalence classes) is countable. This is a contradiction, so there is at least one non-countable equivalence class.

  • 1
    $\begingroup$ I don't understand how an order come into play here, why does ordering the sets even matter in this case ? isn't a union enough ? $\endgroup$ – GinKin Dec 20 '13 at 19:05
  • 1
    $\begingroup$ The 'order' of a set is just the number of elements it contains, i.e. it's size. $\endgroup$ – Ragnar Dec 20 '13 at 19:42
  • $\begingroup$ Or it's cardinality, I see. Thanks again. $\endgroup$ – GinKin Dec 20 '13 at 19:48

I have prove for 3. If A isn't countable and A/R is countable then there is an equivalence class that isn't countable. We have example for it is- If A= the set of real numbers Relation between a and b is either both are rational or irrational Then Q/R is countable having two equivalence classes one of rationals and second is of irrationals. So here equivalence class of irrationals is uncountable.


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.