Is a lexicographic order over a partial-order and a total-order a total ordering?

854 Views Asked by At

Is the following statement true? If so, can someone advise on how to prove it?

Let A = $(S_1,\prec_1)$ be a partially-ordered set and let B = $(S_1,\prec_2)$ be a totally-ordered set

Let $\preccurlyeq$ be the lexicographic order on $A \times B$.

Then $\preccurlyeq$ is an total ordering on $A \times B$.

1

There are 1 best solutions below

2
On BEST ANSWER

It’s false in general. Let $S_1=\{a,b\}$, where $a$ and $b$ are incomparable with respect to $\prec_1$, and $a\prec_2b$. Then $\langle S_1\times S_1,\preccurlyeq\rangle$ is not a total order, as can be seen from its Hasse diagram:

             <a,b>        <b,b>  
               |            |  
             <a,a>        <b,a>