3

Suppose $R$ is a total order on $A$ and $S$ is a total order on $B$. Define a relation $L$ on $A \times B$ as follows: $L = \{((a, b), (a', b')) \in (A \times B) \times (A \times B) | aRa' \land (a = a' \implies bSb') \}$. Is $L$ a total order? (Assume that we have also proven that L is a partial order).

I would appreciate a suggestion when looking for a counterexample (I suspect that the $L$ is not a total order).

Why I think it is not a total order:

To show that $L$ is a total order let $(a,b), (c,d) \in A\times B$ and we will show that $(a,b)L(c,d) \lor (c,d)L(a,b)$. Since $R$ and $S$ are total orders we have:

  • $aRc \lor cRa$
  • $bSd \lor dSb$

We can split the proof into cases:

  1. $aRc \land bSd$. Then it doesn't matter whether $a =c$, we have $(a,b)L(c,d)$
  2. $aRc \land dSb$.
    1. If $a\ne c$ we can have $(a,b)L(c,d)$.
    2. But if $a=c$ to have this result we need to have $bSd$. If $b=d$ then $bSd$ so $(a,b)L(c,d)$. However if $b \ne d$, suppose $bSd$. Since $S$ is antisymmetric it would follow that $b=d$ which is a contradiction, so $(b,d)\notin S$.

It seems to me that I am stuck at point 2.2. $(a,b)L(c,d)$ cannot be true so the only way the proof would work out is if $(c,d)L(a,b)$ which I am unlikely to prove in this case.

pseudomarvin
  • 861

1 Answers1

2

$L$ is called lexicographical order and it is indeed a total order: in your point 2.2, you have that $(c,d)L(a,b)$ holds since $a=c$ and $dSb$. The other cases are treated analogously.

Note: the lexicographical order is exactly the order used in dictionaries, except that there words don't necessarily have the same length. But since you have a minimal element "a" in the alphabet, you can think that you are putting enough "a"'s at the end of every word so that they are all of the same length.

In general: $L=\{ ((x_1,\dots,x_n),(y_1,\dots y_n)) \in (X_1 \times \dots \times X_n)^2 \mid x_1R_1y_1 \wedge (x_1=y_1 \Rightarrow (x_2 R_2 y_2 \wedge (x_2=y_2 \Rightarrow (\dots))))\}$

57Jimmy
  • 6,266
  • Thanks for your help. Regarding your note, is the lexicographic order $L$ always defined the way it is defined in my question? It seems that we could use just a single total order $ R={(a,a') \in A\times A}$ where $A$ could stand for the set of all letters. We wouldn't need $S$ right? $aRa'$ would mean that $a$ preceeds or is in the same place in the alphabet as $a'$. – pseudomarvin Aug 13 '16 at 12:39
  • 1
    Yes, that's right: on a dictionary we have $n$ copies of the same ordered set (the alphabet), and on all of them we have the same order relation. But you could define it more in general, as in your example, with different orders, although it gets a bit cumbersome (see edited answer). – 57Jimmy Aug 13 '16 at 13:37