Definition Of Lexicographic Ordering

Question

I am reading about lexicographic ordering, and I want to make sure I am understanding it properly.

Lexicographic ordering is defined to be the cartesian product of two, or more, posets. So given that $A_1 = (B_1, \preceq)$, and $A_2 = (B_2, \preceq)$; and $A_1 \times A_2$ is a lexicographic order?

And $((a,b),(c,d))$ is in $A_1 \times A_2$, if $(a,b)$ is in $A_1$, and $(c,d)$ is in $A_2$.

But for the cartesian product to be defined, it seems like the relation in each poset has to be the same. Is that right?

A part of what the book says, that I don't understand, is, "Lexicographic ordering is defined by specifying that one pair is less than a second pair:

(i) if the first entry of the first pair is less than (in $A_1$) the first entry of the second pair, or

(ii) if the first entry of both the first and second pairs are equal, but the second entry of first pair is less than (in $A_2$) the second entry of the second pair.

In other words, $(a_1,a_2)$ is less than $(b_1,b_2)$, that is, $(a_1,a_2)≺(b_1,b_2),$ either

if $a_1≺b_1$ or

if both $a_1=b_1$ and $a_2≺b_2$."

Answer 1

Let $A=\{a,b,c\}$ have the ordering $a<b<c$.

Let $B=\{0,1\}$ have the ordering $0<1$.

Then the lexicographic ordering on $A\times B$ is $(a,0)<(a,1)<(b,0)<(b,1)<(c,0)<(c,1)$.

Answer 2

I don't understand what you mean by "the relation in each poset has to be the same" -- they don't have to be the same sets.

For example, $B_1 = \{ a, b, c\}, B_2 = \{ a, d, e\}$. With the "obvious" order $a < b < c < d < e$. Then the (lexicographic) order on the product is what the name says: $(a,b) < (c,e)$ for example and $(a,b) < (a,d)$.

Lexicographic order is exactly how you'd sort words: $donkey < monkey$ but $monkey < ponkey$ and so on.

Answer 3

No, a lexicographic ordering is not a Cartesian product of posets; it’s a particular partial order on a Cartesian product of posets. Consider the partial order $\langle\Bbb N,\le\rangle$. The lexicographic order on $\Bbb N^3$, which I’ll denote by $\preceq$, is defined as follows:

for any $\langle m_1,m_2,m_3\rangle$ and $\langle n_1,n_2,n_3\rangle$ in $\Bbb N^3$, $\langle m_1,m_2,m_3\rangle\preceq\langle n_1,n_2,n_3\rangle$ if and only if:

• $m_1<n_1$, or
• $m_1=n_1$ and $m_2<n_2$, or
• $m_1=n_1$ and $m_2=n_2$ and $m_3\le n_3$.

In other words, first you compare the first components of the ordered triples; if one is smaller than the other, its ordered triple comes first in the lexicographic order. If the first components are equal, you go on to the second components and do the same thing. If they’re equal, you go on to the third components. It’s exactly like alphabetizing words: able comes before big because a comes before b in alphabetical order, and it also comes before axle because even though both words begin with a, the second letter, b, of able comes before x, the second letter of axle. (In fact, lexicographic order simply means dictionary order.)

Here’s another example, this time with a Cartesian product of two different posets. Let $P_1=\langle\Bbb N\le\rangle$, and let $P_2=\langle\wp(\{0,1,2,3\}),\subseteq\rangle$. Then in the lexicographic order $\preceq$ on $\Bbb N\times\wp(\{0,1,2,3\})$ we have

$$\begin{align*} &\langle 3,\{0,2\}\rangle\prec\langle 4,\varnothing\rangle&&\text{because }3<4\\ &\langle 3,\{0,2\}\rangle\prec\langle 3,\{0,2,3\}\rangle&&\text{because }3=3\text{ and }\{0,2\}\subsetneqq\{0,1,2\}\;,\text{ and}\\ &\langle 3,\{0,2\}\rangle\not\preceq\langle 3,\{2\}\rangle&&\text{because although }3=3,~\{0,2\}\nsubseteq\{2\}\;. \end{align*}$$