An interesting bijection $\varphi: \mathbb{N}^+ \to \mathbb{Q}^+$
|
01-01-2013, 12:28 AM
Post: #1
|
|||
|
|||
An interesting bijection $\varphi: \mathbb{N}^+ \to \mathbb{Q}^+$
Define $\sigma: n \mapsto (p_n, q_n)$ as follows: $\quad\quad\quad \sigma(n) = (p_n, q_n)= \begin{cases} (1,1), & n = 1, \\ (p_{ \frac{n}{2}}, \; p_{\frac{n}{2}} + q_{\frac{n}{2}}), & 2\mid n > 1, \\ (p_{\lfloor \frac{n}{2} \rfloor} + q_{\lfloor \frac{n}{2} \rfloor}, \; q_{\lfloor \frac{n}{2} \rfloor}), & 2\nmid n > 1\end{cases}$ and $\: \displaystyle{\quad \varphi(n) = \frac{p_n}{q_n} = \begin{cases} 1, & n = 1, \\ \frac{\varphi( \frac{n}{2} )}{1 + \varphi(\frac{n}{2})}, & 2 \mid n > 1 \\ 1 + \varphi(\lfloor \frac{n}{2} \rfloor), & 2 \nmid n > 1\end{cases}}$ Where $\lfloor x \rfloor$ is the integer part of $x$. Here are some examples: $\sigma(1) = (1,1),\, \sigma(2) = (1,2),\, \sigma(3) = (2, 1),\, \sigma(4) = (1,3),\, \sigma(5) = (3,2),\, \sigma(6) = (2,3),\, \sigma(7) = ..$ $\displaystyle{\varphi(1) = 1,\,\varphi(2) = \frac{1}{2},\, \varphi(3) = 2,\, \varphi(4) = \frac{1}{3},\, \varphi(5) = \frac{3}{2},\, \varphi(6) = \frac{2}{3},\, \varphi(7) = 3,\, \varphi(8) = \frac{1}{4}, \ldots}$ We need to prove that $\quad\quad\;$ (a) $\varphi$ is surjective: $\varphi(\mathbb{N}^+) = \mathbb{Q}^+$ $\quad\quad\;$ (b) $\varphi$ is injective: $(\varphi(m) = \varphi(n)) \implies (m = n)$ Proof (a) Let $\displaystyle{M = \{m \in \mathbb{N}^+ \mid \forall p \in \mathbb{N} \cap (0, m)\; (\gcd(p,m) = 1) \implies \bigg( \frac{p}{m}, \frac{m}{p} \in \varphi(\mathbb{N}^+)\bigg)\}}$ $\quad\quad\quad\quad$ Clearly $1 \in M$. Assume $\mathbb{N}^+ \ni k < m \implies k\in M$ for some $m > 1$ and $\quad\quad\quad\quad\, 1\le p < m,\, \gcd(p,m) = 1.$ Then $p, m -p \in M$ and $\gcd(p, m-p) = 1.\quad$ Thus $\quad\quad\quad\quad$ $\displaystyle{\varphi(k) = \frac{p}{m - p},\, \varphi(k') = \frac{m -p}{p}}$ for some $k,\; k'$ and so $\displaystyle{\varphi(2k) = \frac{p}{m},\,\varphi(2k' + 1) = \frac{m}{p}}$ $\quad\quad\quad\quad$ Therefore $m \in M$. Which means $M = \mathbb{N}^+$ and so $\displaystyle{\varphi(\mathbb{N}^+) = \mathbb{Q}^+ = \left\{\frac{p}{q} \mid p,\,q \in \mathbb{N}^+\right\}}$ $\quad\quad\;$ (b) Let $K = \{k \in \mathbb{N}^+ \mid (\varphi(m) = \varphi(n)) \wedge (m,n \le k) \implies (m = n)\}$, then $1\in K$. $\quad\quad\quad\quad$ Suppose $j > 1,\;$ and $\; i < j \implies i \in K$. If $\varphi(j) = \varphi(l) = a$ for some $l \le j$, then $\quad\quad\quad\quad\, 0< a \ne 1,\; j \equiv i \mod 2$ by the definition of $\varphi$ and $j > 1$. Hence $\displaystyle{\quad\quad\quad\quad\, a < 1 \implies \varphi(j/2) = \frac{a}{1 - a} =\varphi(l/2) \underset{\frac{j}{2} < j}{\implies} j/2 = l/2 \implies j = l}\quad$ and $\displaystyle{\quad\quad\quad\quad\, a >1 \implies \varphi\left(\frac{j - 1}{2}\right) = a - 1 =\varphi\left(\frac{l - 1}{2}\right) \implies \frac{j -1}{2} = \frac{l - 1}{2}\implies j = l}$ $\quad\quad\quad\quad$So $K = \mathbb{N}^+$. In other words, $\;\forall m,n \in\mathbb{N}^+\, (\varphi(m) = \varphi(n))\implies (m = n). \quad\square$ |
|||
01-01-2013, 12:44 AM
Post: #2
|
|||
|
|||
Remark: An interesting bijection $\varphi: \mathbb{N}^+ \to \mathbb{Q}^+$
Remark It is quite interesting: why it's not in the standard analysis text? |
|||
01-01-2013, 12:59 AM
Post: #3
|
|||
|
|||
Python Code: An interesting bijection $\varphi: \mathbb{N}^+ \to \mathbb{Q}^+$
Code: def nr(n): |
|||
01-01-2013, 01:18 AM
Post: #4
|
|||
|
|||
RE: An interesting bijection $\varphi: \mathbb{N}^+ \to \mathbb{Q}^+$
The following shows that when $n = 1172, q$ reaches $3$ digit the first time. And it's not $100$.
|
|||
01-02-2013, 09:35 AM
Post: #5
|
||||||||||||
|
||||||||||||
RE: An interesting bijection $\varphi: \mathbb{N}^+ \to \mathbb{Q}^+$
$\quad\quad$ This is to say that, start with $p_1 = q_1 = 1$, the reproduction(multiplication) pattern \[\begin{matrix} \frac{p}{q} \\ \swarrow \quad\quad \searrow \\ \frac{p}{p+q} \quad\quad \frac{p+q}{q} \end{matrix}\] $\quad\quad$ generates all positive rationals $\frac{p_n}{q_n}\;(\gcd(p_n,q_n) = 1)$. $\quad\quad$ And different hereditary paths determine different rationals.
|
||||||||||||
« Next Oldest | Next Newest »
|