Exercise 10.9

Proof. Consider any positive integer $n$. Define a sequence $a=\left(a_1,a_2,\dots \right)$ in $A$ by

We claim that the section $S_a$ has the same order type as ${({\mathbb{Z}}_{\text{+}})}^n$. To show this we construct an order-preserving mapping $f:S_a\to {({\mathbb{Z}}_{\text{+}})}^n$. So consider any sequence $x=\left(x_1,x_2,\dots \right)$ in $S_a$ so that $x<a$. Now define a finite sequence where $y_i=x_{n-i+1}$ for any $i\in \left\{1,\dots ,n\right\}$, and set $f(x)=y=\left(y_1,\dots ,y_n\right)$. Clearly $f(x)\in {({\mathbb{Z}}_{\text{+}})}^n$ since $x\in A\subset {({\mathbb{Z}}_{\text{+}})}^{\omega }$.

Here we must digress for a moment and show that, for all $x=\left(x_1,x_2,\dots \right)\in A$, $x\in S_a$ if and only if $x_i=1$ for all $i>n$.

$\text{(⇒)}$ We show the contrapositive. So suppose that there is an $i>n$ where $x_i\ne 1$. Moreover let $i$ be the greatest such index, which must exist since $x$ must end in an infinite string of 1’s. Clearly then the fact that $x_i\in {\mathbb{Z}}_{\text{+}}$ and $x_i\ne 1$ means that $x_i>1$. Now, if $i>n+1$ then we have that $x_i>1=a_i$ and $x_j=1=a_j$ for all $j>i$ so that clearly $x>a$. If $i=n+1$ and $i>2$ clearly $x_i>2=a_{n+1}=a_i$ and $x_j=1=a_j$ for all $j>i$ so that again $x>a$. Lastly suppose that $i=n+1$ but that $x_i=2=a_{n+1}=a_i$. If $x_j=1=a_j$ for all $j<i=n+1$ then clearly $x=a$. On the other hand, if there is a $1\le j<n+1=i$ where $x_j\ne 1$ then let $j$ be the greatest such index. Then we clearly have $x_j>1=a_j$ while $x_k=a_k$ for all $k>j$ so that $x>a$. Therefore in every one of these exhaustive cases, we have that $x\ge a$ so that $a\notin S_a$.

$\text{(⇐)}$ Now suppose that $x_i=1$ for every $i>n$. Then we have that $x_{n+1}=1<2=a_{n+1}$ while $x_j=1=a_j$ for all $j>n+1>n$ so that $x<a$ and hence $x\in S_a$.

Now, returning to the main proof, we first show that $f$ as defined above preserves order. To this end let $\prec$ denote the dictionary order on ${({\mathbb{Z}}_{\text{+}})}^n$. Now consider any $x=\left(x_1,x_2,\dots \right)$ and $x^{\prime }=\left(x_1^{\prime },x_2^{\prime },\dots \right)$ in $S_a$ where $x<x^{\prime }$. Also let $y=f(x)$ and $y^{\prime }=f(x^{\prime })$. Then there is an $m\in {\mathbb{Z}}_{\text{+}}$ where $x_m<x_m^{\prime }$ and $x_i=x_i^{\prime }$ for all $i>m$. We also have by what was shown above that $x_i=1x_i^{\prime }$ for all $i>n$ since $x,x^{\prime }\in S_a$. So it has to be that $m\le n$. It then follows from the fact that $1\le m\le n$ that $1\le n-m+1\le n$ as well. Thus we have

For any $1\le j<n-m+1$ we have that $n-j+1>m$ so that

Thus by definition we have that $f(x)=y\prec y^{\prime }=f(x^{\prime })$, which shows that $f$ preserves order since $x$ and $x^{\prime }$ were arbitrary. Note that this also clearly shows that $f$ is injective.

To show that $f$ is also surjective, consider any $y=\left(y_1,\dots ,y_n\right)\in {({\mathbb{Z}}_{\text{+}})}^n$. Now define a sequence

so that clearly $x=\left(x_1,x_2,\dots \right)\in S_a$ by what was shown above. Now let $y^{\prime }=\left(y_1^{\prime },\dots ,y_n^{\prime }\right)=f(x)$. Consider any $1\le i\le n$ and let $j=n-i+1$ so that also $n-j+1=i$, noting also that $1\le j\le n$. Then we have

by the definition of $f$. Since $i$ was arbitrary this shows that $f(x)=y^{\prime }=y$, which shows that $f$ is surjective since $y$ was arbitrary.

The existence of $f$ therefore shows that $S_a$ and ${({\mathbb{Z}}_{\text{+}})}^n$ have the same order type. □

Proof. Consider any nonempty subset $B$ of $A$. Clearly, the sequence $(1,1,\dots )$ is the smallest element of $A$ and hence if it is in $B$ then it is also the smallest element of $B$. So suppose that $(1,1,\dots )\notin B$ so that, for every $x\in B$ there is a unique greatest $n_x\in {\mathbb{Z}}_{\text{+}}$ where $x_{n_x}>1$ but $x_i=1$ for all $i>n_x$. So let $I=\left\{n_x\mid x\in B\right\}$, noting that $B\ne \varnothing$ implies that $I\ne \varnothing$ as well. Thus $I$ is a nonempty subset of ${\mathbb{Z}}_{\text{+}}$ and hence has a smallest element $n$. If we then let $B_n$ be the set of sequences $x\in B$ where $x_n>1$ but $x_i=1$ for all $i>n$, then the fact that $n\in I$ clearly implies that $B_n\ne \varnothing$. Also, if we define the sequence

as in part (a) then it follows from what was shown there that $B_n\subset S_a$. Moreover, it was shown that $S_a$ has the same order type as the dictionary order of ${({\mathbb{Z}}_{\text{+}})}^n$, which we know to be a well-ordering. Hence $S_a$ must also be well-ordering so that $B_n$ has a smallest element $b=\left(b_1,b_2,\dots \right)$ since it is a nonempty subset of $S_a$. We claim that $b$ is in fact the smallest element of all of $B$.

So consider any $x\in B$ so that $n_x\in I$. It then follows that $n\le n_x$ since it is the smallest element of $I$. If $n=n_x$ then we have that $x\in B_n$ so that $b\le x$ since it is the smallest element of $B_n$. If $n<n_x$ then we have that $b_{n_x}=1<x_{n_x}$ but $b_i=1=x_i$ for every $i>n_x>n$. This shows that $b<x$. Thus in all cases $b\le x$, which shows that $b$ is the smallest element of $B$ since $x$ was arbitrary. Since $B$ was arbitrary, this shows that $A$ is well-ordered as desired. □