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.

  • $\begingroup$ $i=0$ and $i=1$ are not enough to represent all the natural numbers. Consider how you would represent $3$. $\endgroup$ – Andreas Blass Mar 18 at 3:47
  • $\begingroup$ 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.$ $\endgroup$ – coffeemath Mar 18 at 3:48
  • 1
    $\begingroup$ @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. $\endgroup$ – Andreas Blass Mar 18 at 3:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.