0

I am reading Topology by James Munkres and he defines the dictionary order relation as:

Definition Suppose that $A$ and $B$ are both sets with order relations $<_A$ and $<_B$ respectively. Define an order $<$ on $A\times B$ by defining

$$a_1 \times b_1 < a_2 \times b_2$$

if $a_1<_A a_2$, or $a_1=a_2$ and $b_1<_B b_2$. It is called the dictionary order relation on $A\times B$.

I think that I intuitively understand the relation as working as indexing words in the dictionary. The problem is that I do not understand how is it that the order relation of the following cases is defined in the previous definition:

  1. How is it in the definition that $a_1 \times b_1 < a_2 \times b_1$ ?
  2. How is it in the definition that $a_1 \times b_3 < a_3 \times b_1$ ?

I kind of intuitively feel that it could be deduced from the definition but I do not see how. I want to understand it so I make sure I do understand the concept and the definition.

Thanks

MPW
  • 43,638
César D. Vázquez
  • 365
  • Points in $A\times B$ are compared by their first elements, and the second elements are compared if there is a "tie" with the first elements. If the order can be determined using only the first elements, the second elements aren't used. For example, if $A=B=\mathbb R$, then $(1,r)<(2,s)$ no matter what $r$ and $s$ are because $1<_A 2$. – MPW May 18 '20 at 13:23

1 Answers1

1

If you look at the definition of dictionary order relation, you see that you can say in words that $(a_1, b_1) < (a_2, b_2)$ if and only if

  • The first element of the pair $(a_1, b_1)$ is less than the first element of the pair $(a_2, b_2)$ with respect to $<_A$, or
  • The first two elements of the pairs $(a_1, b_1)$ and $(a_2, b_2)$ are equal and the second element of the pair $(a_1, b_1)$ is less than the second element of the pair $(a_2, b_2)$ with respect to $<_B$.

With this, we can see that the defintion for $(a_1, b_1) < (a_2, b_1)$ is just:

  • $a_1 <_A a_2$, or
  • $a_1 = a_2$ and $b_1 <_B b_1$.

Note that in this case we don't have that $b_1 <_B b_1$ (since trivially $b_1 = b_1$), so if you know that $(a_1, b_1) < (a_2, b_1)$, then the definition of the dictionary order relation implies that $a_1 <_A a_2$.

For $(a_1, b_3) < (a_3, b_1)$ the definition is that:

  • $a_1 <_A a_3$, or
  • $a_1 = a_3$ and $b_3 <_B b_1$.

In this case, if you know that $(a_1, b_3) < (a_3, b_1)$, then the defintion of the dictionary order relation implies that one of the above has to hold; if no more information is given about $a_1,a_3,b_1$ and $b_3$ then no more information can be deduced.

Rick
  • 1,896