How many distinct equivalence classes does this equivalence on rationals have?

Question

Let $$A = \{ r\in \mathbb Q \mid \exists p\in \mathbb Z,\text{ and $q\in \mathbb Z$, with $p$ even and $q$ odd, and $r = p/q$} \}$$

For example, $A$ contains such $2/9, 16/(-34)$, and $4$. $A$ does not contain $9/10$, or $-15$ , or $18/32$.

Let $\mathbb Q$ be the set of all rational numbers and let the relation ~ be defined by $x \sim y$ if and only if $x − y ∈ A$.

And I need help for:

How many distinct equivalence classes does ~ have$?$ Describe them.

I think it's an infinite set, but professor told us it's finite. How could it be finite?

Answer 1

This isn't a complete answer, as I can't classify all equivalence classes.

Your professor isn't right. The equivalence relation which you have provided in fact has infinitely many equivalence classes. Take for example $\frac{1}{2^n},n\in\Bbb N$. I claim these numbers are pairwise inequivalent under this relation.

Indeed, suppose $n<m$. Then we have $\frac{1}{2^n}-\frac{1}{2^m}=\frac{2^{m-n}-1}{2^m}$ which has odd numerator and even denominator, and hence can't be represented as $\frac{\text{even}}{\text{odd}}$.

Let me remark that $\frac{1}{2^n}$ don't generate all equivalence classes, as, for example, $\frac{1}{6}$ is not equivalent to any of these (indeed, $\frac{1}{6}-\frac{1}{2^n}=\frac{2^{n-1}-3}{3\cdot 2^n}$).

Answer 2

$\newcommand{\Q}{\mathbb{Q}}$Let me try and describe all the equivalence classes.

Write $\alpha \in \Q$ as $$ \alpha = \frac{a}{b}, $$ with $a, b$ coprime integers.

If $a$ is even, then $\alpha \in A$, so it is in the class of $0$.

All $\alpha$ such that both $a, b$ are odd are in the class of $1$, as $$ \alpha - 1 = \frac{a}{b} - 1 = \frac{a - 1}{b} \in A. $$

We are left with the $\alpha$ with $a$ odd and $b$ even. Let $$ \alpha = \frac{a}{2^{e} s}, \qquad \beta = \frac{b}{2^{f} t}, $$ with $a, b, s, t$ odd, and $e \ge f > 0$. Then $$ \alpha - \beta = \frac{a t - 2^{e - f} b s}{2^{f} s t}. $$ If $e > f$, then this is not in $A$, so that $\alpha$ and $\beta$ are not equivalent. If $e = f$, then $$ \alpha - \beta = \frac{a t - b s}{2^{f} s t} $$ is in $A$ if and only if $$\tag{cond} 2^{f+1}\ \text{divides}\ a t - b s. $$ Now given $$ \alpha = \frac{a}{2^{f} s}, \qquad \beta = \frac{b}{2^{f} t}, $$ with $\alpha$ fixed, what are the $\beta$ that are equivalent to $\alpha$? We need (cond) to hold. Choose $t$ to be an arbitrary odd integer, then we have $$ b s \equiv a t \pmod{2^{f+1}}, $$ which has the unique solution modulo $2^{f+1}$ $$\tag{bnaught} b_{0} = s^{-1} a t \pmod{2^{f+1}}, $$ where $a^{-1}$ denotes the inverse of the (odd) integer $a$ modulo $2^{f+1}$. It follows that $\beta$ is equivalent to $\alpha$ if and only if $$ \beta = \frac{b_{0} + k 2^{t+1}}{2^{f} t} $$ where $t$ is an arbitrary odd integer, $k$ is an arbitrary integer, and $b_{0}$ is determined from (bnaught).

This seems to me very close to a description of the classes. I'll try to come back to this later.