# Order Theory/Lexicographic order

Definition (lexicographic order):

Let $(S_{\alpha },\leq _{\alpha })_{\alpha \in A}$ be preordered sets, where $A$ is well-ordered. Define an order on $\bigcup _{\alpha \in A}$ , the Cartesian product, by

$(s_{\alpha })_{\alpha \in A}\leq (t_{\alpha })_{\alpha \in A}:\Leftrightarrow$ .

Proposition (lexicographic order induced by posets is poset):

Whenever

Proposition (lexicographic order induced by total orders is total):

Whenever $A$ is a well-ordered set and $(S_{\alpha },\leq _{\alpha })_{\alpha \in A}$ are totally ordered sets, the lexicographic order on $\prod _{\alpha \in A}S_{\alpha }$ is total.

Proof: Let any two elements $(s_{\alpha })_{\alpha \in A}$ and $(t_{\alpha })_{\alpha \in A}$ of $\prod _{\alpha \in A}S_{\alpha }$ be given. Then either $(s_{\alpha })_{\alpha \in A}=(t_{\alpha })_{\alpha \in A}$ , or there exists a smallest $\beta \in A$ so that $s_{\beta }\neq t_{\beta }$ . Since $\leq _{\beta }$ is total, either $s_{\beta } or $s_{\beta }>t_{\beta }$ , and thus either $(s_{\alpha })_{\alpha \in A}<(t_{\alpha })_{\alpha \in A}$ or $(s_{\alpha })_{\alpha \in A}>(t_{\alpha })_{\alpha \in A}$ . $\Box$ 