User:Dfeuer/Definition:Lexicographic Ordering on Product

Definition

Let $\struct {I, \preceq}$ be a well-ordered set.

For each $i \in I$, let $\struct {X_i, \le_i}$ be an ordered set.

Let $X = \ds \prod_{i \mathop \in I} X_i$ be the Cartesian product of the $X_i$.

The lexicographic ordering on $X$ is the binary relation $\le$, defined as follows:

For $a, b \in X$, let $M_{a, b} = \set {i \in I: a_i \ne b_i}$.

Then $a \le b$ if and only if either of the following holds:

• $M_{a, b}$ is empty
• $M_{a, b}$ is non-empty, and, letting $m = \min M_{a, b}$, $a_m \le_m b_m$

Here, $\min M_{a, b}$ denotes the smallest element of $M_{a, b}$ under $\preceq$, which exists as $I$ is a woset.

Also see

User:Dfeuer/Lexicographic Ordering is Ordering

Lexicographic Order of Family of Totally Ordered Sets is Totally Ordered Set