Exercise 7.2

Proof. To show that $f$ is injective, consider $n,m\in \mathbb{Z}$ where $n\ne m$.

Case: $n>0$. Then $f(n)=2n$, which is clearly even. If $m>0$, then clearly $f(n)=2n\ne 2m=f(m)$ since $n\ne m$. If $m\le 0$ then $f(m)=-2m+1=2(-m)+1$ is clearly odd so that it must be that $f(n)\ne f(m)$.

Case: $n\le 0$. Then $f(n)=-2n+1=2(-n)+1$, which is clearly odd. If $m>0$ then $f(m)=2m$ is even so that it has to be that $f(n)\ne f(m)$. If $m\le 0$ then $f(m)=-2m+1\ne -2n+1=f(n)$ since $n\ne m$.

Thus in every case $f(n)\ne f(m)$, which shows that $f$ is injective since $n$ and $m$ were arbitrary.

To show that $f$ is surjective, consider any $k\in {\mathbb{Z}}_{\text{+}}$. If $k$ is even then $k=2n$ for some $n\in {\mathbb{Z}}_{\text{+}}$. Hence $n>0$ (since $k>0$ and $n=k∕2$) so that $f(n)=2n=k$, noting that $n\in \mathbb{Z}$ since ${\mathbb{Z}}_{\text{+}}\subset \mathbb{Z}$. If $k$ is odd then $k=2m-1$ for some $m\in {\mathbb{Z}}_{\text{+}}$. So let $n=1-m$ so that clearly $n$ is an integer and

Thus $f(n)=-2n+1=-2(1-m)+1=-2+2m+1=2m-1=k$. This shows that $f$ is surjective since $k$ was arbitrary. Therefore we have shown that $f$ is a bijection as desired. □

Proof. First, it is not even clear that the range of $f$ is constrained to $A$, so let us show this. Consider any $(x,y)\in {\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ so that $f(x,y)=(x+y-1,y)$. Since $x\ge 1$ and $y\ge 1$, we have that $x+y\ge 1+1=2>1$ so that $x+y-1>0$ and hence $x+y-1\in {\mathbb{Z}}_{\text{+}}$. Thus clearly $f(x,y)=(x+y-1,y)\in {\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$. We also have

Therefore it is clear that $f(x,y)=(x+y-1,y)\in A$ by definition.

To show that $f$ is injective consider $(x,y)$ and $(x^{\prime },y^{\prime })$ in ${\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ where $f(x,y)=(x+y-1,y)=(x^{\prime }+y^{\prime }-1,y^{\prime })=f(x^{\prime },y^{\prime })$. Thus $x+y-1=x^{\prime }+y^{\prime }-1$ and $y=y^{\prime }$. Therefore $x+y-1=x^{\prime }+y^{\prime }-1=x^{\prime }+y-1$, from which it obviously follows that $x=x^{\prime }$ as well. Then $(x,y)=(x^{\prime },y^{\prime })$, which shows that $f$ is injective since $(x,y)$ and $(x^{\prime },y^{\prime })$ were arbitrary.

Now consider any $(z,y)\in A$ so that $(z,y)\in {\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ and $y\le z$. Let $x=z-y+1$ so that clearly $z=x+y-1$. We also have

so that $(x,y)\in {\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$. Since also we have $f(x,y)=(x+y-1,y)=(z,y)$, $f$ is surjective since $(z,y)$ was arbitrary. This completes the proof that $f$ is a bijection. □

Proof. First, we show that the range of $g$ is indeed ${\mathbb{Z}}_{\text{+}}$ since this is not obvious. Consider any $(x,y)\in A$ so that $(x,y)\in {\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ and $y\le x$. First, if $x$ is even then $x=2n$ for some $n\in \mathbb{Z}$. Then $g(x,y)=(x-1)x∕2+y=(2n-1)(2n)∕2+y=(2n-1)n+y$, which is clearly an integer. If $x$ is odd then $x=2n+1$ for some integer $n$ so that

which is also clearly an integer. We also have that $-y<0$ since $y>0$ so that

Since we have shown that $g(x,y)\in \mathbb{Z}$ as well, it follows that $g(x,y)\in {\mathbb{Z}}_{\text{+}}$.

Consider any $(x,y)\in A$ so that $(x,y)\in {\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ and $y\le x$. Then clearly

A simple inductive argument shows that $g(x,y)<g(x+n,1)$ for any $n\in {\mathbb{Z}}_{\text{+}}$. This was just shown for $n=1$. Then, assuming it true for $n$, we have that $g(x,y)<g(x+n,1)<g((x+n)+1,1)=g(x+(n+1),1)$, which completes the induction.

So consider any $(x,y)$ and $(x^{\prime },y^{\prime })$ in $A$ so that $(x,y)$ and $(x^{\prime },y^{\prime })$ are in ${\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$, $y\le x$, and $y^{\prime }\le x^{\prime }$. Also suppose that $(x,y)\ne (x^{\prime },y^{\prime })$ so that either $x\ne x^{\prime }$ or $y\ne y$. If $x=x^{\prime }$ then it has to be that $y\ne y^{\prime }$ so that clearly

If $x\ne x^{\prime }$ then we can assume that $x<x^{\prime }$. Then let $n=x^{\prime }-x$ so that clearly $n>0$ and $x^{\prime }=x+n$. By what was just shown, we have

since $1\le y^{\prime }$. Thus $g(x,y)\ne g(x^{\prime },y^{\prime })$. Since this is true in both cases, this shows that $g$ is injective since $(x,y)$ and $(x^{\prime },y^{\prime })$ were arbitrary.

To show that $g$ is also surjective, consider any $z\in {\mathbb{Z}}_{\text{+}}$. Define the set $B=\left\{x\in {\mathbb{Z}}_{\text{+}}\mid g(x,1)\le z\right\}$. First, we have that $g(1,1)=1\le z$ since $z\in {\mathbb{Z}}_{\text{+}}$ so that $1\in B$ and therefore $B\ne \varnothing$. If $z=1$ then clearly $z=1\le 1=g(1,1)=g(z,1)$. If $z\ne 1$ then we have

Now consider any $x,y\in {\mathbb{Z}}_{\text{+}}$ where $x<y$. It then follows from what was shown above that $g(x,1)\le g(x,y)<g(x+1,1)$. From this we clearly have that the function $g(x,1)$ is monotonically increasing in $x$, i.e. for $x,y\in {\mathbb{Z}}_{\text{+}}$, $x<y$ implies that $g(x,1)<g(y,1)$. By the contrapositive of this, $g(x,1)\ge g(y,1)$ implies that $x\ge y$. With this in mind, consider any $x\in B$ so $g(x,1)\le z\le g(z,1)$. Then this implies that $x\le z$, which shows that $z$ is an upper bound of $B$ since $x$ was arbitrary.

We have thus shown that $B$ is a nonempty set of integers that is bounded above. It then follows from Exercise 4.9 part (a) that $B$ has a largest element $x$. Now let $y=z-g(x,1)+1$, noting that, since $x\in B$,

and hence $y\in {\mathbb{Z}}_{\text{+}}$ so that $(x,y)\in {\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$. We also must have that $z<g(x+1,1)$ since otherwise we would have that $x+1\in B$, which would violate the definition of $x$ as being the largest element of $B$. Thus we have

so that $(x,y)\in A$.

Lastly, since $y=z-g(x,1)+1$, we clearly have

This shows that $g$ is surjective since $z$ was arbitrary, thereby completing the long and arduous proof that $g$ is a bijection. □