Prove that $p:\omega \times \omega \to \omega$ defined by $p(i,j)=2^i(2j+1)-1$ is one-to-one and onto.

Question: Prove that $$p:\omega \times \omega \to \omega$$ defined by $$p(i,j)=2^i(2j+1)-1$$ is one-to-one and onto. Then show that if $$i\in m$$ and $$j \in n$$, then $$p(i,j) \in p(m,n)$$.

The book offers a hint as follows:

If $$1 ⋸ m$$, then $$m-1=\bigcup m$$. To prove $$p$$ is onto $$\omega$$, apply the Well-Ordering Principle to prove that for all $$n \in \omega$$, if $$1 ⋸ n$$, then $$n=2^i(2j+1)$$ for some $$i\in \omega$$ and $$j\in \omega$$. Note: if $$k\in \omega$$, then $$k=k^+-1$$.

I genuinely have no idea where to start with the problem, and I don't understand the hint at all. We've gone through arithmetic and order on the set of natural numbers $$\omega$$, but I don't see how this relates. Any help is appreciated.

Edit: I see that for $$i=0$$ and $$i=1$$, we can represent every odd and even natural number, and thus, every natural number in general. Hence, $$p$$ is onto $$\omega$$. I'm still clueless for injectivity and the second part of the question.

• $i=0$ and $i=1$ are not enough to represent all the natural numbers. Consider how you would represent $3$. – Andreas Blass Mar 18 at 3:47
• I take it the $-1$ in the formula is just so one can represent $0.$ Every positive integer is uniquely a power of $2$ ($0$ power for odds) times an odd positive number. So I don't think you can get away without allowing arbitrary $i.$ – coffeemath Mar 18 at 3:48
• @coffeemath Indeed, if you could get away without using all possible values of $i$, then $p$ would not be one-to-one; the values produced by unneeded values of $i$ would be duplicated by needed ones. – Andreas Blass Mar 18 at 3:51