Given a coding function between pairs of naturals and naturals:
$$ \begin{gather} \phi: \mathbb{N} \times \mathbb{N} \to \mathbb{N} \\ \phi: m, n \mapsto 2^n(2m + 1) - 1 \end{gather} $$
The notes attempt to show bijectivity by first showing injectivity and then surjectivity. I have no problem with the injectivity proof. However, I am not understanding the surjectivity proof. It is laid out below:
For a given natural number $y \in \mathbb{N}$ we show how to construct $n$ and $m$ such that $\phi(n, m) = y$.
This is a relatively straightforward reversal of the function. We begin by noting that we assume $y = 2^n(2m + 1) − 1$ so the number $y + 1$ is of the form $a \times b$ where $a$ is an even number and $b$ is an odd number.
- We can find $a$ by viewing $y + 1$ in binary and taking the longest chain of least-significant bits that are $0$.
- We can find $b$ by dividing $y + 1$ by $2$ until it becomes odd.
In either case we can directly get $n$ from $a$ as $n = \log_2(a)$ (or the number of bits in $a$), and $m$ from $b$ as $m = \frac{b−1}{2}$.
The context for the binary usage is that previously, it was asserted that any output from this function has a binary form of: $m$ in binary, followed by a $0$, followed by $n$ $1$s, and this easy conversion method was offered as a preliminary reason to be confident in $\phi$'s bijectivity.
My problem is with the bold part. It does not seem like a safe assumption to make that $a$ is odd and $b$ is even -- because this $\text{odd} \times \text{even}$ product can only describe the even numbers, never the odd numbers. For example, if $y + 1 = 1$ then $n = 0$ and so $2^n$ must be $1$ (which is odd). In fact, $2^n = 1$ has to be the case for every odd $y + 1$ we wish to express. In this case, both $a$ and $b$ must be odd, and so $\log_2(a) \notin \mathbb{N}$ in this instance (well, except for $a=1$).
Am I correct in concluding this proof's assumption is flawed?
Clarification: In this instance, $0 \in \mathbb{N}$. It is considered a natural.