Exercise 3.9

Question

Check that the dictionary order is an order relation.

Dan Whitman · Accepted Answer

ewcommand\appt[1]{a_{#1} 	imes b_{#1}}

Suppose that $A$ and $B$ are two sets with order relations $<_A$ and $<_B$.
Recall that the dictionary order $<$ on $A 	imes B$ is defined by
\begin{gather*}
  \appt{1} < \appt{2}
\end{gather*}
if $a_1 <_A a_2$ or if $a_1 = a_2$ and $b_1 <_B b_2$.
\begin{proof}
  Clearly, $<$ is a relation on $A 	imes B$ so we just need to show the three properties of an order relation:
  \begin{itemize}
  \item (Comparability) Consider distinct points $\appt{1}$ and $\appt{2}$ in $A 	imes B$ so that $a_1 
eq a_2$ or $b_1 
eq b_1$.
    If $a_1 
eq a_2$ then they are comparable in $<_A$ (since it is an order relation) so that, without loss of generality, we can assume that $a_1 <_A a_2$.
    Then of course $\appt{1} < \appt{2}$ by definition.
    So assume that $a_1 = a_2$ so that it must be that $b_1 
eq b_2$.
    Then $b_1$ and $b_2$ are comparable in $<_B$ since it is an order relation.
    So without loss of generality, we can assume that $b_1 <_B b_2$.
    Then of course $\appt{1} < \appt{2}$ since also $a_1 = a_2$.
    Thus either way $\appt{1}$ and $\appt{2}$ are comparable in $<$.

\item (Nonreflexivity) Suppose that $\appt{}$ is any element of $A 	imes B$.
    Since $<_B$ is an order relation, it is nonreflexive so it is not true that $b <_B b$.
    Since of course $a=a$, it follows that it cannot be that $\appt{} < \appt{}$ since it would have to be that $b <_B b$.
    Hence $<$ is nonreflexive since $\appt{}$ was arbitrary.

\item (Transitivity) Suppose that $\appt{1} < \appt{2}$ and $\appt{2} < \appt{3}$.
    We then have the following cases:

Case: $a_1 <_A a_2$.
    \begin{itemize}
    \item Case: $a_2 <_A a_3$.
      Then $a_1 <_A a_2$ and $a_2 <_A a_3$ so that $a_1 <_A a_3$ since $<_A$ is transitive.
      Thus by definition $\appt{1} < \appt{3}$.

\item Case: $a_2 = a_3$ and $b_2 <_B b_3$.
      Then $a_1 <_A a_2 = a_3$ so that $\appt{1} < \appt{3}$ by definition.
    \end{itemize}

Case: $a_1 = a_2$ and $b_1 <_B b_2$.
    \begin{itemize}
    \item Case: $a_2 <_A a_3$.
      Then $a_1 = a_2 <_A a_3$ so that by definition $\appt{1} < \appt{3}$.

\item Case: $a_2 = a_3$ and $b_2 <_B b_3$.
      Then $a_1 = a_2 = a_3$ and $b_1 <_B b_2$ and $b_2 <_B b_3$ so that $b_1 <_B b_3$ since $<_B$ is transitive.
      Therefore again $\appt{1} < \appt{3}$ by definition.
    \end{itemize}
    
    Thus in all cases $\appt{1} < \appt{3}$, which shows that $<$ is transitive.
  \end{itemize}
\end{proof}

Exercise 3.9

Answers

Comments

Exercise 3.9

Answers

Comments

Add answer