Exercise 11.4

Proof. First, we show that $A$ is simply ordered by $\prec$. Consider distinct $(x_0,y_0)$ and $(x_1,y_1)$ in $A$ so that $y_0=x_0^3$ and $y_1=x_1^3$. Since they are distinct, it has to be that $x_0\ne x_1$ or $y_0\ne y_1$. The latter case actually implies the former since the function $f(x)=x^3$ is a well-defined function. Hence we can assume that $x_0\ne x_1$, from which we can also assume without loss of generality that $x_0<x_1$. Since $f(x)=x^3$ is also a monotonically increasing function (which is easy to show), it then follows that $y_0=x_0^3<x_1^3=y_1$. Thus we have that $x_0<x_1$ and $y_0\le y_1$ so that $(x_0,y_0)\prec (x_1,y_1)$ by definition. Since $(x_0,y_0)$ and $(x_1,y_1)$ were arbitrary, this shows that $\prec$ is a simple order on $A$.

To show that it is maximal suppose that $B$ is any proper superset of $A$ so that there is an $(x,y)\in B$ where $(x,y)\notin A$. Therefore clearly $y\ne x^3$ by definition. Now let $z=x^3$ so that $y\ne x^3=z$ but $(x,z)\in A$. Clearly, it is not true that $x<x$ so it can neither be that $(x,y)\prec (x,z)$ nor $(x,z)\prec (z,y)$. Hence $(x,y)$ and $(x,z)$ are incomparable in $\prec$. This shows that $B$ is not simply ordered and thus that $A$ is maximal since $B$ was an arbitrary superset. □

Proof. To show that $A$ is simply ordered consider distinct $(x_0,y_0)$ and $(x_1,y_1)$ in $A$ so that $y_0=y_1=2$. Since these points are distinct and $y_0=y_2$ it must be that $x_0\ne x_1$, from which we can assume that $x_0<x_1$ without loss of generality. But then clearly it is true that $x_0<x_1$ and $y_0\le y_1$ so that $(x_0,y_0)\prec (x_1,y_1)$. Since these points were arbitrary this shows that $A$ is simply ordered by $\prec$.

To show that it is maximal suppose that $B$ is any proper superset of $A$ so that there is an $(x,y)\in B$ where $(x,y)\notin A$. It then follows that $y\ne 2$ so that the point $(x,2)\in A$ but $(x,2)\ne (x,y)$. Clearly it can be that neither $(x,2)\prec (x,y)$ nor $(x,y)\prec (x,2)$ since it is not true that $x<x$. Hence $(x,y)$ and $(x,2)$ are incomparable in $\prec$. This shows that $B$ is not simply ordered by $\prec$. Since $B$ was an arbitrary superset this shows that $A$ is maximal. □

Proof. Consider the clearly distinct points $(-1,1)$ and $(0,0)$. Clearly since $0=0^2$ and $1={(-1)}^2$ these are both in $A$. However, since $1>0$ it is not true that $-1<0$ and $1\le 0$, and therefore it is not true that $(-1,1)\prec (0,0)$. Similarly since $0\ge -1$ it is not true that $0<-1$ and $0\le 1$, and therefore it is not true that $(0,0)\prec (-1,1)$. Hence the two distinct points are both in $A$ but are not comparable. This suffices to show that $A$ is not simply ordered by $\prec$. □

Proof. $\text{(⊂)}$ First consider any $A_f\in A$ so that $f:(a,b)\to ℝ$ with the properties above for some open interval $(a,b)$. To show that $A_f$ is simply ordered by $\prec$ consider any distinct $(x,y)$ and $(x^{\prime },y^{\prime })$ in $A_f$ so that $y=f(x)$ and $y^{\prime }=f(x^{\prime })$. Since these are distinct it follows that $x\ne x^{\prime }$ or $f(x)=y\ne y^{\prime }=f(x^{\prime })$. In the latter case, it also follows that $x\ne x^{\prime }$ as well for otherwise $f$ would not be a function. Hence we can, without loss of generality, assume that $x<x^{\prime }$. Since $f$ is non-decreasing it follows that also $y=f(x)\le f(x^{\prime })=y^{\prime }$, and therefore by definition $(x,y)\prec (x^{\prime },y^{\prime })$. Since these elements of $A_f$ were arbitrary, it follows that $A_f$ is simply ordered by $\prec$.

To show that $A_f$ is maximal consider any proper superset $A$ of $A_f$ so that there is an $(x,y)\in A$ where $(x,y)\notin A_f$. There are a few possible ways in which $(x,y)$ can fail to be an element of $A_f$.

Case: $x\in (a,b)$. Then it must be that $y\ne f(x)$ since $(x,y)\notin A_f$. Since it is not true that $x<x$, it has to be that neither $(x,y)\prec (x,f(x))$ nor $(x,f(x)),(x,y)$. Hence $(x,y)$ and $(x,f(x))$ are incomparable elements of $A$ (noting that clearly $(x,(f(x))\in A_f\subset A$) so that $A$ is not simply ordered by $\prec$.

Case: $x\ge b$. Note that this is only possible if $b<\infty$ so that $b\in ℝ$. Thus in this case we have that the image of $f$ is unbounded above by property (ii). Hence there is a $y_u\in \mathit{reals}$ where $y^{\prime }>y$ and $y^{\prime }$ is in the image of $f$. Thus there is also an $x^{\prime }\in (a,b)$ where $y=f(x^{\prime })$ so that $(x^{\prime },y^{\prime })\in A_f\subset A$. Now, we have $x^{\prime }<b\le x$ but $y^{\prime }>y$ so that it is not true that $y^{\prime }\le y$, and hence it cannot be that $(x^{\prime },y^{\prime })\prec (x,y)$. Similarly is it is clearly not true that $x<x^{\prime }$ so it cannot be that $(x,y)\prec (x^{\prime },y^{\prime })$ either. This shows that $(x,y)$ and $(x^{\prime },y^{\prime })$ are incomparable elements of $A$ so that $A$ is not simply ordered.

Case: $x\le a$. An argument analogous to the previous case shows that $a>-\infty$ so that the image of $f$ is unbounded below. From this, it follows again that $A$ is not simply ordered.

Thus in all cases $A$ is not simply ordered so that $A_f$ is a maximal simply ordered subset of ${ℝ}^2$ since $A$ was an arbitrary proper superset. This shows that $A_f\in B$ so that $A\subset B$ since $A_f$ was arbitrary.

$\text{(⊃)}$ Now consider any $B\in B$ so that $B$ is a maximal simply ordered set by $\prec$. Define

We prove that $B$ has the following properties:

(1)

If $(x_0,y_0)$ and $(x_1,y_1)$ are in $B$ and $x_0<x_1$ then $y_0\le y_1$.

(2)

For every $x\in X$ there is a unique $y\in ℝ$ where $(x,y)\in B$.

To show show (1) consider $(x_0,y_0)$ and $(x_1,y_1)$ in $B$ and suppose that $x_0<x_1$. Since $B$ is simply ordered, it must be that either $(x_0,y_0)\prec (x_1,y_1)$ or $(x_1,y_1)\prec (x_0,y_0)$. Since $x_0<x_1$ it clearly must be that $(x_0,y_0)\prec (x_1,y_1)$ and hence also $y_0\le y_1$.

To show (2) consider any $x\in X$. Clearly, there is a $y\in ℝ$ where $(x,y)\in B$ by the definition of $X$. To show that this $y$ is unique, suppose that $(x,y_0)$ and $(x,y_1)$ are both in $B$ but that $y_0\ne y_1$ so that $(x,y_0)$ and $(x,y_1)$ are distinct. Since $B$ is simply ordered they must be comparable in $\prec$ but they clearly cannot be since it is not true that $x<x$. As this is a contradiction, it must be that $y_0=y_1$.

With that out of the way, let $b$ be the least upper bound of $X$ if it is bounded above and $b=\infty$ otherwise. Similarly, let $a$ be the greatest lower bound if $X$ is bounded below and $a=-\infty$ otherwise. Now we claim that $X$ is equal to the open interval $(a,b)$.

So consider any $x\in X$ so that then clearly $a\le x\le b$ since $a$ and $b$ are lower and upper bounds of $X$, respectively. Clearly if $b=\infty$ then it cannot be that $x=b$ (since $x\in ℝ$) so assume that $b\in ℝ$ and $x=b$. Then $b=x\in X$ so that by property (2) there is a unique $y\in ℝ$ where $(b,y)\in B$. Clearly then $(b+1,y)\notin B$, since $b+1\notin X$, so that the set $B^{\prime }=B\cup \left\{(b+1,y)\right\}$ is a proper superset of $B$. Now consider any $(x^{\prime },y^{\prime })\in B$ so that clearly $x^{\prime }\in X$ and hence $x^{\prime }\le b<b+1$. By property (1) above it also follows that $y^{\prime }\le y$, and so we have that $(x^{\prime },y^{\prime })\prec (b+1,y)$. Since $(x^{\prime },y^{\prime })$ was arbitrary, this shows that $(b+1,y)$ is comparable to every element of $B$ and hence $B^{\prime }$ is simply ordered by $\prec$. But this is not possible since $B$ is maximal and $B^{\prime }$ is a proper superset. Hence it must be that $x\ne b$. An analogous argument shows that $x\ne a$ as well and hence $a<x<b$. Since $x$ was arbitrary this shows that $X\subset (a,b)$.

Now consider any $x\in (a,b)$ so that $a<x<b$. Since $b$ is the least upper bound of $X$, it has to be that $x$ is not an upper of $X$ so that there is an $x_g\in X$ where $x<x_g<b$ (clearly the existence of $x_g$ also follows when $b=\infty$ since then $X$ is unbounded above). Clearly then there is also a $y_g\in ℝ$ where $(x_g,y_g)\in B$. It then follows that the set $Y_g=\left\{y\in ℝ\mid (z,y)\in B\text{ for some }x<z<b\right\}$ is nonempty. By an analogous argument there is an $(x_l,y_l)\in B$ where $a<x_l<x$ so that the set $Y_l=\left\{y\in ℝ\mid (z,y)\in B\text{ for some }a<z<x\right\}$ is nonempty. Now, for any $y\in Y_g$, we have that $(z,y)\in B$ for some $x<z<b$. Therefore $x_l<x<z$ and by property (1) of $B$ we have that $y_l\le y$. Since $y$ was arbitrary this shows that $y_l$ is a lower bound of $Y_g$ and hence it has a greatest lower bound $y_v$. So suppose that $x\notin X$ so that there is not a $y\in ℝ$ where $(x,y)\in B$. Then we have that the set $B\cup \left\{(x,y_v)\right\}$ is a proper superset of $B$. However, consider any $(x^{\prime },y^{\prime })\in B$ so that $x^{\prime }\in X$ but $x^{\prime }\ne x$.

Case: $x^{\prime }<x$. Then it has to be that $a<x^{\prime }<x$ so that $y^{\prime }\in Y_l$. Then, for any $y\in Y_g$ we again have that $(z,y)\in B$ for some $x<z<b$. Hence $x^{\prime }<x<z$ so that $y^{\prime }\le y$ by property (1) since $(x^{\prime },y^{\prime })\in B$ and $(z,y)\in B$. Since $y$ was arbitrary, this shows that $y^{\prime }$ is a lower bound of $Y_g$. Since $y_v$ is the greatest lower bound of $Y_g$, we have that $y^{\prime }\le y_v$. Then clearly $(x^{\prime },y^{\prime })\prec (x,y_v)$ since also $x^{\prime }<x$.

Case: $x^{\prime }>x$. Then it has to be that $x<x^{\prime }<b$ so that $y^{\prime }\in Y_g$. It then follows that $y_v\le y^{\prime }$ since $y_v$ is the greatest lower bound of $Y_g$. Hence we have that $(x,y_v)\prec (x^{\prime },y^{\prime })$ since $x<x^{\prime }$ as well.

Therefore in all cases we have that $(x,y_v)$ and $(x^{\prime },y^{\prime })$ are comparable in $\prec$. Since $(x^{\prime },y^{\prime })$ was arbitrary, this clearly shows that $B\cup \left\{(x,y_v)\right\}$ is simply ordered. But this cannot be possible since it is a proper superset and $B$ is maximal! So it has to be that in fact there is a $y\in ℝ$ where $(x,y)\in B$, and hence $x\in X$. Since $x\in (a,b)$ was arbitrary, this shows that $(a,b)\subset X$. This completes the rather long proof that $X=(a,b)$.

Now, by property (2) there is a unique $y\in ℝ$ for every $x\in X=(a,b)$ where $(x,y)\in B$. So we define a function $f:(a,b)\to ℝ$ by simply setting $f(x)=y$. Clearly based on the way this function is defined and the fact that $(a,b)=X$ we have that $B=A_f$. We must now show that $f$ has the properties (i) through (iii) above.

Property (i) follows almost immediately from property (1) of $B$. To see this, consider any $x,y\in (a,b)$ where $x<y$. Then $(x,f(x))$ and $(y,f(y))$ are in $B$ and hence $f(x)\le f(y)$ by property (1). For property (ii) suppose that $b<\infty$ but that the image of $f$ is bounded above. Hence it image has an upper bound, say $y_u\in ℝ$, so that clearly $B\cup \left\{(b+1,y_u)\right\}$ is a proper superset of $B$. So consider any $(x,y)\in B$ so that $y=f(x)$ for some $x\in (a,b)$. Then clearly $f(x)$ is in the image of $f$ so that $y=f(x)\le y_u$ since $y_u$ is an upper bound of the image. Since also we must have $x<b<b+1$, it follows that $(x,y)\prec (b+1,y_u)$. Since $(x,y)\in B$ was arbitrary, this shows that $B\cup \left\{(b+1,y_u)\right\}$ is simply ordered, which cannot be possible since it is a proper superset and $B$ is maximal. So it has to be that in fact, the image of $f$ is unbounded above when $b<\infty$, which shows property (ii). An analogous argument shows property (iii).

Since $f$ has all of the required properties and $B=A_f$, this shows that $B\in A$. Clearly then $B\subset A$ since $B$ was arbitrary. This shows that $A=B$ as desired. □