[Math] Countability and uncountability of a set $A$ and the set of equivalence classes $A / R$

discrete mathematicselementary-set-theoryequivalence-relationsrelations

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.

Thanks.

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.

Best Answer

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.

Related Question