# Show that $F:\mathbb N \to \mathbb Q_{>0}$ is bijective.

Let $\Bbb {P} = {p_1,p_2,...}$ denote the set of all prime numbers, i.e., $p_1 = 2, p_2 = 3, p_3 = 5, p_4 = 7, p_5 = 11$ and so on. For every $n ∈ \Bbb {N}$ represent $n$ as the product of its prime factors to some powers: $$n=\prod_{i=1}^\infty {p_i^{a_i}}$$ where all but finitely many $a_i$'s are $0$. For example $4116=2^2\cdot3^1\cdot5^0\cdot7^3\cdot11^0\cdot13^0...$

Define $F:\mathbb N \to \mathbb Q_{>0}$ by $$F(n) = F\left(\prod_{i=1}^\infty {p_i^{a_i}}\right) = \prod_{i=1}^\infty {p_i^{f(a_i)}}$$ where $f(a_i) = (-1)^{a_i-1}\lfloor\left(\frac{a_i+1}{2}\right)\rfloor$ for $a_i \in \Bbb N$ which is a bijection $f:\Bbb N \to \Bbb Z$

Now I need to prove that $F$ is a bijection. I have already proven that $f$ is a bijection so that can be assumed. I figured I would do the usual thing to show injective: let $n,m\in\Bbb N$ and suppose $F(n)=F(m)$ then show that this implies $n=m$. I just am not sure how to go about doing this. should I define $m\in\Bbb N$ as $m=\prod_{i=1}^\infty {p_i^{b_i}}$ to show this? Or perhaps I should try a completely different approach?

• Do you mean you proved that $f\colon\mathbb N\to\mathbb Z$ is a bijection? – Wolfram Jan 29 '17 at 20:57
• yes, since the $f$ I described maps $\Bbb N \to \Bbb Z$ – Jordan Peek Jan 29 '17 at 21:05
• I edited, not sure if that clears up any of the confusion – Jordan Peek Jan 29 '17 at 21:08

For any non-zero element of $\mathbb N$ there is a unique prime factorization of the kind $p_1^{a_1}\cdots p_s^{a_s}$, where $a_i\in\mathbb N$ (I assume $0\in\mathbb N$). Analogically, for any element of $\mathbb Q_{>0}$ there is a unique prime factorization of the same kind but with $a_i\in\mathbb Z$. To prove this use the uniqueness of representation in the form $p/q$, where $p,q$ are coprime positive integers, and the prime factorization theorem in $\mathbb N$. Prime factors of $q$ will give negative prime powers and those of $p$ - positive.

Now if you have any bijection $f\colon\mathbb N\to\mathbb Z$, the map $F$ described in the question is a bijection. This is pretty straitforward: if $m\in\mathbb Q_{>0}$, consider the prime factorization of this number $p_1^{a_1}\cdots p_s^{a_s}$. Then $p_1^{f^{-1}a_1}\cdots p_s^{f^{-1}a_s}$ is a pre-image of $m$ by definition, so $F$ is surjective. If there are two pre-images, consider their factorizations and show by the bijectivity of $f$ and uniqueness of the factorization of the image that if their images are equal, then they are equal themselves.

The fundamental theorem of arithmetic generalizes to positive rational numbers. If $q\in\mathbb{Q}_{>0}$, then there exists a unique sequence of integers $(e_k)_{k\ge1}$, with only a finite number of nonzero entries, such that $$q=\prod_{k\ge1}p_k^{e_k}$$ The trick for existence is, given $a/b$ with $a$ and $b$ coprime positive integers, is to decompose $ab$ into a product of prime powers and then switching signs for the the prime factors in $b$. Proving the uniqueness should be easy.

A consequence of this is that if $f\colon\mathbb{N}\to\mathbb{Z}$ is a map sending $0$ to $0$, we can define $$F\colon\mathbb{N}_{>0}\to\mathbb{Q}_{>0}$$ by $$F(n)=\prod_{k\ge1}p_k^{f(a_k)},\qquad n=\prod_{k\ge1}p_k^{a_k}$$ It is well defined by uniqueness of factorization in $\mathbb{N}_{>0}$.

Also $F$ turns out to be a bijection as soon as $f$ is a bijection. Suppose it is the case.

If $q=\prod_{k\ge1}p_k^{e_k}$, then consider $$n=\prod_{k\ge1}p_k^{f^{-1}(e_k)}$$ and, by definition, $F(n)=q$. For injectivity, use the generalized uniqueness of a factorization mentioned at the beginning.

Now you have just to prove that the given $f$ is a bijection sending $0$ to $0$.

Note that $f$ can be more easily described as $$f(a)=\begin{cases} -a/2 & \text{if a is even}\\[4px] (a+1)/2 & \text{if a is odd} \end{cases}$$