Find an equivalence relation over all of $\mathbb{Z}$ which has infinitely many equivalence classes with infinitely many elements in each

Question

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?

Answer 1

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, ...\}$.

Answer 2

we cannot place $0$ into an unique equivalence class

So don't. Put it into one of the existing classes and you're done. Equivalence relationships and partitionings are the same thing, you can shuffle elements quite freely.

More generally, consider any bijection $f:\mathbb{Z}\to\mathbb{Z}\times\mathbb{Z}$, and let $\pi:\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$ be the projection onto second coordinate: $\pi(a,b)=b$.

Then define $x\sim y$ if and only if $\pi(f(x))=\pi(f(y))$, a.k.a. the kernel of $\pi\circ f$. You can easily verify that this satisfies your requirements. And in fact, every equivalence class that satisfies your requirements arises in this manner.

Answer 3

I will give 2 Solutions , though there are variations & tweaks which can give more Solutions.

SOLUTION 1 :

Using the Decimal representation of some transformation function $f(n)$ involving reciprocals.

Consider the rational number $1/(9+|n|)$ :
It will have a Non-Zero Decimal representation.
Due to Property of rational numbers , there will eventually follow repeating Digits in that representation.

CORE IDEA : Take the repeating Digits to be the Equivalence Class for Integer $n$.

We see that , we will have infinite Equivalences Classes.
Move-over , we will have infinite count in all Equivalences Classes.

Here is a listing :

$n=0$ , $1/(9+0)=0.\color{orange}{1}111\cdots$ : $0 \approx [1]$
$n=\pm1$ , $1/(9+1)=0.1\color{orange}{0}00\cdots$ : $\pm1 \approx [0]$
$n=\pm2$ , $1/(9+2)=0.\color{orange}{10}101010\cdots$ : $\pm2 \approx [10]$
$n=\pm3$ , $1/(9+3)=0.08\color{orange}{3}333\cdots$ : $\pm3 \approx [3]$
$n=\pm4$ , $1/(9+4)=0.0\color{orange}{769230}76923076923076923076923\cdots$ : $\pm4 \approx [769230]$
$n=\pm5$ , $1/(9+5)=0.0\color{orange}{714285}714285714285714285714285\cdots$ : $\pm5 \approx [714285]$

Suitably large $n$ values will have same repeating Digits landing in same Equivalence Class.
$[1] \approx \{0,\pm81,\pm891,\pm8991,\pm89991\cdots\}$
$[0] \approx \{\pm1,\pm91,\pm991,\pm9991,\pm99991\cdots\}$
$[10] \approx \{\pm2,\pm101,\pm1091,\pm10991,\pm109991\cdots\}$
$[3] \approx \{\pm3,\pm111,\pm1191,\pm11991,\pm119991\cdots\}$
$[769230] \approx \{\pm4,\pm121,\pm1291,\pm12991,\pm129991\cdots\}$
$[714285] \approx \{\pm5,\pm131,\pm1391,\pm13991,\pm139991\cdots\}$

We can tweak the rational number transformation function in certain ways (Eg1 change $9$ to $15$ , Eg2 change $|n|$ to $n^2$) & use the repeating Digits in certain other ways (Eg3 use the length , Eg4 add up the Digits) to get Alternate Examples for the Equivalence Classes.

SOLUTION 2 :

Using Binary representation of Integer $(n+1)$

$0+1 \equiv 0\color{orange}{1}_2 \approx [1]$
$1+1 \equiv 0\color{orange}{1}0_2 \approx [1]$
$2+1 \equiv 0\color{orange}{11}_2 \approx [11]$
$3+1 \equiv 0\color{orange}{1}00_2 \approx [1]$
$4+1 \equiv 010\color{orange}{1}_2 \approx [1]$
$5+1 \equiv 0\color{orange}{11}0_2 \approx [11]$
$6+1 \equiv 0\color{orange}{111}_2 \approx [111]$
$20+1 \equiv 01010\color{orange}{1}_2 \approx [1]$
$40+1 \equiv 010100\color{orange}{1}_2 \approx [1]$
$80+1 \equiv 0101000\color{orange}{1}_2 \approx [1]$
$222+1 \equiv 0110\color{orange}{11111}_2 \approx [11111]$
$333+1 \equiv 010100\color{orange}{111}0_2 \approx [111]$
$444+1 \equiv 011011110\color{orange}{1}_2 \approx [1]$

CORE IDEA : take the right most contiguous Digits made of $1$ to be the Equivalence Class.

We get the following :
$\{0,1,3,4,20,40,80,444\cdots\} \approx [1]$
$\{2,5,122,426\cdots\} \approx [11]$
$\{6,333,1910,2006\cdots\} \approx [111]$
$\{222,891\cdots\} \approx [11111]$

We can tweak that too : Eg 5 take the right most contiguous Digits made of $1$ & take that length , Eg 6 Count the number of non-trivial $0$ Digits in the Binary representation