Lexicographical order - posets vs preorders

Question

I found the following definition for lexicographical ordering on Wikipedia (and similar definitions in other places):

Given two partially ordered sets $A$ and $B$, the lexicographical order on the Cartesian product $A \times B$ is defined as $(a,b) \le (a',b')$ if and only if $a < a'$ or ($a = a'$ and $b \le b'$). The result is a partial order. If $A$ and $B$ are totally ordered, then the result is a total order as well.

Does this definition work equally well if $A$ and $B$ are preorders, rather than posets? In other words, does the anti-symmetric property of the ordering relations on A and B make any difference here?

Answer 1

Yes, if $\langle A,\le_A\rangle$ and $\langle B,\le_B\rangle$ are preorders, the same construction yields a preorder $\langle A\times B,\preceq\rangle$. Specifically, for $\langle a,b\rangle,\langle c,d\rangle\in A\times B$ define $\langle a,b\rangle\preceq \langle c,d\rangle$ iff $a<_A c$, or $a\le_A c$ and $b\le_B d$. Clearly $\preceq$ is reflexive, so you have only to check that it’s transitive.

Added: I should have said explicitly what I mean by $a<_A c$ for the preorder $\le_A$. I don’t mean that $a\le_A c$ and $a\ne c$. Rather, I mean that $a\le_A c$ and $c\not\le_A a$. Equivalently, I mean that $a\le_A c$ and $a\not\sim_A c$, where $a\sim_A c$ iff $a\le_A c$ and $c\le_A a$. Here $\sim_A$ is the equivalence relation on $A$ whose equivalence classes are sets of $\le_A$-indistinguishable members of $A$, and the relation induced on $A/\sim_A$ by $\le_A$ is a partial order. The point is that if $a\sim_A a'$, I want to treat $a$ and $a'$ exactly alike.

If we were dealing with partial orders $\le_A$ and $\le_B$, I could define $\langle a,b\rangle\preceq \langle c,d\rangle$ iff $a<_A c$, or $a=c$ and $b\le_B d$, using the usual definition of lexicographic order. Note, though, that for partial orders that definition is equivalent to saying that $\langle a,b\rangle\preceq \langle c,d\rangle$ iff $a<_A c$, or $a\le_A c$ and $b\le_B d$: if $\langle a,b\rangle\preceq \langle c,d\rangle$ by the latter definition, then either $a<_A c$, in which case $\langle a,b\rangle\preceq \langle c,d\rangle$ by the usual definition as well, or $a\le_A c$, $a\not<_A c$, and $b\le_B d$, in which case $a=c$ and $b\le_B d$, and again $\langle a,b\rangle\preceq \langle c,d\rangle$ by the usual definition. For preorders the two are not equivalent, because a preorder need not be antisymmetric. For preorders the equivalent formulation is that $\langle a,b\rangle\preceq \langle c,d\rangle$ iff $a<_A c$, or $a\sim_A c$ and $b\le_B d$.

To that end suppose that $\langle a,b\rangle\preceq\langle c,d\rangle\preceq\langle e,f\rangle$; clearly $a\le_A c\le_A e$. If either $a<_A c$ or $c<_A e$, then $a<_A e$, and $\langle a,b\rangle\preceq\langle e,f\rangle$. Otherwise we have $b\le_B d$ and $d\le_B f$, so $b\le_B f$, and again $\langle a,b\rangle\preceq\langle e,f\rangle$.