3
$\begingroup$

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) \}$
  • 0
    Oh, that was one of the conditions! Sorry, I missed it at first.2011-01-10

1 Answers 1

3

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.

  • 0
    @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.2011-01-10