1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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'. $\endgroup$
    – Ragnar
    Jul 17, 2014 at 13:17
  • $\begingroup$ 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 $\endgroup$
    – AlexR
    Jul 17, 2014 at 13:18

1 Answer 1

Reset to default
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ great.. thanks soo much! :) $\endgroup$
    – mle
    Jul 17, 2014 at 13:28
  • $\begingroup$ @AnatolyIvanovichMaltsev Happy to help :) $\endgroup$
    – AlexR
    Jul 17, 2014 at 13:29
  • $\begingroup$ in this case $\leq^d$ is total order in $A^n$, is correct? $\endgroup$
    – mle
    Jul 17, 2014 at 15:46
  • 2
    $\begingroup$ @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. $\endgroup$
    – AlexR
    Jul 17, 2014 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.