# Preorders, chains, cartesian products, and lexicographical order

Definitions:

A preorder on a set $X$ is a binary relation $\leq$ on $X$ which is reflexive and transitive.

A preordered set $(X, \leq)$ is a set equipped with a preorder.... Where confusion cannot result, we refer to the preordered set $X$ or sometimes just the preorder $X$.

If $x \leq y$ and $y \leq x$ then we shall write $x \cong y$ and say that $x$ and $y$ are isomorphic elements.

Write $x < y$ if $x \le y$ and $y \not\le x$ for each $x, y \in X$. This gives a strict partial order on $X$. (See also, this question.)

Given two preordered sets $A$ and $B$, the lexicographical order on the Cartesian product $A \times B$ is defined as $(a,b) \le_{lex} (a',b')$ if and only if $a < a'$ or ($a \cong a'$ and $b \le b'$). The result is a preorder.

A subset $C$ of a preorder $X$ is called a chain if for every $x,y \in C$ we have $x \leq y$ or $y \leq x$.... We shall say that a preorder $X$ is a chain ... if the underlying set $X$ is such.

Exercise:

Let $C$ and $C'$ be chains. Show that the set of pairs $(c, c')$, where $c \in C$ and $c' \in C'$, is also a chain when ordered lexicographically

-
That’s exactly the correct fix. – Brian M. Scott Jul 15 '12 at 21:56
@BrianM.Scott I just saw your edit in my other question. Thanks. – Code-Guru Jul 15 '12 at 22:00

Suppose $(c_1, c_1')$ and $(c_2, c_2')$ are pairs with $c_1, c_2 \in C$ and $c_1', c_2' \in C'$. Then $c_1 \le c_2$ or $c_2 \le c_1$ and $c_1' \le c_2'$ or $c_2' \le c_1'$. If $c_1 \le c_2$ but $c_2 \not\le c_1$ then $c_1 < c_2$ and $(c_1, c_1') \le_{lex} (c_2, c_2')$. Similarly, if $c_1 \not\le c_2$ and $c_2 \le c_1$ then $(c_2, c_2') \le_{lex} (c_1, c_1')$. If $c_1 \le c_2$ and $c_2 \le c_1$ then $c_1 \cong c_2$. Now if $c_1' \le c_2'$ then $(c_1, c_1') \le_{lex} (c_2, c_2')$. On the other hand if $c_2' \le c_1'$ then $(c_2, c_2') \le_{lex} (c_1, c_1')$.