Recently, when I self-learnt Discrete Mathematics and Its Applications 8th by Kenneth Rosen, I did only the even-numbered exercises which the author offers the detailed description instead of the odd ones because the odd ones and the corresponding even ones are very similar.
I has some questions about exercise 9.6-38 which is related with the partial ordering and the lexicographic order. The problem is
Show that lexicographic order is a partial ordering on the set of strings from a poset.
The answer says (Here the book answer use $<$ instead of $\prec$ for the partial ordering, so I use the same convention as it)
Reflexivity is clear from the definition. To show antisymmetry, suppose that $a_1 \ldots a_m<b_1 \ldots b_n$, and let $t = min(m,n)$ . This means that either $a_1 \ldots a_t<b_1 \ldots b_t$ and $m < n$, so that $b_1 \ldots b_n\not<a_1 \ldots a_m$, or else $a_1 \ldots a_t<b_1 \ldots b_t$, so that $b_1 \ldots b_t \not< a_1 \ldots a_t$ and hence again $b_1 \ldots b_n\not<a_1 \ldots a_m$. Finally for transitivity, suppose that $a_1 \ldots a_m<b_1 \ldots b_n < c_1 \ldots c_p$. Let $t = min(m,n) , r = min(n,p) , s = min(m,p)$ , and $l = min(m,n,p)$ . Now if $a_1 \ldots a_l<b_1 \ldots b_l <c_1 \ldots c_l$ , then clearly $ a_1 \ldots a_m < c_1 \ldots c_p $ . Otherwise, without loss of generality we may assume that $ a_1 \ldots a_l = b_1 \ldots b_l $ . If $ l=t, $ then $ m<n $ and $m \le p$. Furthermore, either $ b_1 \ldots b_r < c_1 \ldots c_r $ , or $ b_1 \ldots b_r = c_1 \ldots c_r $ and $n < p$. In the former case, if $ r>l, $ then since $ p>m $ we have $ a_1 \ldots a_m < c_1 \ldots c_p $ , whereas if $ r=l, $ then $ a_1 \ldots a_l < c_1 \ldots c_l $ . In the latter case, $ a_1 \ldots a_s = c_1 \ldots c_s $ and $ m<p, $ so again $ a_1 \ldots a_m < c_1 \ldots c_p $ . If $ l<t, $ then we must have $ b_1 \ldots b_l < c_1 \ldots c_l $ , whence $ a_1 \ldots a_l < c_1 \ldots c_l $ .
My main confusion here is the "without loss of generality". Since the predicates are $a_1 \ldots a_m<b_1 \ldots b_n$ and $b_1 \ldots b_n < c_1 \ldots c_p$, the $b_1 \ldots b_l = c_1 \ldots c_l$ can be generalized from $a_1 \ldots a_l = b_1 \ldots b_l$ due to they are targeted at one assumed relation each. But $a_1 \ldots a_l = c_1 \ldots c_l$ may not because the relation between $a$ and $c$ is what to be proved.
But after some thoughts I seem to clear the confusion. Here is my understanding.
$b_1 \ldots b_l = c_1 \ldots c_l$: Here I offer my variant based on the book answer to help readers understand the book answer. $$ \text{assume } b_1 \ldots b_l = c_1 \ldots c_l.\\ t = min(m,n) , r = min(n,p) , s = min(m,p) ,l = min(m,n,p)\Rightarrow r,t\le l\\ \begin{cases} 1.\; l=r(\text{correspond to the original answer }l<t)\Rightarrow n<p,m\ge (r=n) \Rightarrow r=n\\ \Rightarrow t=n=r=l\\ \Rightarrow a_1 \ldots a_t<b_1 \ldots b_t\\ \Rightarrow \begin{cases} t=l(\text{similar to the original ans "if r = l, then ..."})&\Rightarrow a_1 \ldots a_l<b_1 \ldots b_l \Rightarrow a_1 \ldots a_l<c_1 \ldots c_l \Rightarrow a_1 \ldots a_m = c_1 \ldots c_p\\ t<l(\text{impossible})& \end{cases}\\ 2.\; l=min(m,r)<r\\ (\text{correspond to }l=t \text{ but }r=l\text{ there is included in case 1})\\ \Rightarrow (l=t) \wedge (p,n>m)\\ \Rightarrow \begin{cases} a_1 \ldots a_t<b_1 \ldots b_t &\Rightarrow a_1 \ldots a_l< c_1 \ldots c_l\Rightarrow a_1 \ldots a_m = c_1 \ldots c_p\\ a_1 \ldots a_t=b_1 \ldots b_t,m<n &\Rightarrow a_1 \ldots a_l = c_1 \ldots c_l\Rightarrow a_1 \ldots a_m = c_1 \ldots c_p \text{ due to }p>m \end{cases} \end{cases} $$
$a_1 \ldots a_l = c_1 \ldots c_l$: Since $a_1 \ldots a_l$ and $b_1 \ldots b_l$ must be substrings of $a_1 \ldots a_t$ and $b_1 \ldots b_t$, so $a_1 \ldots a_l$ can only be $\preccurlyeq b_1 \ldots b_l$, similarly for $b_1 \ldots b_l$ and $c_1 \ldots c_l$. Then since they are same length substrings, we can directly use transitive property of the poset. Then $a_1 \ldots a_l \preccurlyeq b_1 \ldots b_l \preccurlyeq c_1 \ldots c_l,a_1 \ldots a_l = c_1 \ldots c_l\Rightarrow a_1 \ldots a_l = b_1 \ldots b_l = c_1 \ldots c_l$. So it is included in the above case and the book one.
Q:
- Is my above interpretation of the "without loss of generality" right?
- Is there one elegant proof of the transitivity part in this problem?