        \problemdata       % Takes 5 *mandatory* arguments
        {posets}             % latex-friendly label for the prob.
        {relations}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {F01 PS4-1} % Usage (list ones you are aware of).
        {}        % Last revision info (author, date).


\begin{problem}
Let $R$ be the lexicographic (dictionary) ordering of strings
of symbols from a totally ordered alphabet as defined in Rosen p. 417.

\problempart Prove that $R$ is a total order.

\solution{
If $\alpha$, $\beta$ are strings, let us denote by
$\alpha\sqsubseteq\beta$ the fact that $\alpha$ is a \emph{prefix} of
$\beta$, i.e., that $\alpha\gamma=\beta$, for some $\gamma$.  Let us
also denote by $\alpha\restriction n$ the prefix of $\alpha$ of length
$n$. 

Then, the lexicographic order $R$ is such that 
$$
\alpha R \beta 
\:\iff\:
\alpha\sqsubseteq\beta 
\;\vee \;
\alpha\restriction t \prec \beta\restriction t
$$
where $t$ is the length of the shortest string. That is, $\alpha$ comes
before $\beta$ iff either it is a prefix of $\beta$ or its $t$-prefix
comes \emph{strictly} before the $t$-prefix of $\beta$ (in the
ordering of strings of length $t$, which we know is total). 

We first show that $R$ is a partial order. Reflexivity is obvious, and
antisymmetry is deduced easily: Suppose $\alpha R\beta$ and $\beta
R\alpha$. If any of the strings has its $t$-prefix strictly before the
$t$-prefix of the other string, then the latter one can't be a prefix
of the former; and it certainly cannot have its $t$-prefix strictly
before the $t$-prefix of the former string. Hence, the only
possibility is that both $\alpha \sqsubseteq \beta$ and
$\beta\sqsubseteq\alpha$, which implies $\alpha=\beta$.  

For transitivity, let's assume that $\alpha R\beta$ and 
$\beta R\gamma$, where $\alpha$, $\beta$, $\gamma$ are of 
length $m$, $n$, $l$, respectively, and $t=\min(m,n)$, 
$s=\min(n,l)$,  $r=\min(m,n,l)$. Then: 
\begin{itemize}
\item
If $\beta\sqsubseteq\gamma$, then $r=t$ and:
\begin{itemize}
\item If $\alpha\sqsubseteq\beta$, then $\alpha$ is also a prefix of
$\gamma$.
\item
If $\alpha\restriction t\prec\beta\restriction t$, then 
$\alpha\restriction r\prec\gamma\restriction r$, too.
\end{itemize} 
\item
If $\beta\restriction s\prec\gamma\restriction s$, then:
\begin{itemize}
\item
If $\alpha\sqsubseteq\beta$, then we either have
$\alpha\sqsubseteq\gamma$, or $\alpha\restriction
r\prec\gamma\restriction r$. 
\item
If $\alpha\restriction t\prec\beta\restriction t$, then we can infer
that again $\alpha\restriction r\prec\gamma\restriction r$.
\end{itemize}
\end{itemize}
Therefore, in any case, we have $\alpha R\gamma$; so $R$ is indeed
transitive, which concludes the proof $R$ is a partial order.

To prove that $R$ is total, consider any two $\alpha$, $\beta$ and
note that their $t$-prefixes are comparable (by the fact $\preceq$ over
strings of length $t$ is total). Equality of the prefixes implies one
of the strings is a prefix of the other; and any strict order of the
prefixes implies a similar order for the strings. In any case, the
strings are comparable. Which implies $R$ is total.
}

% OLD PROOF FOR PROBLEM 1
%Let $S$ be the totally ordered alphabet, $\preceq_S$ the total order
%on it, and $\prec_S$ the corresponding ``less than'' relation,
%$$
%a \prec_S b  
%\:\iff\: 
%a\preceq_S \wedge a\neq b,
%$$
%again on $S$. 
%
%In Rosen, $R$ is defined to be the relation that, for every two
%strings $\alpha,\beta\in S^\ast$, 
%$$
%\alpha R \beta  \:\iff\:  
%\alpha=\beta \;\vee\; \alpha\prec\beta,
%$$
%where $\prec$ is the following relation on $S^\ast$ (Rosen, p.~418): if
%$\alpha=a_1a_2\dots a_m$, $\beta=b_1b_2\dots b_n$, and $t=\min(m,n)$,
%then   
%$$
%\alpha\prec\beta
%\iff
%(a_1,a_2,\dots,a_t) \prec_t (b_1,b_2,\dots,b_t)
%\\
%\vee \bigl[
%       (a_1,a_2,\dots,a_t) = (b_1,b_2,\dots,b_t)
%       \wedge
%       m<n
%\bigr],
%$$
%$\prec_t$ being the lexicographic ordering that $\preceq_S$ induces
%onto $S^t$. 
%
%\medskip
%Let us first try to prove that $R$ is a partial order. One can easily
%verify that it is sufficient to show that $\prec$ is both
%assymetric\footnote{A relation $R$ on a set $A$ is assymetric iff, for
%all $x,y\in A$, $xRy\implies y\mbox{$\not\!\!R$}x$. Note that
%\emph{a}symmetry and \emph{anti}symmetry are different properties, in
%general. (See also Rosen Exercises~6.1.10--12.)} and transitive. So,
%we try to prove these two things.
%
%For assymetry, suppose $\alpha\prec\beta$, for arbitrary $\alpha =
%(a_1,a_2,\dots,a_m)$, $\beta  = (b_1,b_2,\dots,b_n)$. Then, setting
%$t=\min(m,n)$, we have either $(a_1,a_2,\dots,a_t) \prec_t
%(b_1,b_2,\dots,b_t)$, or $(a_1,a_2,\dots,a_t) = (b_1,b_2,\dots,b_t)
%\wedge m<n$. In the first case, there is an $i\in\{1,2,\dots,t\}$ such
%that  
%$$
%a_1=b_1,\quad  
%a_2=b_2,\quad  
%\dots,\quad  
%a_{i-1}=b_{i-1},\quad  
%a_i\prec_S b_i.
%$$
%This implies that certainly 
%$(b_1,b_2,\dots,b_t) \not\!\prec_t (a_1,a_2,\dots,a_t)$ and also that
%$(b_1,b_2,\dots,b_t) \neq (a_1,a_2,\dots,a_t)$; so,
%$\beta\not\prec\alpha$. In the second case, $\alpha$ is a proper
%prefix of $\beta$, which again easily implies that
%$\beta\not\prec\alpha$. 
%
%For transitivity, assume $\alpha\prec\beta$ and $\beta\prec\gamma$,
%for any  
%$\alpha = (a_1,a_2,\dots,a_m)$, 
%$\beta  = (b_1,b_2,\dots,b_n)$, and
%$\gamma = (c_1,c_2,\dots,c_l)$. Then, setting 
%$t=\min(m,n)$ and $u=\min(n,l)$, we have 
%$$
%\text{either } 
%(a_1,a_2,\dots,a_t) \prec_t (b_1,b_2,\dots,b_t), 
%\text{ or }
%(a_1,a_2,\dots,a_t) = (b_1,b_2,\dots,b_t)\wedge m<n,
%$$
%and
%$$
%\text{either } 
%(b_1,b_2,\dots,b_u) \prec_u (c_1,c_2,\dots,c_u), 
%\text{ or }
%(b_1,b_2,\dots,b_u) = (c_1,c_2,\dots,c_u)\wedge n<l,
%$$
%and we are left with four cases to examine. We study the most
%interesting one (the rest can be treated in similar ways), i.e., the
%case where both $(a_1,a_2,\dots,a_t) \prec_t (b_1,b_2,\dots,b_t)$, and  
%$(b_1,b_2,\dots,b_u) \prec_u (c_1,c_2,\dots,c_u)$. Then we know there
%exist $i\in\{1,2,\dots,t\}$ and $j\in\{1,2,\dots,u\}$ such that 
%\begin{gather*}
%a_1=b_1,\quad 
%a_2=b_2,\quad  
%\dots,  \quad  
%a_{i-1}=b_{i-1},\quad  
%a_i\prec_S b_i,
%\\
%b_1=c_1,\quad  
%b_2=c_2,\quad  
%\dots,  \quad 
%b_{j-1}=c_{j-1},\quad  
%b_j\prec_S c_j.
%\end{gather*}
%Pick $k=\min(i,j)$. Then, we have 
%$$
%a_1=b_1=c_1,\quad  
%a_2=b_2=c_2,\quad  
%\dots,\quad  
%a_{k-1}=b_{k-1}=c_{k-1},\quad  
%a_k\preceq_S b_k \preceq_S c_k,
%$$
%where, in the last relation, at least one of the inequalities has to
%be strict ($\prec_S$, not $\preceq_S$), since $k$ has to equal at
%least one of $i,j$. Hence, what we really have is a
%$k\in\{1,2,\dots,\min(m,l)\}$ for which (also using the transitivity
%of $\prec_S$)
%$$
%a_1=c_1,\quad  
%a_2=c_2,\quad  
%\dots,\quad  
%a_{k-1}=c_{k-1},\quad  
%a_k\prec_S c_k;
%$$
%but this clearly implies that $\alpha\prec\gamma$.
%
%\medskip
%Finally, to prove that $R$ is total, consider two arbitrary strings
%$\alpha=(a_1,a_2,\dots,a_m)$, $\beta=(b_1,b_2,\dots,b_n)$, and again
%let $t=\min(m,n)$. If $\alpha=\beta$, then certainly $\alpha R\beta$,
%i.e., the strings are indeed comparable. If $\alpha$, $\beta$ are
%distinct, then there are two cases: either $a_i=b_i$ for all
%$i=1,2,\dots,t$, or there exists an $i\in\{1,2,\dots,t\}$ such that
%$a_i\neq b_i$. 
%
%In the first case it has to be $m\neq n$ (otherwise, we would have
%$\alpha=\beta$, which is false, by assumption); hence, either $m<n$,
%in which case $\alpha\prec\beta$, or $n<m$, in which case
%$\beta\prec\alpha$. (Notice our use of the fact that the natural
%ordering $\leq$ on the nonnegative integers is total.) So, $\alpha
%R\beta$ or $\beta R\alpha$, and the strings are comparable.
%
%In the second case, let $i_0$ be the least $i\in\{1,2,\dots,t\}$ for
%which $a_i\neq b_i$. Since the ordering $\preceq_S$ on $S$ is total,
%we know that either $a_{i_0}\prec_S b_{i_0}$ or $b_{i_0}\prec_S
%a_{i_0}$. Hence (also using the minimality of $i_0$), we have either
%$$
%a_1=b_1,\quad
%a_2=b_2,\quad
%\dots,  \quad
%a_{i_0-1}=b_{i_0-1},\quad  
%a_{i_0}\prec_S b_{i_0},
%$$
%in which case $\alpha\prec\beta$, or 
%$$
%b_1=a_1,\quad
%b_2=a_2,\quad
%\dots,  \quad
%b_{i_0-1}=a_{i_0-1},\quad  
%b_{i_0}\prec_S a_{i_0},
%$$
%in which case $\beta\prec\alpha$. So, again $\alpha R\beta$ or $\beta
%R\alpha$, and  the strings are comparable. 
%
%Therefore, in every case, $\alpha$ and $\beta$ are comparable; that
%is, $R$ is total.









\problempart Prove that neither $R$ nor $R^{-1}$ is a well-ordering,
for alphabets with more than one element.

\solution{Consider the alphabet $\{a,b\}$ with $a\preceq b$. Then $R$
is not a well ordering since\\ $\{b,ab,aab,aaab,aaaab,\ldots\}$ has no
least element.  Moreover, $R^{-1}$ is not a well-ordering since
$\{a,aa,aaa,aaaa,\ldots\}$ has no least element.

%Consider the alphabet 
%$\{\ldots,a_{-2},a_{-1},a_0,a_1,a_2,\ldots\}$, 
%with the ordering 
%$\ldots\preceq a_{-1}\preceq a_0\preceq a_1\preceq\ldots$. 
%Then $R$ is not a well-ordering, since the set of strings, 
%$\{a_{-1},a_{-2},a_{-3},\ldots\}$ does not have a least element.
%Moreover, the set of strings $\{a_0,a_1,a_2,\ldots\}$ 
%does not have a least element under the ordering $R^{-1}$, and
%therefore $R^{-1}$ is not a well-ordering either.
}
\end{problem}