Is there an injective function from the set of natural numbers N to the set of rational numbers Q, and viceversa.

What are these two functions if they exist?

Please I would appreciate easy examples just using set theory without using cardinality or other complex notation.

  • 2
    $\begingroup$ Injection from one to the other is obvious. $\endgroup$ – Wojowu Feb 6 '17 at 17:37
  • $\begingroup$ @Wojowu If it was obvious to me I would have not posted the question. $\endgroup$ – JJ Ab Feb 6 '17 at 17:41
  • $\begingroup$ @JJAb Remember that $\mathbb{N}\subset\mathbb{Q}$: every natural number is rational. If $A$ is a subset of $B$, do you see an injection from $A$ into $B$? (HINT: what's the easiest way to take in an element of $A$ and spit out an element of $B$, if every element of $A$ is an element of $B$?) $\endgroup$ – Noah Schweber Feb 6 '17 at 17:42
  • 1
    $\begingroup$ @JJAb I think Wojowu means the $\mathbb{N}\to\mathbb{Q}$ is obvious. $\endgroup$ – David Hill Feb 6 '17 at 17:42
  • $\begingroup$ @NoahSchweber is it $f: n -> n $ ? $\endgroup$ – JJ Ab Feb 6 '17 at 17:46

An injection from the naturals to the rationals is just the identity function (every natural is a rational).

For an injection from the rationals to the naturals, do the following. If $x\in\mathbb Q$ then $x=p/q$ for some $p,q$ with no common factor, $p\in\mathbb Z$ and $q\in\mathbb Z+$, and these values of $p$ and $q$ are uniquely determined. Write $f(x)=2^p\times 3^q$ if $p\geq 0$ and $f(x)=2^{-p}\times 3^q\times 5$ if $p<0$. This is an injection from $\mathbb Q$ to $\mathbb N$.

It is possible to define a bijection between the two, but it is more fiddly to do so.

  • $\begingroup$ I had a question, what do you mean when you say p and q are uniquely determined? $\endgroup$ – JJ Ab Feb 6 '17 at 19:48
  • $\begingroup$ I meant that once you choose $x\in Q$ there's only one possible way of writing it as $p/q$ that satisfies those conditions (i.e. lowest terms with $q>0$). So what I've written does actually define a function (in other words if we both start from the same $x$ and apply this definition we'll both get the same value of $f(x)$). $\endgroup$ – Especially Lime Feb 6 '17 at 22:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.