Minimal Characterization of N (3.3.2)

Hrbacek and Jech Introduction to Set Theory, chapter 3, section 3, exercise 2:

Let $(A,\prec)$ be a linearly ordered set. For $p,q∈A$ we say $q$ is the successor of $p$ if $q$ is the $\prec$-least element of the set of elements greater than $p$, if it exists. Assume $A$ is nonempty and the following properties hold:

1. Every $p∈A$ has a successor.
2. Every nonempty subset of $A$ has a $\prec$-least element.
3. Every $p∈A$ which is not the $\prec$-least element of $A$ is a successor to some $q∈A$.

Show $(A,\prec)≅(ℕ,<)$. Show that the the condition may not hold if one of (a)-(c) is not assumed.

Proof: We shall show the conditions of Theorem 3.4 hold. 3.4(a) holds because $p \prec S(p)$, 3.4(b) is exactly the same here, and to observe 3.4(c) let $B⊆A$ be nonempty with nonempty set of upper bounds $C$; then $C$ has a $\prec$-least element $c$, and if $c$ is the $\prec$-least element of $A$, then $c$ can be the only element of $B$ and $c$ is also the $\prec$-greatest element of $B$. So we can assume $c=S(d)$ for some $d$, where if we assume $c∉B$ we cannot have $d \prec b$ for any $b$ or else either $c$ is the $\prec$-greatest element of $B$ or we have $d \prec b \prec c$ and $c$ is not the successor of $d$. Hence $d$ is an upper bound of $B$ strictly smaller than $c$, a contradiction.

Now, we will present examples $(A,\prec)$ not isomorphic to $(ℕ,\prec)$ each failing exactly one of the properties (a)-(c). $¬$(a) Let $A=\{∅\}$ with $∅ \not \prec ∅$; then $∅$ is the $\prec$-least element of the only nonempty subset of $A$, and (c) is vacuous. $¬$(b) One may examine $(ℤ,<)$ as an example, though it has not been constructed yet; we will imitate it with the set $A=\{+,-\}×ℕ-\{(-,0)}$ where $+,-$ are any two distinct sets, under the relation $a \prec b$ as in $ℤ$ (formalize this by setting the relation $\prec '$ on $\{+\}×ℕ$ as in $(ℕ,<)$, the relation $\prec ''$ on $\{-\}×ℕ-\{(-,0)\}$ as that on $(ℕ,>)$, and take their union under the relation $a \prec b$ where every element of $\{-\}×ℕ-\{(-,0)\}$ is less than all of $\{+\}×ℕ$). We see that every element in $ℤ$ has a successor, and every element is a successor to another, yet is not isomorphic to $ℕ$ as it does not have a least element. $¬$(c) Take the set $N×N$ under the relation $(a,b) < (c,d)$ if $a < c$ or $a=c$ and $b < d$. This is seen to be a linear order, where the successor of $(a,b)$ is $(a,b+1)$ and where the least element of a nonempty subset $A$ is the element $(x,y)$ where $x$ is the least element of $\{n∈ℕ | ∃m, (n,m)∈A\}$ and $y$ is the least element of $\{m∈ℕ | (x,m)∈A\}$. Yet $(1,0)$ is clearly seen not to have a least element and not to be the least element of $ℕ×ℕ$, hence an isomorphism cannot be constructed.$~\square$