MathDB

Let

\mathbb{N}

and

\mathbb{N}^*

be the sets containing the natural numbers/positive integers respectively.
We define a binary relation on

\mathbb{N}

a\acute{\in}b

iff the

a

-th bit in the binary representation of

b

1

.
We define a binary relation on

\mathbb{N}^*

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))

Problem Statement