Exercise 6.4

Proof. We show by induction that, for all $n\in {\mathbb{Z}}_{\text{+}}$, any simply ordered set with cardinality $n$ has a largest element. This of course shows the result since, by definition, $A\ne \varnothing$ has cardinality $n$ for some $n\in {\mathbb{Z}}_{\text{+}}$ when $A$ is finite.

First, suppose that $A$ is simply ordered and has cardinality 1 so that clearly $A=\left\{a\right\}$ for some element $a$. It is also clear that $a$ is trivially the largest element of $A$ since it is the only element.

Now suppose that any simply ordered set with cardinality $n$ has a largest element. Suppose that $A$ is simply ordered by $\prec$ and has cardinality $n+1$. Then there is a bijection $f$ from $A$ to $\left\{1,\dots ,n+1\right\}$, noting that obviously $f^{-1}$ is also a bijection. Clearly, $A$ is nonempty (since the cardinality of $A$ is $n+1>n>0$) so there is an $a\in A$. Let $A^{\prime }=A-\left\{a\right\}$ so that $A^{\prime }$ has cardinality $n$ by Lemma 6.1. Note also that clearly $A^{\prime }$ is simply ordered by $\prec$ as well (technically we must restrict $\prec$ to elements of $A^{\prime }$ so that it is really ordered by $\prec \cap (A^{\prime }\times A^{\prime })$). It then follows that $A^{\prime }$ has a largest element $b$ by the induction hypothesis. Since $a$ and $b$ must be comparable in $\prec$ by the definition of a simple order we have the following:

Case: $a=b$. This is not possible since $b\in A^{\prime }$ but clearly $a\notin A-\left\{a\right\}=A^{\prime }$.

Case: $a\prec b$. We claim that $b$ is the largest element of $A$. To see this, consider any $x\in A$ so that either $x=a$ or $x\in A^{\prime }$. In the former case clearly $x=a\preccurlyeq b$, and in the latter $x\preccurlyeq b$ since $b$ is the largest element of $A^{\prime }$. This shows that $b$ is the largest element of $A$ since $x$ was arbitrary.

Case: $b\prec a$. We claim that $a$ is the largest element of $A$. So consider any $x\in A$ so that $x=a$ or $x\in A^{\prime }$. In the first case obviously $x\preccurlyeq x=a$, and in the second $x\preccurlyeq b\preccurlyeq a$ since $b$ is the largest element of $A^{\prime }$. This shows that $a$ is the largest element of $A$ since $x$ was arbitrary.

Thus in all cases, we have shown that $A$ has a largest element, which completes the induction. □

Proof. We again show this by induction on the (finite) cardinality of the set. First, if $A$ is a simply ordered set with cardinality 1 then clearly $A=\left\{a\right\}$ for some $a$, which is clearly trivially the same order type as the section $\left\{1\right\}$.

Now suppose that all simply ordered sets of cardinality $n$ have the order type of a section of positive integers. Consider then a set $A$ simply ordered by $\prec$ that has cardinality $n+1$. Clearly, $A\ne \varnothing$ so that it has a largest element $a$ by part (a). Then the set $A^{\prime }=A-\left\{a\right\}$ has cardinality $n$ by Lemma 6.1. Since $A^{\prime }$ is also clearly simply ordered by $\prec$ (with the appropriate restriction) it follows from the induction hypothesis that it has order type of $\left\{1,\dots ,m\right\}$ for some $m\in {\mathbb{Z}}_{\text{+}}$. Since this also implies that $A^{\prime }$ has the cardinality of $m$, it has to be that $m=n$ since this cardinality is unique (by Lemma 6.5). So let $f^{\prime }$ be the order-preserving bijection from $A^{\prime }$ to $\left\{1,\dots ,m\right\}=\left\{1,\dots ,n\right\}$. Now define

for any $x\in A$. It is clear that $f$ is a function from $A$ to $\left\{1,\dots ,n+1\right\}$ since obviously $n+1\in \left\{1,\dots ,n+1\right\}$ and the image of $f^{\prime }$ is $\left\{1,\dots ,n\right\}\subset \left\{1,\dots ,n+1\right\}$.

Consider next any $x$ and $x^{\prime }$ in $A$ where $x\prec x^{\prime }$. Suppose for the moment that $x=a$. Then $x^{\prime }\preccurlyeq a=x$ since $a$ is the largest element of $A$. This contradicts the fact that $x\prec x^{\prime }$ so that it must be that $x\ne a$. Then $f(x)=f^{\prime }(x)$. If also $x^{\prime }\ne a$ then clearly $f(x)=f^{\prime }(x)<f^{\prime }(x^{\prime })=f(x^{\prime })$ since $f^{\prime }$ preserves order. If $x^{\prime }=a$ then $f(x^{\prime })=n+1$ so that $f(x)=f^{\prime }(x)\le n<n+1=f(x^{\prime })$ since the image of $f^{\prime }$ is only $\left\{1,\dots ,n\right\}$. Hence in all cases $f(x)<f(x^{\prime })$ so that $f$ preserves order since $x$ and $x^{\prime }$ were arbitrary. Note that this also shows that $f$ is injective since, for any $x,x^{\prime }\in A$ where $x\ne x^{\prime }$, we can assume without loss of generality that $x\prec x^{\prime }$ (since it must be that $x\prec x^{\prime }$ or $x^{\prime }\prec x$) so that $f(x)<f(x^{\prime })$, and hence $f(x)\ne f(x^{\prime })$.

Lastly consider any $k\in \left\{1,\dots ,n+1\right\}$. If $k=n+1$ then clearly by definition $f(a)=n+1=k$, noting that obviously $a\in A$. On the other hand, if $k\ne n+1$ then it has to be that $k<n+1$ so $k\le n$. Then $k\in \left\{1,\dots ,n\right\}$, which is the image of $f^{\prime }$ so that there is an $x\in A^{\prime }$ where $f^{\prime }(x)=k$ since $f^{\prime }$ is bijective (and therefore surjective). Since $x\in A^{\prime }$ we have that $x\in A$ but $x\ne a$ so that $f(x)=f^{\prime }(x)=k$. This shows that $f$ is surjective since $k$ was arbitrary.

Thus we have shown that $f$ is an order-preserving bijection from $A$ to $\left\{1,\dots ,n+1\right\}$, which completes the induction since by definition $A$ has order type $\left\{1,\dots ,n+1\right\}$. □