3
$\begingroup$

Does there exist an equivalence relation, defined on $\mathbb{N}$, with infinitely many equivalence classes, all of which contain infinitely many elements?

I see no reason for such a relation not to exist, but I'm having trouble finding an example.

$\endgroup$
3
$\begingroup$

Yes. First note that $\lvert\mathbb N\rvert=\lvert\mathbb N\rvert^2$ so it would be strange if there weren't.

For instance let $\sim$ be the equivalence relation defined by $p^n\sim p^k$ for all $p$ prime and $n,k\ge 1$, and let all numbers which aren't of the form $p^n$ be equivalent.

So $$1\sim 6\sim 10\sim 12\sim 14\sim 15\sim\cdots$$ $$2\sim 4\sim 8\sim 16\sim\cdots$$ $$3\sim 9\sim 27\sim\cdots$$

and so on.

Edit: To elaborate on my first point. Let $f:\mathbb N^2\to\mathbb N$ be any bijection. Then set $f(n,k)\sim f(n,l)$ for all $n,k,l$ to get an equivalence relation as wanted.

$\endgroup$
4
$\begingroup$

An example: Let $a\equiv b$ if the highest power of $2$ that divides $a$ is the same as the highest power of $2$ that divides $b$.

So $\{1,3,5,7,9,\dots\}$ is one equivalence class.

$\{2,6,10,14,18,\dots\}$ is another.

$\{4,12,20,28,36,\dots\}$ is another.

And so on.

There are many other examples.

$\endgroup$
4
$\begingroup$

Little less constructive...

Take your favorite bijection $\mathbb{N} \stackrel{f}{\to} \mathbb{N} \times \mathbb{N}$, let $\pi_2$ be the projection in the second coordinate, and consider $h=\pi_2 \circ f$. Now, define $x \sim y \iff h(x)=h(y).$

$\endgroup$
1
$\begingroup$

Here's another example: Let $a \sim b$ if $a$ and $b$ have the same number of prime factors (up to multiplicity). We can put $1$ in with the prime numbers to meet your criterion of all classes being infinite. Then the classes are: $$\{1,2,3,5,7,11,\ldots\}\\ \{4,6,9,10,14,\ldots\}\\ \{8,12,18,20,\ldots\}\\ etc.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.