# Order Theory/Lexicographic order

Definition (lexicographic order):

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

${\displaystyle (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 ${\displaystyle A}$ is a well-ordered set and ${\displaystyle (S_{\alpha },\leq _{\alpha })_{\alpha \in A}}$ are totally ordered sets, the lexicographic order on ${\displaystyle \prod _{\alpha \in A}S_{\alpha }}$ is total.

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