Possible cardinalities of the equivalence partitioning Let $\sim$ denote a relation in $\mathbb{R}$ as follows:
$x \sim y \iff d(x,y) \in \mathbb{Q} $ ($d(x,y)$ is the distance between $x$ and $y$)
Determine the possible cardinalities of the equivalence partitioning.
I'm having a bit of trouble working on this problem, because intuitively it's possible to have countable infinity as cardinality, since you could just take $y = 1$ and then for every $n \in \mathbb{N}: d(y,n) \in \mathbb{N} \subset \mathbb{Q}$, but the question is about which cardinalities are possible, and I can't think of any elements in $\mathbb{R}$ where the distance between that number and any other element isn't in $\mathbb{Q}$ or where it would be countable.
If I look at the equation for distance, $d(x,y) = \sqrt{(x-y)^2}$ I still am nowhere. Can someone give me a hint as to how I should go about this?
 A: Perhaps a proof that this is in fact an equivalence relation can shed some light.
If $x\sim y$ then $|x-y|\in\mathbb Q$, and so $x-y\in\mathbb Q$, and conversely if $x-y\in\mathbb Q$ then $|x-y|\in\mathbb Q$ so $x\sim y$.  The fact that $x\sim x$ then follows from the fact that $x-x=0\in\mathbb Q$.  The fact that if $x\sim y$ then $y\sim x$ follows from the fact that either says $|x-y|=|y-x|\in\mathbb Q$.  The fact that if $x\sim y$ and $y\sim z$ then $x\sim z$ follows from the fact that if $x-y\in\mathbb Q$ and $y-x\in\mathbb Q$ then $x-z\in\mathbb Q$.
So the relation is congruence modulo $\mathbb Q$: two numbers are equivalent if and only if their difference is rational.
It's easy to show from that that the set of all numbers equivalent to $x$, i.e. the equivalence class to which $x$ belongs, is the set of all numbers of the form $x+r$ for some $r\in\mathbb Q$.  The number of such possible values of $r$ is countably infinite.  And different values of $r$ yield different numbers equivalent to $x$.  Hence the equivalence class is countably infinite.
Consequently there cannot be only countably many equivalence classes, since the union of countably many countable sets is countable.
The number of equivalence classes cannot exceed $2^{\aleph_0}$ since you can pick one member from each equivalence class and then the set of numbers chosen is a subset of $\mathbb R$, whose cardinality is $2^{\aleph_0}$.  So it's a cardinality greater than $\aleph_0$ but less than or equal to $2^{\aleph_0}$.  Going beyond there to a proof that it's actually equal to $2^{\aleph_0}$ is something I once could do while standing on one foot, but I seem to be rusty on some of this.
