Example 2, Sec 7 in Munkres' TOPOLOGY 2nd ed: How to show that $\mathbb{Z}_+ \times \mathbb{Z}_+$ is countable?

Question

We need to show that there is a bijection $h \colon \mathbb{Z}_+ \times \mathbb{Z}_+ \to \mathbb{Z}_+$. For this purpose, Munkres define a subset $A$ of $\mathbb{Z}_+ \times \mathbb{Z}_+$ as follows: $$A \colon= \{ \ (x,y) \in \mathbb{Z}_+ \times \mathbb{Z}_+ \ \colon \ y \leq x \ \}.$$ Then he defines the maps $f \colon \mathbb{Z}_+ \times \mathbb{Z}_+ \to A$ and $g \colon A \to \mathbb{Z}_+$ as follows: $$f(x,y) \colon= (x+y-1, y) \ \ \ \forall \ \ (x,y) \in \mathbb{Z}_+ \times \mathbb{Z}_+,$$ and $$g(x,y) \colon= \frac{(x-1)x}{2} + y \ \ \ \forall \ \ (x,y) \in A.$$ That the map $f$ is a bijection is clear to me.

How to show (directly) that the map $g$ is also a bijection?

It is clear intuitively.

Once we show that $g$ is indeed a bijection, then the map $h$ could be defined as $$h \colon= g \circ f.$$

My effort:

For all $(x,y) \in A$, we note that $$g(x,y) = y+ \sum_{i=1}^{x-1} i.$$

What next?

Answer 1

Since you asked me to answer here: http://dbfin.com/topology/munkres/chapter-1/section-7-countable-and-uncountable-sets/#comment-2337405063.

To formally see that $g$ is bijective, note that

a) for every $x,y\in \mathbb{Z}_+$, $g((x,y))\in\mathbb {Z}_+$;

b) $g((1,1))=1$;

c) if $y<x$ then $g(x,y)+1=g((x,y+1))$; and

d) for every $x\in \mathbb{Z}_+$, $g(x,x)+1=g((x+1,1))$.

a)-d) show that the image set of $g$ is an inductive subset of $\mathbb{Z}_+$, i.e. it is $\mathbb{Z}_+$, and $g$ is surjective. They also show that $g$ is injective, as for $x<x'$ and $y<y'$, $g(x,y)<g(x,y')<g(x',1)$.

Answer 2

Your observation that $$g(x,y) = y+\sum_{i=1}^{x-1}i$$ is good.

Define $T(x) = \sum_{i=1}^x i$ to be the $x$'th triangular number. The question is then if any integer $z\in\mathbb{Z}_+$ can be written uniquely as the sum of a triangular number $T(x-1)$ and an integer $y\leq x$.

That $g$ is surjective is clear: Let $z\in\mathbb{Z}_+$, choose $x$ with $T(x-1)<z\leq T(x)$, and set $y = z-T(x-1)$. Since $T(x)-T(x-1) = x$, and since $z\leq T(x)$, we have $y\leq x$. Also, $$z = y + T(x-1).$$ Now it also makes intuitively sense that this decomposition is unique: Take the largest triangular number $T(x-1)$ strictly less than $z$, and let $y$ be the remaining part. As for a more rigorous argument for uniqueness, suppose that $$ z = y_1+T(x_1-1),$$ $$ z = y_2+T(x_2-1),$$ where $y_1\leq x_1$ and $y_2\leq x_2$, and suppose further for contradiction that $x_1<x_2$. Then $$T(x_2-1) - T(x_1-1) = y_1-y_2,$$ but $T(x_2-1)-T(x_1-1) = (x_2-1)+\cdots+x_1$, and since $y_1\leq x_1$, we must have $$(x_2-1)+\cdots+x_1 = y_1-y_2<x_1,$$ which is a contradiction.

Answer 3

This works, but (in my opinion) there's an easier way to show countability: given a pair of positive integers $a, b$, let $h(a, b)=2^a(2b+1)$ - that is, the $a$th power of 2 times the $b$th odd number. This is a bijection from $\mathbb{Z}_+\times\mathbb{Z}_+$ to $\mathbb{Z}_+$.

• Surjectivity: Given $c\in\mathbb{Z}_+$, let $a$ be the largest power of 2 which divides $c$, and let $k={c\over 2^a}$. Then $k$ is odd, so $k=2b+1$ for some $b$; then $c=h(a, b)$.

• Injectivity: Given $a, a', b, b'\in\mathbb{Z}_+$, if $h(a, b)=h(a', b')$, then we must have $a=a'$; otherwise, suppose $a<a'$, then $2b+1=2^{a'-a}(2b+1)$, which is a contradiction since $2b+1$ is odd but $a'-a>0$. But if $a=a'$, then $b=b'$ after dividing both sides by $2^a$.