Saturday, 17 August 2013

Prove that the Lexicographical Order is Partially Ordered

Prove that the Lexicographical Order is Partially Ordered

Let $X$ be a partially ordered set under $\le$. Let $FIN(X)$ be the set of
finite sequences (including the empty sequence) whose members are elements
of $X$.
If $\sigma = (x_1 x_2 ... x_n)$, $\tau = (y_1 y_2 ... y_m) \in X$, we say
$\sigma \le_L \tau$ if and only if either $\tau$ extends $\sigma$ or where
$j$ is least so $x_j \ne y_j$ then $x_j \le y_j$.
By extension, we mean that there is a sequence $\rho \in X$ such that
$\tau = (\sigma$ followed by $\rho)$. So, let $X = \{0, 1\}$, with $0 \le
1$. If $\sigma = (100)$, $\rho = (110)$, then $\tau = (\sigma$ followed by
$\rho)$ = $(100100)$.
The part "where $j$ is least so $x_j \ne y_j$ then $x_j \le y_j$" is
unclear to me. My interpretation is that if there is some index $i$ such
that $x_i \ne y_i$, let $j$ be the smallest $i$. If $x_j \le y_j$ (or $x_j
\lt y_j$), then $\sigma \le_L \tau$. For example $(011001) \le_L
(0101010)$. But if such a $j$ does not exist, then that half of the
condition is false. So $(100) \le_L (1001)$ only because $(1001)$ extends
$(100)$.

Is there a succinct way to prove the asymmetric and the transitive axiom
in the definition of partial order? I examined case by case. Assuming that
my understanding in question $1.$ is correct, I think I got it. The
following shows that the asymmetric axiom holds:
Let $\sigma \le_L \tau \le_L \sigma$. So, both of the following are true:
1. $\tau$ extends $\sigma$ or if there exists a $j$, the smallest index
such that $x_j \ne y_j$, then $x_j \le y_j$.
2. $\sigma$ extends $\tau$ or if there exists a $k$, the smallest index
such that $x_k \ne y_k$, then $y_k \le x_k$.

Start with the first scenario in statement $1$. Suppose that $\tau$
extends $\sigma$. Then $\sigma = (x_1 x_2 ... x_n)$, $\tau = (y_1 y_2 ...
y_m)$ with $n \le m$ and $x_i = y_i$ for all $i = 1 ... n$. If $\sigma$
extends $\tau$, then $\sigma = \tau$. On the other hand, if there exists a
$j$, the smallest index such that $x_j \ne y_j$ with $y_j \le x_j$, we
reach a contradiction. It is because such a j must be smaller or equal to
n, contradicting the premise that $x_i = y_i$ for all $i = 1 ... n$. So
such a scenario cannot happen.

Proceed with the second scenario in statement $1$. Suppose that there
exists a $j$, the smallest index such that $x_j \ne y_j$, then $x_j \le
y_j$. If $\sigma$ extends $\tau$, then again, we'll have a contradiction,
because extension requires that $x_i = y_i$ for all $i = 1 ...
$min($n,m$). On the other hand, suppose that there exists a $k$, the
smallest index such that $x_k \ne y_k$, then $y_k \le x_k$. Then $j = k$
with $x_j \le y_j, y_j \le x_j$. Since we are given that $X$ is a
partially order under $\le$, $x_j = y_j$, which produces another
contradiction.

No comments:

Post a Comment