next up previous contents
Siguiente: Homomorfismos Un nivel arriba: Relaciones de orden Anterior: Orden de prefijo

Orden lexicográfico

Sea $\Sigma$ un alfabeto dotado de un orden ``$\leq$'', por ejemplo, para el alfabeto ASCII consideramos el orden usual. Extendemos el orden ``$\leq$'' de $\Sigma$ a un orden `` $\leq_{\mbox{\scriptsize\it lg}}$'' de $\Sigma^*$ mediante la definición siguiente:

\begin{eqnarray*}\forall\sigma_1,\sigma_2\in\Sigma^*:\ \sigma_1\leq_{\mbox{\scri...
...y}\right\}\Rightarrow s_1<s_2\end{displaymath}
\end{minipage}}
\end{eqnarray*}


La siguiente proposición resume las propiedades más elementales de este orden, llamado lexicográfico. Su demostración es más tediosa que instructiva y por esa razón la omitimos.

Proposición 2.7   El orden lexicográfico satisface las propiedades siguientes:
1.
Es, en efecto, un orden, es decir, cualesquiera que sean las palabras $\sigma, \tau, \upsilon$,

\begin{eqnarray*}&& \sigma \leq_{\mbox{\scriptsize\it lg}} \sigma \\
(\sigma \...
..._{\mbox{\scriptsize\it lg}} \sigma) &\Rightarrow& \sigma = \tau
\end{eqnarray*}


2.
Es lineal, es decir, $\forall \sigma, \tau$: $\left(\sigma \leq_{\mbox{\scriptsize\it lg}} \tau\right)\lor \left(\sigma = \tau\right)\lor \left(\tau \leq_{\mbox{\scriptsize\it lg}} \sigma\right).$
3.
Es congruente por la izquierda, es decir, $\forall \sigma, \tau: \upsilon$, $\left(\sigma \leq_{\mbox{\scriptsize\it lg}} \tau\ \Rightarrow \ \upsilon\sigma \leq_{\mbox{\scriptsize\it lg}} \upsilon\tau\right)$. Mas no lo es por la derecha.



Guillermo Morales-Luna
2000-06-27