Lesson 3

On the set \(X \times Y\), one can also define a lexicographic order: \((x_{1}, y_{1}) \preceq (x_{2}, y_{2})\) if \(x_{1} \prec x_{2}\) or (\(x_{1} = x_{2}\) and \(y_{1} \preceq y_{2}\)). In the case where the same original order is used, we get the lexicographic order on pairs (i.e., sequences of length two) of elements from the original set. This naturally generalizes to triples, quadruples, and so on, as well as to infinite sequences.

Problem. Let the orders \((X, \preceq_{X})\) and \((Y, \preceq_{Y})\) be linear. Is the lexicographic order linear?