Foundations of Advanced Mathematics

We will prove the existence of maximal elements; the existence of minimal elements is similar, and we omit the details. Let $n=|A|\text{.}$ We proceed by induction on $n\text{.}$ If $n=1\text{,}$ then the single element of $A$ is clearly a maximal element. Now assume that $n\ge 2\text{.}$ Suppose that the result is true for $n-1\text{.}$ Let $w\in A\text{,}$ and let $B=A-\{w\}\text{.}$ By Exercise 7.4.8 we know that $(B,\preccurlyeq )$ is a poset. Because |$B|=n-1\text{,}$ it follows from the inductive hypothesis that there is a maximal element $p$ of $B\text{.}$ We now define $r\in A$ as follows. If $p\preccurlyeq w\text{,}$ let $r=w\text{;}$ if it is not the case that $p\preccurlyeq w\text{,}$ then let $r=p\text{.}$ We claim that $r$ is a maximal element of $A\text{.}$ There are two cases. First, suppose that $p\preccurlyeq w\text{.}$ Then $r=w\text{.}$ Suppose that there is some $y\in A$ such that $w\preccurlyeq y$ and $w\ne y\text{.}$ By transitivity it follows that $p\preccurlyeq y\text{,}$ and by antisymmetry it follows that $p\ne y\text{.}$ Because $y\ne w\text{,}$ then $y\in B\text{,}$ and we then have a contradiction to the fact that $p$ is a maximal element of $B\text{.}$ It follows that $w$ is a maximal element of $A\text{.}$ Second, suppose that it is not the case that $p\preccurlyeq w\text{.}$ Then $r=p\text{.}$ Because $p$ is a maximal element of $B\text{,}$ then there is no $x\in B$ such that $p\preccurlyeq x$ and $p\ne x\text{.}$ It follows that there is no $x\in A=B\cup \{w\}$ such that $p\preccurlyeq x$ and $p\ne x\text{,}$ and hence $p$ is a maximal element of $A\text{.}$

Let $p,q\in A\text{,}$ and suppose that both are least upper bounds of $X\text{.}$ By definition both $p$ and $q$ are upper bounds for $X\text{.}$ Because $p$ is a least upper bound of $X\text{,}$ and $q$ is an upper bound of $X\text{,}$ then $p\preccurlyeq q$ by the definition of least upper bounds. Similarly, we see that $q\preccurlyeq p\text{.}$ By antisymmetry, it follows that $p=q\text{.}$ A similar argument works for greatest lower bounds; we omit the details.

Let $n=|A|\text{.}$ We proceed by induction on $n\text{.}$ If $n=1$ the result is trivial. Now assume that $n\ge 2\text{.}$ Suppose that the result is true for $n-1\text{.}$ By Theorem 7.4.9 the poset $A$ has a maximal element, say $r\in A\text{.}$ Let $B=A\setminus \{r\}\text{.}$ By Exercise 7.4.8 we know that $(B,\preccurlyeq )$ is a poset. Because $|B|=n-1\text{,}$ it follows from the inductive hypothesis that there is a total ordering ${\preccurlyeq }^{″}$ on $B$ such that if $x\preccurlyeq y$ then $x{\preccurlyeq }^{″}y\text{,}$ for all $x,y\in B\text{.}$ Now define a relation ${\preccurlyeq }^{\prime }$ on $A$ as follows. If $x,y\in B\text{,}$ let $x{\preccurlyeq }^{\prime }y$ if and only if $x{\preccurlyeq }^{″}y\text{.}$ If $x\in A\text{,}$ let $x{\preccurlyeq }^{\prime }r\text{.}$ It is left to the reader in Exercise 7.4.9 to show that ${\preccurlyeq }^{\prime }$ is a total order on $A\text{,}$ and that if $x\preccurlyeq y$ then $x{\preccurlyeq }^{\prime }y\text{,}$ for all $x,y\in A\text{.}$

We follow [KR83a]. We prove the result by induction on $n\text{.}$ When $n=1$ the result is trivial. Now assume that $n\ge 2\text{.}$ Suppose that the result holds for $n-1\text{.}$ By Theorem 7.4.9 the poset $A$ has a maximal element, say $r\in A\text{.}$ Let $x\in A\text{.}$ Because $\preccurlyeq$ is a total ordering, we know that $x\preccurlyeq r$ or $r\preccurlyeq x\text{.}$ If it were the case that $r\preccurlyeq x\text{,}$ then by hypothesis on $r$ we would know that $r=x\text{.}$ Hence $x\preccurlyeq r\text{.}$ Let $B=A\setminus \{r\}\text{.}$ By Exercise 7.4.8 we know that $(B,\preccurlyeq )$ is a poset. Because $|B|=n-1\text{,}$ it follows from the inductive hypothesis that there is an order isomorphism from $(B,\preccurlyeq )$ to $(\{1,2,\dots ,n-1\},\le )\text{,}$ say $f:B\to \{1,2,\dots ,n-1\}\text{.}$ Let $F:A\to \{1,2,\dots ,n\}$ be defined by $F(x)=f(x)$ for all $x\in B\text{,}$ and $F(r)=n\text{.}$ Because $f$ is bijective, it is straightforward to see that $F$ is bijective as well; we omit the details. To see that $F$ is an order isomorphism, it suffices by Lemma 7.4.16 to show that $x\preccurlyeq y$ if and only if $F(x)\le F(y)\text{,}$ for all $x,y\in A\text{.}$ First, let $x,y\in B\text{.}$ Then $x\preccurlyeq y$ if and only if $f(x)\le f(y)$ because $f$ is an order isomorphism. Because $F(x)=f(x)$ and $F(y)=f(y)\text{,}$ then $x\preccurlyeq y$ if and only if $F(x)\le F(y)\text{.}$ Now let $z\in B\text{.}$ We know that $z\preccurlyeq r\text{,}$ and we also know that $F(z)\le n=F(r)\text{,}$ because $F(z)\in \{1,2,\dots ,n-1\}\text{.}$ Hence $z\preccurlyeq r$ if and only if $F(z)\le F(r)\text{,}$ because both these statements are true. It follows that $F$ is an order isomorphism.