# Lexicographical order - posets vs preorders

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?

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$$.
• Is there some reference online on which properties of $A$ and $B$ are preserved by $\langle A\times B, \le\rangle$? Commented Mar 4, 2018 at 3:41