Subsets of N are Countable (3.3.6)

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

Let $X⊆ℕ$; prove there exists a one-to-one sequence $f$ onto $X$.

Proof: Let $X$ be nonempty; then let $a∈X$ be the least element of $X$. We define the sequence $f$ by$$f_0 = a$$$$f_{n+1}=g(f_n,n)$$where $g(x,n)$ is the least element of $\{y∈X~|~y > x\}$ when it exists (cf. 3.3.5). Now, we let $P(n)$ be the proposition: if $n∈X$, then $n=f_m$ for some $m∈ℕ$. We shall prove it by total induction. Let $k∈X$. If $X∩k$ is empty, then $k$ is the least element of $X$ and $k=f_0$; otherwise let $p$ be the largest element of this bounded subset. We see $k > p$, and if $r > p$ then $r∉X∩k$ and hence either $r ≥ k$ or $r∉X$, implying $k$ is the least element of $\{y∈X~|~y > p\}$, i.e. $k=g(p,n)$ for all $n∈N$. Since $k > p$ we have $p=f_m$ for some $m$ and now $k=f_{m+1}$. Hence $\text{ran }f=X$.

We shall now prove by double induction (cf. 3.2.13) that $m < n$ and $f_m,f_n$ existing implies $f_m < f_n$, so $f$ is one-to-one. If $n = 0$ then the case is vacuous, so let $n=k+1$ with $m≤k$. If $m=k$ then $f_m < f_n = f_{m+1}$ by the definition of $f$. If $m < k$ then by inductive assumption $f_m < f_k < f_{k+1} = f_n$ and now $f_m < f_n$. This completes the induction and the proof.$~\square$

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$