Prob. 9, Sec. 10 in Munkres' TOPOLOGY, 2nd ed: How to verify transitivity for anti-dictionary order? Let $A$ denote the set of all the sequences of positive integers each of which ends in an infinite string of $1$s. For any two elements $x, y \in A$, let's define $x < y$ if there is some positive integer $n$ such that $x_n < y_n$ and $x_i = y_i$ for $i> n$. 
Then how to show that this relation $<$ defines a total order on $A$? 
How to show that $A$ is well-ordered under this relation? 
My effort: 
The non-reflexivity and trichotomy of the above relation are easy to verify. So, let's suppose that $x, y, z \in A$ such that $x < y$ and $y < z$. Then there are natural numbers $m$ and $n$ such that $a_m < b_m$ and $a_i = b_i$ for $i > m$, and $b_n < c_n$ and $b_i = c_i$ for $i > n$. 
If $m = n$, then $a_n < b_n < c_n$ and $a_i = b_i = c_i$ for $i > n$, and thus it follows that $a < c$. 
If $m < n$, then $a_n = b_n < c_n$ and $a_i = b_i = c_i$ for $i > n$, and so $a < c$ again. 
And, similarly for the case $n < m$. 
Is the above logic correct? 
Let $A_0$ be a non-empty subset of $A$. We need to show that $A_0$ has a smallest element. 
If $(1, 1, 1, \ldots) \in A_0$, then this is clearly the smallest element of $A$ and hence of $A_0$. So let's assume that $(1, 1, 1, \ldots) \not\in A_0$. 
What next? 
 A: Before doing this exercise I would introduce a notation. For all $x \in A \setminus \{ (1,1,1,1,\dots) \}$ define $F(x) = \max \{ n \ge 1 : x_{n+1} = x_{n+2} = \dots = 1\}$. Define moreover $F(1,1,\dots )=0$.
After that, we check that $A$ is totally ordered. Let $x,y \in A$. Then there are three cases:


*

*$F(x)<F(y)$: then $x < y$

*$F(x)>F(y)$: then $y < x$

*$F(x)=F(y)$: then you consider $$l= \max \{ n : x_n \neq y_n \}$$ if $x_l > y_l$ you have $y<x$, otherwise you have $x<y$.
In any case, we have $x < y$ or $y < x$, so the order is total.
Now, let $A_0 \subseteq A$ non empty. To show that $A_0$ has a smallest element proceed as follows: call
$$N=\min \{ F(x) : x \in A_0\}$$
 and $$A_0' = \{ x \in A_0 : F(x) = N \}$$
then clearly the minimum of $A_0$ (if it exists) must belong to $A_0'$.  But $A_0'$ can be embedded monotonically into $\{ 1, 2, \dots, N\}^{\Bbb{Z}_+}$ ordered with the anti-lexicographic order by
$$x \mapsto (x_1, \dots, x_N)$$
so $A_0'$ has a minimum, and this is the minimum of $A_0$.
