I have read about
Definition Of Lexicographic Ordering,
Lexicographic Order,
Generalized lexicographic order,
Lexicographical order,
Lexicographic ordering,
and many other related questions with their corresponding provided answers. It seems there's none about my question here:
Let $\left({S_1, \preceq_1}\right)$ and $\left({S_2, \preceq_2}\right)$ be ordered sets such that $\preccurlyeq$ be the lexicographic order on $S_1 \times S_2.$ By definition we have that $$\left({x_1, x_2}\right) \preccurlyeq \left({y_1, y_2}\right) \iff \left({x_1 \prec_1 y_1}\right) \lor \left({x_1 = y_1 \land x_2 \preceq_2 y_2}\right).$$
Then $\preccurlyeq$ is an ordering on $S_1 \times S_2.$ For vectors with only two entries: $(x_1, x_2), (y_1, y_2),$ the transitivity property of lexicography ordering is such that if $\left({x_1, x_2}\right) \preccurlyeq \left({y_1, y_2}\right)$ and $\left({y_1, y_2}\right) \preccurlyeq \left({z_1, z_2}\right)$ then $\left({x_1, x_2}\right) \preccurlyeq \left({z_1, z_2}\right)$ which is proved as follows.
By definition of lexicographic order on $S_1 \times S_2$, we need to show four cases:
Case (1): Let $x_1 = y_1 = z_1.$ Then, $x_2 \preceq_2 y_2 \ \text{ and } \ y_2 \preceq_2 z_2$ and it follows that: $\left({x_1, x_2}\right) \preccurlyeq \left({z_1, z_2}\right)$
Case (2): Let $x_1 = y_1$ and $y_1 \ne z_1.$ Then, $y_1 \prec z_1 \ \text{ but as } x_1 = y_1 \implies x_1 \prec z_1$ and it follows that $\left({x_1, x_2}\right) \preccurlyeq \left({z_1, z_2}\right).$
Case (3): Let $x_1 \ne y_1$ and $y_1 = z_1.$ Then, $x_1 \prec y_1 \text{ but as } \ y_1 = z_1, \implies x_1 \prec z_1 $ and it follows that $\left({x_1, x_2}\right) \preccurlyeq \left({z_1, z_2}\right).$
Case (4): Let $x_1 \ne y_1$ and $y_1 \ne z_1.$ Then, $x_1 \prec y_1$ and $y_1 \prec z_1 \implies x_1 \prec z_1$ and $\left({x_1, x_2}\right) \preccurlyeq \left({z_1, z_2}\right)$
Thus, in all cases it can be seen that: $\left({x_1, x_2}\right) \preccurlyeq \left({z_1, z_2}\right) \quad\quad\Box$
QUESTION: for n-tuple vectors, $A = (a_1, a_2, \ldots, a_n), \ B = (b_1, b_2, \ldots, b_n), \ C = (c_1, c_2, \ldots, c_n)$, how would I prove such a transitivity property using all these four cases? Could there be a better way than using the four cases to prove transitivity?
Best Answer
I'm assuming "ordered set" means "partially ordered set". If $A=B$ or $B=C$, this is clear, so assume that $A\prec B\prec C$ (that is, none of them are equal). Then by definition of lexicographic order, there is some $i$ with $1\leq i\leq n$ such that $a_i\prec_i b_i$ and $a_j=b_j$ for all $j<i$. Similarly, there is some $k$ with $1\leq k\leq n$ such that $b_k\prec_k c_k$ and $b_j=c_j$ for all $j<k$. We need only consider two cases.
Case (1): Assume $k\leq i$. Then for all $j<k$, we have $a_j=b_j=c_j$ and $a_k\preceq_k b_k\prec_k c_k$, hence $A\prec C$.
Case (2): Assume $i<k$. Then for all $j<i$, we have $a_j=b_j=c_j$ and $a_i\prec_i b_i\preceq_i c_i$, hence $A\prec C$.