OIMU 2009 Problem 5

Let $\mathbb{N}$ and $\mathbb{N}^*$ be the sets containing the natural numbers/positive integers respectively.

We define a binary relation on $\mathbb{N}$ by $a\acute{\in}b$ iff the $a$ -th bit in the binary representation of $b$ is $1$ .

We define a binary relation on $\mathbb{N}^*$ by $a\tilde{\in}b$ iff $b$ is a multiple of the $a$ -th prime number $p_a$ .

i) Prove that there is no bijection $f:\mathbb{N}\to \mathbb{N}^*$ such that $a\acute{\in}b\Leftrightarrow f(a)\tilde{\in}f(b)$ . ii) Prove that there is a bijection $g:\mathbb{N}\to \mathbb{N}^*$ such that $(a\acute{\in}b \vee b\acute{\in}a)\Leftrightarrow (g(a)\tilde{\in}g(b) \vee g(b)\tilde{\in}g(a))$ .