Prob. 12, Sec. 3 in Munkres' TOPOLOGY, 2nd ed: How to relate these order relations?

59 Views Asked by At

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

(i) The dictionary order: $x_0 \times y_0 \prec x_1 \times y_1$ if $x_0 < x_1$, or if $x_0 = x_1$ and $y_0 < y_1$.

(ii) $x_0 \times y_0 \prec x_1 \times y_1$ if $x_0 - y_0 < x_1 - y_1$, or if $x_0 -y_0 = x_1 - y_1$ and $y_0 < y_1$.

(iii) $x_0 \times y_0 \prec x_1 \times y_1$ if $x_0 + y_0 < x_1 + y_1$, or if $x_0 +y_0 = x_1 + y_1$ and $y_0 < y_1$.

Then how to show that the order in (ii) is the same as the dictionary order on $\mathbb{Z} \times \mathbb{Z}_+$?

And, how to show that the order in (iii) is the same as the order on $\mathbb{Z}_+$?

It would suffice in each case to find an order-preserving bijection.

1

There are 1 best solutions below

0
On

For (ii), a bijection is: $$ (x, y) \mapsto (x - y, y)\colon \mathbb{Z}_{+}^2 \to \mathbb{Z} \times \mathbb{Z}_{+} $$ $\mathbb{Z} \times \mathbb{Z}_{+}$ with the dictionary order consists of a sequence of blocks $\dots Z_{-m} ... Z_{-1} Z_0 \: Z_1 \dots Z_n \dots$ in the order shown, where each block $Z_k, k \in \mathbb{Z}$ is a copy of $\mathbb{Z}_{+}$ with its natural order. $Z_k$ is the image of all $(x,y)$ with $x-y = k$.

For (iii), a bijection is: $$ (x, y) \mapsto {\frac{(x+y-1)(x+y-2)} 2} + y\colon \mathbb{Z}_{+}^2 \to \mathbb{Z}_{+} $$ Here, ${\frac{(x+y-1)(x+y-2)} 2}$ is the number of pairs $(v, w) \in \mathbb{Z}_{+}^2$ with $v + w < x + y)$. Where $n = x + y$ this is the number of predecessors of $(n-1,1)$ in the ordering on $\mathbb{Z}_{+}^2$.