Let R1 be a total order on set S1 and R2 be a total order on set S2. Prove or disprove that the lexicographic order is a total order on S1 X S2.
So far I'm trying to start the proof with: Let R1 be a total order on set S1, and R2 be a total order on set S2 If for every x,y that are elements of S1, we have x R1 y or y R1 x, and for every x,y that are elements of S2, we have x R2 Y or y R2 x. Then...
Take two arbitrary elements of $S1 \times S2, (a,b)$ and $(c,d)$ You want to prove that they are comparable. Because $R1, R2$ are total, we know $a,b$ and $c,d$ are comparable. From the definition of lexicographic order, if $a \neq b$ we use the comparison in $R1$ to order the pairs, else we use the comparison in $R2$ to order the pairs. Now you have to show antisymmetry and transitivity, which you can do from the definition.