I want to find an equivalence relation defined on all integers (that is, all of $\mathbb{Z}$) where
- The equivalence relation partitions $\mathbb{Z}$ into infinitely many equivalence classes; and
- Every equivalence class contains an infinite number of elements.
I've been thinking about this interesting question for a while, and I have come up with two ideas which are close, but not complete solutions.
My first idea was to define the equivalence relation $\sim$ where $x \sim y \iff x = \pm p^m, y = \pm p^n$ for some prime number $p$, and some integers $m, n$.
- This will certainly create infinitely many equivalence classes where each equivalence class will essentially contain all powers of one prime number (positive or negative).
- Since there are infinitely many prime numbers, there will be infinitely many equivalence classes, and each equivalence class will contain infinitely many elements.
However, there are two problems with this idea: firstly, $1$ and $-1$, which are equal to $\pm p^0$ for all prime numbers $p$, will be in all of the equivalence classes. Secondly, $0$ will need to be placed in an equivalence class by itself, which does not satisfy the condition that every equivalence class must contain an infinite number of elements.
My second idea was to say that two integers $x$ and $y$ a are equivalent iff the largest power of $2$ that divides them is the same. Essentially, I say that $x$ and $y$ are equivalent iff the number of zeroes at the end of their binary expansion is the same.
However, this fails to account for the number $0$; we cannot place $0$ into an unique equivalence class because that would fail to satisfy the condition that every equivalence class must contain an infinite number of elements.
Can anyone provide a hint or a solution to this problem?
Best Answer
We can fix your first idea but there is another problem with it: you have said nothing about the integers which are not prime powers. However, all of these problems can be fixed easily. First, exclude $\{1, -1\}$ from the prime classes. Next, create one more equivalence class of everything else: $\{0, \pm1, \pm6, \pm10, ...\}$.