Exercise 11.3

Question

Let $A$ be a set with a strict partial order $\prec$; let $x \in A$.
Suppose that we wish to find a maximal simply ordered subset $B$ of $A$ that contains $x$.
One plausible way of attempting to define $B$ is to let $B$ equal the set of all those elements of $A$ that a \emph{comparable} with $x$:
\begin{gather*}
B = \left\{y \mid y \in A 	ext{ and either } x \prec y 	ext{ or } y \prec xight\}\,.
\end{gather*}
But this will not always work.
In which of Examples 1 and 2 will this procedure succeed and in which will it not?

Dan Whitman · Accepted Answer

First, it seems that, as defined above, $B$ does not actually contain $x$ itself!
This is because it is not true that $x \prec x$ by the non-reflexivity of the partial order $\prec$.
We assume that this was an oversight, which is easily remedied by defining
\begin{gather*}
B' = \left\{y \in A \mid 	ext{either } x \prec y 	ext{ or } y \prec xight\}
\end{gather*}
and $B = B' \cup \left\{xight\}$.

For Example~1, a circular region in ${\mathbb{R}}^2$ is clearly
\begin{gather*}
C_{\mathbf{x} _0,r} = \left\{\mathbf{x}  \in {\mathbb{R}}^2 \mid \left|\mathbf{x}  - \mathbf{x} _0ight| < right\} \,,
\end{gather*}
where the point $\mathbf{x} _0 \in {\mathbb{R}}^2$ is the center of the circle, $r \in {\mathbb{R}_{+}}$ is the radius, and $\left|(x,y)ight| = \sqrt{x^2 + y^2}$ is the standard vector magnitude.
Then the collection  $\mathcal{A}$ is the set of all circular regions:
\begin{gather*}
\mathcal{A} = \left\{C_{\mathbf{x} _0,r} \mid \mathbf{x} _0 \in {\mathbb{R}}^2 	ext{ and } r \in {\mathbb{R}_{+}}ight\} \,.
\end{gather*}
Then let $\mathcal{C} = \left\{C_{(0,0),r} \mid r \in {\mathbb{R}_{+}}ight\}$ be the set of circles centered at the origin, which is a maximal simply ordered subset according to the example (and this is not difficult to show).
Arbitrarily choose $X = C_{(0,0),1}$, that is the circular region of radius 1 centered at the origin so that clearly $X \in \mathcal{C}$.
Since the partial order in this example is ``is a proper subset of'', define
\begin{gather*}
\mathcal{B}' = \left\{Y \in \mathcal{A} \mid Y \subsetneq X 	ext{ or } X \subsetneq Yight\}
\end{gather*}
and $\mathcal{B} = \mathcal{B}' \cup \left\{Xight\}$.
The question is then whether $\mathcal{B} = \mathcal{C}$.
We claim that, for this example, this is not the case.
\begin{proof}
Consider the set $C_{(1,0),2}$ and any $\mathbf{x}  \in X = C_{(0,0),1}$ so that $\left|\mathbf{x}  - (0,0)ight| < 1$.
Then we have
\begin{gather*}
\left|\mathbf{x}  - (1,0)ight| \leq \left|\mathbf{x}  - (0,0)ight| + \left|(0,0) - (1,0)ight| < 1 + \left|(-1,0)ight| = 1 + 1 = 2\,,
\end{gather*}
where we have utilized the ever-useful triangle inequality.
Therefore $\mathbf{x}  \in C_{(1,0),2}$ so that $X \subset C_{(1,0),2}$ since $\mathbf{x} $ was arbitrary.
However, clearly the point $(1,0) \in C_{(1,0),2}$ but we have that $(1,0) 
otin C_{(0,0),1} = X$ since $\left|(1,0) - (0,0)ight| = \left|(1,0)ight| = 1 \geq 1$.
This shows that $X \subsetneq C_{(1,0),2}$ so that by definition $C_{(1,0),2} \in \mathcal{B}'$ and therefore $C_{(1,0),2} \in \mathcal{B} = \mathcal{B}' \cup \left\{Xight\}$.
But clearly $C_{(1,0),2} 
otin \mathcal{C}$ since it is not centered at the origin.
This shows that $\mathcal{B} 
eq \mathcal{C}$, as desired.
\end{proof}
Hence it would seem that this method of attempting to define a maximal simply ordered subset containing $X$ has failed in this example.
It is easy to come up with an analogous counterexample that shows the same result as the other example of a maximal simply ordered subset of circles tangent to the y-axis at the origin.

Regarding Example~2, recall that the order $\prec$ is defined by
\begin{gather*}
(x_0, y_0) \prec (x_1, y_1)
\end{gather*}
if $y_0 = y_1$ and $x_0 < x_1$ for $(x_0, y_0)$ and $(x_1, y_1)$ in ${\mathbb{R}}^2$.
It is then claimed (which is again easy to show) that maximal simply ordered subsets are horizontal lines in the plane, that is sets
\begin{gather*}
L_{y_0} = \left\{(x,y) \in {\mathbb{R}}^2 \mid y = y_0ight\}
\end{gather*}
for some $y_0 \in {\mathbb{R}}$.
So consider any such $y_0 \in {\mathbb{R}}$ and let $\mathbf{x}  = (0, y_0)$.
Now define
\begin{gather*}
B' = \left\{\mathbf{y}  \in {\mathbb{R}}^2 \mid \mathbf{x}  \prec \mathbf{y}  	ext{ or } \mathbf{y}  \prec \mathbf{x} ight\}
\end{gather*}
and $B = B' \cup \left\{\mathbf{x} ight\}$.
In contrast to Example~1, we here claim that $B = L_{y_0}$, which is to say that $B$ \emph{does} define the maximal simply ordered subset.
\begin{proof}
Consider any $(x,y) \in B = B' \cup \left\{\mathbf{x} ight\}$ so that either $(x,y) \in B'$ or $(x,y) = \mathbf{x} $.
Clearly if $(x,y) = \mathbf{x}  = (0, y_0)$ then $(x,y) \in L_{y_0}$ since $y = y_0$.
On the other hand, if $(x,y) \in B'$ then $(x,y) \prec \mathbf{x} $ or $\mathbf{x}  \prec (x,y)$.
In the former case we have that $(x,y) \prec \mathbf{x}  = (0, y_0)$ so that, by definition $y = y_0$ and $x < 0$.
Clearly then $(x,y) = (x,y_0) \in L_{y_0}$ by definition.
In the latter case we also have $y = y_0$ (though this time $0 < x$) so that again $(x,y) \in L_{y_0}$.
Since $(x,y)$ was arbitrary, this shows that $B \subset L_{y_0}$.

Now consider any $(x,y) \in L_{y_0}$ so that $y = y_0$.
If $x = 0$ then $(x,y) = (0, y_0) = \mathbf{x} $ so that obviously $(x,y) \in \left\{\mathbf{x} ight\}$.
If $0 < x$ then $(x,y) = (x, y_0) \prec (0, y_0) = \mathbf{x} $ so that $(x,y) \in B'$.
Similarly, if $x < 0$, then $\mathbf{x}  = (0, y_0) \prec (x, y_0) = (x,y)$ so that again $(x,y) \in B'$.
Hence in all cases either $(x,y) \in B'$ or $(x,y) \in \left\{\mathbf{x} ight\}$ so that $(x,y) \in B' \cup \left\{\mathbf{x} ight\} = B$.
This shows that $L_{y_0} \subset B$ since again $(x,y)$ was arbitrary.

Thus we have shown that $B = L_{y_0}$ as desired.
\end{proof}
So it would seem that, in this example, this naive technique does work!

Exercise 11.3

Answers

Comments

Exercise 11.3

Answers

Comments

Add answer