Section 3: Problem 12 Solution

Working problems is a crucial part of learning mathematics. No one can learn topology merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.

James R. Munkres

Let $\mathbb{Z}_{+}$ denote the set of positive integers. Consider the following order relations on $\mathbb{Z}_{+}\times\mathbb{Z}_{+}$ :

(i) The dictionary order.

(ii) $(x_{0},y_{0})<(x_{1},y_{1})$ if either $x_{0}-y_{0}<x_{1}-y_{1}$ or $x_{0}-y_{0}=x_{1}-y_{1}$ and $y_{0}<y_{1}$ .

(iii) $(x_{0},y_{0})<(x_{1},y_{1})$ if either $x_{0}+y_{0}<x_{1}+y_{1}$ , or $x_{0}+y_{0}=x_{1}+y_{1}$ and $y_{0}<y_{1}$ .

In these order relations, which elements have immediate predecessors? Does the set have a smallest element? Show that all three order types are different.

The following Figure 1↓ illustrates the orders.

Figure 1 The three orders on $\mathbb{Z}_{+}\times\mathbb{Z}_{+}$ .

Immediate predecessors. (i) In the dictionary order every element $(x,y)$ , $y>1$ , has an immediate predecessor $(x,y-1)$ , while $(x,1)$ does not (if $(x',y')<(x,1)$ then $x'<x$ , and $(x',y')<(x',y'+1)<(x,1)$ ).

(ii) Suppose $(x',y')<(x,y)$ . Consider two cases. If $x>1$ and $y>1$ , then $(x',y')\le(x-1,y-1)<(x,y)$ (either $x'-y'=x-y$ $=(x-1)-(y-1)$ and $y'\le y-1$ , or $x'-y'<x-y$ $=(x-1)-(y-1)$ ), hence, the immediate predecessor of $(x,y)$ in this case is $(x-1,y-1)$ . If, on the other hand, $x=1$ or $y=1$ , then $x'-y'<x-y$ (if $x'-y'=x-y$ then $y'<y$ and $x'<x$ , one of which is not possible), and, hence, $(x',y')<(x'+1,y'+1)<(x,y)$ , i.e. if $x=1$ or $y=1$ , there is no immediate predecessor.

(iii) Suppose $(x',y')<(x,y)$ . Consider two cases. If $y>1$ , then $(x',y')\le(x+1,y-1)<(x,y)$ (either $x'+y'=x+y$ $=(x+1)+(y-1)$ and $y'\le y-1$ , or $x'+y'<x+y$ $=(x+1)+(y-1)$ ). If $y=1$ , then $x'+y'<x+y$ (if $x'+y'=x+y$ then $y'<y=1$ ), hence, $x+y>2$ and $(x',y')\le(1,x+y-2)<(x,y)$ . Therefore, every element except $(1,1)$ has an immediate predecessor, namely, if $y>1$ , it is $(x+1,y-1)$ , and if $y=1,x>1$ , it is $(1,x+y-2)$ .

The smallest element. If there is a smallest element, then it must be the least among those without an immediate predecessor (but not vice versa, of course).

In (i) it is $(1,1)$ and, indeed, it is the smallest.

In (ii) there is no smallest element without predecessor, as for every $(x,1)$ , we have $(1,2)<(x,1)$ , but for every $(1,y)$ , we have $(1,y+1)<(1,y)$ (another way to see that there is no smallest element in (ii): $(x,y+1)<(x,y)$ ).

In (iii) there is only one element without immediate predecessor, which is $(1,1)$ , and, as it is easy to see, it is the smallest element.

The order type. Given the answers for the previous questions, it is immediate that the order types are different. Indeed, if there is a bijective correspondence between two orders that preserves the order, then, as it is easy to see, it must also preserve immediate predecessors and smallest elements. However, from this point of view, the structure of each order is different.

Order	The number of elements without the immediate predecessor	Whether the order has the smallest element
(i)	Countable	+
(ii)	Countable	-
(iii)	1	+

In fact, the order type of the order (ii) is that of the dictionary order on $\mathbb{Z}\times\mathbb{Z}_{+}$ . And the order type of the order (iii) is that of $\mathbb{Z}_{+}$ .

Indeed, imagine, first, the dictionary order on $\mathbb{Z}\times\mathbb{Z}_{+}$ , which is the order in (i) extended to the left for all $x$ ’s. Now, take this dictionary order, and place it into the positive corner as in (ii). I.e. a point $(x,1)$ goes to the point $(x+1,1)$ if $x\ge0$ , or $(1,1-x)$ if $x<0$ . We kind of bended the line $(x,1)$ of the dictionary order to fit it into the corner. Now, for each point $(x,1)$ of the original order, we take all points above it and place them to the diagonal that starts from the point where the point $(x,1)$ was placed. For example, $(0,n)$ becomes $(n,n)$ , $(1,n)$ becomes $(1+n,n)$ , $(-1,n)$ becomes $(n,1+n)$ etc. I hope you can see how the dictionary order on $\mathbb{Z}\times\mathbb{Z}_{+}$ becomes the order in (ii) (see Figure 1↑).

If not, then here is a formal bijective correspondence: $f(x,y)=(\max(0,x)+y,\max(0,-x)+y)$ . Let denote it as $f(x,y)=(a_{x,y},b_{x,y})$ . Note that $a_{x,y}-b_{x,y}=\max(0,x)-\max(0,-x)=x$ for all $x$ , so that in the dictionary order $(x,y)<(x',y')$ iff $x<x'$ , or $x=x'$ and $y<y'$ iff $a_{x,y}-b_{x,y}<a_{x',y'}-b_{x',y'}$ or $a_{x,y}-b_{x,y}=a_{x',y'}-b_{x',y'}$ and $x=x',y<y'$ , i.e. $b_{x,y}<b_{x',y'}$ , iff in the order (ii) $f(x,y)=(a_{x,y},b_{x,y})$ $<(a_{x',y'},b_{x',y'})=f(x',y')$ .

Now, consider $\mathbb{Z}_{+}$ . Place $1$ to $(1,1)$ , $2$ to $(2,1)$ and $3$ to $(1,2)$ , then $4$ , $5$ and $6$ to $(3,1)$ , $(2,2)$ and $(1,3)$ , correspondingly, and continue this way to get exactly the order (iii) illustrated in Figure 1↑. A more formal bijective correspondence between the two is also, of course, possible.

Subpages

Section 3: Problem 12 Solution

Section 3: Problem 12 Solution