Example of a map from the natural numbers to the positive rational numbers less than 1

Question

I want an example of a bijective function $f:\mathbb{N} \to \{n \in \mathbb{Q}:0<n<1\}$

There is already a question about an example of a map between $\mathbb{N}$ and $\mathbb{Q}$.

I am not really a layperson but you can approximate me as a layperson. So I cannot derive an example for this.

MOTIVATION:

a few days I was thinking about some crazy functions and roots of those function. The weierstrass factorization theorem also says that any continuous function can be written as the product involving its roots.

Yesterday I saw a video on the product formula of $\sin(x)$.

And I started wandering that can a function have roots which are all rational numbers or maybe roots which all positive rational numbers less than 1.

To get started at all I have to start here

$$\prod_{n=1}^\infty\left(x-a_nQ_n \right)$$

Where $Q_n$ is an example of a bijective function $f:\mathbb{N} \to \{n \in \mathbb{Q}:0<n<1\}$

Answer 1

Let $S$ be the set of all $(x,y)\in \Bbb N^2$ such that $x<y$ and $\gcd(x,y)=1.$ For $q\in \Bbb Q$ with $0<q<1$ let $f(q) =(x,y)\in S$ such that $q=x/y.$ Then $f:\Bbb Q\cap (0,1)\to S$ is a bijection.

Consider the reverse-lexicographic order (i.e. backwards-dictionary order) $<^*$ on $S.$ That is, if $(x_1,y_1)$ and $(x_2,y_2)$ are in S then $(x_1,y_1)<^* (x_2,y_2)$ iff

(i) $\; y_1<y_2$ or (ii) $\; y_1=y_2 \land x_1<x_2.$

Observe that $<^*$ is a linear ("total") order.

Now for any $n\in\Bbb N$ there is exactly one $z\in S$ such that the set $$T(z)=\{w\in S: w=z\lor w<^*z\}$$ has exactly $n$ members (See Appendix below).

So for $q\in \Bbb Q$ with $0<q<1,$ let $g(q)=n$ iff $T(f(q))$ has exactly $n$ members. Then $g: \Bbb Q\cap (0,1)\to\Bbb N$ is a bijection. (Recall $f$ from the 1st paragraph).

Appendix. For $y'\in \Bbb N$ let $S(y')=\{(x,y')\in S\}.$ Then $S(y')$ is finite, with at most $y'-1$ members. So if $z=(x,y)\in S$ then $T(z)\subseteq \cup \{S(y'): y'\le y\}$ so $T(z)$ is finite. Now we have

(a). If $z$ and $z'$ are in $S$ with $z<^*z'$ then the finite set $T(z)$ is a proper subset of the finite set $T(z')$ so $T(z)$ has fewer members than $T(z').$

(b). $\;(1,2)$ is the $<^*$-least member of $S,$ so $T((1,2))$ has just one member.

(c). If $(x,y)\in S$ then there is a $<^*$-least $w\in S$ such that $(x,y)<^*w,$ namely

(c-i). $\; w=(x',y)$ where $x'$ is the least $x''>x$ such that $(x'',y)\in S$ IF such an $x''$ exists, or

(c-ii). $\; w=(1,y+1)$ if there is no such $x''$ as in (c-i).

And if $T((x,y))$ has $n$ members then $ T(w)$ has $n+1$ members.

So by induction on $n\in \Bbb N,$ by (b) and (c), for every $n$ there exists some $z\in S$ such that $T(z)$ has $n$ members; By (a) there is only one such $z.$

Remark: You may have noticed that $<^*$ is a well-order. That is, if $\emptyset\ne U\subseteq S$ then $U$ has a $<^*$-least member. If $<^*$ is a well-order on an infinite set $S$ and if $T(z)$ (as defined above) is finite for each $z\in S$ then $(S,<^*)$ is order-isomorphic to $(\Bbb N,<).$ The first few members of $S$ in $<^*$-increasing order are $(1,2),(1,3),(2,3),(1,4),(3,4),(1,5),...,$ corresponding to the rationals $1/2,1/3,2/3,1/4,3/4,1/5,...$

Answer 2

Although such functions exist, it is not easy (maybe not possible) to get a nice pretty formula for one. You are not going to get anything as simple as the function in lisyarus's comment:

$$f(n) = \frac{1}{n + 2}$$

A common way to demonstrate the bijection is to enumerate the rationals in a systematic way e.g.

$$ \frac{1}{2}, \frac{1}{3}, \frac{2}{3}, \frac{1}{4}, \frac{2}{4}, \frac{3}{2}, \frac{1}{5}, \frac{2}{5}, \frac{3}{5}, \frac{4}{5}, . . .$$

So, I list all of the $\frac{n}{2}$ rationals (all one of them) then all of the $\frac{n}{3}$, then $\frac{n}{4}$, etc. I map $1$ to the first in my list, $2$ to the second,etc. With some effort, you might be able to develop a formula for this. You could easily calculate what $1000000$ mapped to without calculating all of the previous terms. It could be coded simply and efficiently in most programming languages.

However, there is a problem. The function is clearly surjective but it is not injective as, even in my short sample above, $1$ maps to $\frac{1}{2}$ and $5$ maps to $\frac{2}{4}$ which is the same. So, we need to eliminate these duplicates. This is clearly possible but it is much harder to jump to $1000000$ without calculating all previous terms (it is beyond my skills in number theory).

A key point here is that to a modern mathematician, a function does not necessarily have a nice pretty formula. In some cases, we might even prove that a function exists but have no way to calculate it.

It is quite common that it is easy to find an injection from a set $A$ to another set $B$ so that intuitively $A$ is smaller than or the same size as $B$ but also you can find an injection the other way. It could be that neither function is surjective so intuitively $A$ is strictly smaller than $B$ and $B$ is strictly smaller than $A$. You need to learn to accept this with infinite sets. In fact, it is characteristic of them. The map: $n \rightarrow n + 1$ naively proves that $\mathbb{N}$ is smaller than itself. Now, back to the case of an injection in both directions. There is a very useful theorem: Schröder–Bernstein theorem which proves that, in this case, a bijection exists. So, once you have found an injection in both directions you may invoke this theorem and stop without calculating an explicit bijection.

A similar result applies to the case of a surjection in both directions but this requires the Axiom of Choice and hence is not so basic.