For college and university level advanced Mathematics
User avatar
Avik Roy
Posts: 156
Joined: Tue Dec 07, 2010 2:07 am


Unread post by Avik Roy » Sat Jan 29, 2011 1:27 pm

Consider the following functions:
$g:\mathbb N \rightarrow \mathbb N; \ \ \ g(n) = $ highest power of $2$ that divides $n$
$f:\mathbb N \rightarrow P(\mathbb N); \ \ \ f(n) = $ set of all primes that divide $n$
Let $R_1$ and $R_2$ are two relations defined over $\mathbb N$ so that for any two members $a,b$ of $\mathbb N$, $(a,b) \in R_1$ if $g(a) < g(b)$ or, $a<b$ when $g(a) = g(b)$.
For $R_2$, $(a,b) \in R_2$ if $f(a) \subset f(b)$ or $a<b$ when $f(a) = f(b)$

Is there any bijection between $\mathbb N$ and $R_1$ or, $\mathbb N$ and $R_2$ or, $R_1$ and $R_2$

Apologis please if I've missed any mathematical rigor, I'm not that good in it
"Je le vois, mais je ne le crois pas!" - Georg Ferdinand Ludwig Philipp Cantor

Posts: 52
Joined: Sun Dec 19, 2010 11:48 am

Re: ordering

Unread post by abir91 » Sat Jan 29, 2011 2:08 pm

I think all of them are true. A sketch of the proof will be as follows:
First note that, $R_1 \subseteq \mathbb{N} \times \mathbb{N}$. Then show that, $R_1$ is infinite. Then $|N| = |R_1|$. Similar argument for $R_2$.

Have you read the Forum Rules and Guidelines?

Post Reply