# Problem with a strange relation; what is cardinality

I've tried solve this for hours, but I still stuck in the beginning. Here's my problem:

Let $R \subseteq P(\mathbb{N} \times \mathbb{N})^2$ be the following equivalence relation:

$\langle r,s\rangle \in R \Leftrightarrow (\exists \pi : \mathbb{N} \to \mathbb{N} \forall x,y \in \mathbb{N} (\langle x,y\rangle \in r \leftrightarrow \langle\pi(x),\pi(y)\rangle \in s))$

What is cardinality of a set $P(\mathbb{N} \times \mathbb{N})/_R$?

Notes:

• $P(A)$ is a Power Set
• $\pi$ is a bijection
• $A/_R$ is a set of equivalence classes, I mean: $A/_R = \{ [a]_R | a \in Dom(R) \}$
-
Is $\pi$ supposed to be a bijection? Or an arbitrary function? – Andrés E. Caicedo Jan 10 '11 at 2:35
@Andres Caicedo: Yes, $\pi$ is a bijection function. – locer4 Jan 10 '11 at 2:39
Oh, that was one of the conditions! Sorry, I missed it at first. – Andrés E. Caicedo Jan 10 '11 at 2:54

## 1 Answer

Given a bijection $\pi:{\mathbb N}\to{\mathbb N}$, let ${\hat\pi}:{\mathbb N}\times{\mathbb N}\to{\mathbb N}\times{\mathbb N}$ be the function ${\hat\pi}(a,b)=(\pi(a),\pi(b))$. Then ${\hat\pi}$ is a bijection.

We can rewrite the condition for being in $R$ as follows: $\langle r,s\rangle\in R$ iff there is a bijection $\pi:{\mathbb N}\to{\mathbb N}$ such that for any $x\in{\mathbb N}\times{\mathbb N}$, we have that $x\in r$ iff ${\hat\pi}(x)\in s$.

The advantage of this description is two-fold: In a sense, it is simpler, we do not need to worry about the elements of $r,s$ being pairs of numbers. Second, the condition

for any $x\in{\mathbb N}\times{\mathbb N}$, we have that $x\in r$ iff ${\hat\pi}(x)\in s$

can be further simplified: For $r$ a set of pairs of numbers, write ${\hat\pi}''r$ for the pointwise image of $r$ under ${\hat\pi}$: $${\hat\pi}''r=\{{\hat\pi}(q)\mid q\in r\}.$$

Then the condition above is simply $s={\hat\pi}''r$.

So, the relation $R$ is given by: $(r,s)\in R$ iff there is a bijection $\pi$ such that $s={\hat\pi}''r$.

This should help you figure out how to understand the equivalence classes and how to count them.

Below I write some details on how to do this. I suggest that you read the bare minimum for now.

The key observation is that we are saying that $r$ is $R$-related to $s$ iff they are isomorphic. More carefully, let $$f(r)=\{a\mid\exists b\in{\mathbb N}(a,b)\in r\lor(b,a)\in r\}.$$ This is the field of $r$. Then $(f(r),r)$ is a binary relation, and if $(r,s)\in R$, then $(f(r),r)$ is isomorphic to $(f(s),s)$, with the isomorphism being the function $\pi$ from before.

Luckily for us, it is enough to consider the case $f(r)={\mathbb N}$, so we do not need to worry about the extra parameter $f(r)$.

So, what we have to do is to figure out how many non-isomorphic countable binary relations there are. The obvious guess is continuum many. In fact, there are continuum many non-isomorphic (infinite) countable linear orders. For any such order $(A,\le)$ there is a binary relation $r\subseteq{\mathbb N}\times{\mathbb N}$ such that $({\mathbb N},r)$ is isomorphic to $(A,\le)$ (this is easy from the fact that $A$ is countably infinite).

Of course, if $(r,s)\in R$, then $({\mathbb N},s)$ is also isomorphic to $(A,\le)$. This gives us that there are at leas continuum many $R$-classes, and since this is also an upper bound, we find that the number of classes is continuum many.

All that remains is to show that there are continuum many countable linear orders. In fact, to each infinite sequence $s$ of 0s and 1s, we can assign an order $<_s$ so that if $s_1$ and $s_2$ are distinct sequences, then $<_{s_1}$ is not isomorphic to $<_{s_2}$.

To do this, let the code of 0, $c(0)$, be a single point, and the code of 1, $c(1)$, be a copy of ${\mathbb Q}$. Then to the sequence $$a_0,a_1,a_2,\dots$$ where each $a_i$ is 0 or 1, we assign the linear order consisting of: A copy of $c(a_0)$ followed by a copy of ${\mathbb Z}$ followed by a copy of $c(a_1)$ followed by a copy of ${\mathbb Z}$ followed by a copy of $c(a_2)$ ...

It is easy to see that these orders are as wanted.

-
I think, the answer is continuum, but I'm not sure of that, and I don't know, how to prove this. – locer4 Jan 10 '11 at 3:09
Yes, the answer is continuum. I'll add an additional hint a bit later, but there are several ways to proceed now (and my hint may not be the easiest way, it is just how I think of these things). – Andrés E. Caicedo Jan 10 '11 at 3:23
If I understand it right, in this problem there is a question: how many relations are in $\mathbb{N}$? Am I right? Could I rephrase main question of the problem and show, that the solution is continuum? Because it seems to be easer to prove. – locer4 Jan 10 '11 at 7:28
@locer4: It is a bit more than that. The relations cannot be isomorphic. And even more: they cannot be isomorphic as relations on their fields. The bit of work above was to produce non-isomorphic relations with ${\mathbb N}$ as their field. Of course, there are many other ways of doing this, using linear orders is not necessary by any means. But counting relations on ${\mathbb N}$ is not enough, as many different relations may be isomorphic. – Andrés E. Caicedo Jan 10 '11 at 7:34
Thank You very much! :) – locer4 Jan 10 '11 at 8:05