# About definition of lexicographical order

Def. let be $\preceq_A$ a total order, $(a_1,a_2,...,a_n),(b_1,b_2,...,b_n) \in A^n$, $(a_1,a_2,...,a_n) \leq^d (b_1,b_2,...,b_n)$ if one and only one of the following holds is true: $$a_1 \prec_A b_1$$$$a_1=b_1 \wedge a_2 \prec_A b_2$$$$a_1=b_1 \wedge a_2=b_2 \wedge a_3 \prec_A b_3$$$$.$$$$.$$$$.$$$$a_1=b_1 \wedge a_2=b_2 \wedge ... \wedge a_{n-1}=b_{n-1} \wedge a_n \prec_A b_n$$with $a_i \prec_A b_i \equiv a_i \preceq_A b_i \wedge a_i \neq b_i$

Is it correct? Thanks in advance

• That seems right to me, but I don't think two of these can be true at the same time, so 'one and only one' can be simplified to 'one' or 'at least one'. Jul 17, 2014 at 13:17
• That is a plausible definiton. What exactly are you asking for? Note that $\le^d$ should be associated with $\preceq_A$ and needs a little more clarification. Your definition taken for $<^d$ and defining $A \le^d B :\Leftrightarrow A=B \vee A<^d B$ seems like the way to go Jul 17, 2014 at 13:18

To reflect that $\le$ is associated with $\preceq$ and $<$ with $\prec$ you could use \begin{align*}a\prec b & :\Leftrightarrow a\preceq b \wedge a\neq b\\ A<^d B & :\Leftrightarrow \exists k: a_i = b_i \forall i<k \quad \wedge \quad a_k \prec b_k\\ A\le^d B&:\Leftrightarrow A<^d B \vee A=B\end{align*}

If you want to only define $\le^d$ but equivalent to the above (i.e. eliminate usage of $\prec, <$), write this:

$$A\le^d B:\Leftrightarrow A = B \vee (\exists k: a_i=b_i \forall i <k\quad \wedge\quad a_k \ne b_k \wedge a_k \preceq b_k)$$ $k$ could be called the "common prefix length" or something.

• great.. thanks soo much! :)
– mle
Jul 17, 2014 at 13:28
• @AnatolyIvanovichMaltsev Happy to help :) Jul 17, 2014 at 13:29
• in this case $\leq^d$ is total order in $A^n$, is correct?
– mle
Jul 17, 2014 at 15:46
• @AnatolyIvanovichMaltsev Yes, it indeed is. You can verify all axioms for exercise if you wish; it revolves around proving that the $k$ from the definition always exists and using that $\preceq$ is a total order on the alphabet. Jul 17, 2014 at 15:48