Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 7 down vote accepted

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$.

share|improve this answer
    
@Code-Guru: I was actually a little sloppy; I’ll fix it in the next few minutes. –  Brian M. Scott Jul 15 '12 at 21:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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