Prove that $(X, <)$ is isomorphic to $(\mathbb{Z}, <_i)$

Question

Let $(X, <)$ be a linearly ordered set such that

a) $X$ does not have a minimum or a maximum.

b) Every bounded subset of $X$ is finite.

Then, $(X, <)$ is isomorphic to $(\mathbb{Z}, <_i).$

Where $<_i$ is defined as: $a,b \in \mathbb{Z},$ $a<_ib$ if and only if $b-a \in \mathbb{Z}^+$

I know how to prove that $\mathbb{Z}$ is not bounded, and this property resembles the fact that $X$ does not have a maximum or a minimum. I also know that the interval $[a,b]= \{x \in \mathbb{Z} : a \leq_i x \leq_i b\}$ is finite. Merely because $[a,b]$ has the same cardinality as $[0,b-a]$; an interval for which there exists a biyection with the naturals.

So, using b), as every bounded subset of $X$ is finite, then there exists a biyection between any of these sets and a finite ordered subset of $\mathbb{N}.$

$\mathbb{N} \subseteq \mathbb{Z}$ and moreover, if $Y=[s,t]$ is a finite interval of $\mathbb{N}$ there is a biyection between Y, and an interval $[a,b]= \{x \in \mathbb{Z} : a \leq_i x \leq_i b\}$ which has the same cardinality of $Y.$ For example, let $n \in \mathbb{N}, n \in Y.$ Define $f : \mathbb{N} \rightarrow \mathbb{Z}$ such that $ f(n) = x-a.$

So then it is clear that the bounded subsets of $X$ are in correspondence with the bounded subsets of $\mathbb{Z}.$ But this doesn't prove that $(X, <)$ is isomorphic to $(\mathbb{Z}, <_i),$ because I still don't know how to use a) . I don't know if I shoud propose another infinite biyection between the whole $X$ and $\mathbb{Z}.$ If so, I don't really know what would this function look like.

Alternatively, I studied a proposition which asserts that there exists an isomorphism between well ordered sets (and other 3 conditions imposed in this set) and natural numbers. The proof of this uses the Recursion Theorem. Maybe I shoud also use this theorem in this problem, but I am really lost with this idea.

Answer 1

Given $x\in X$, define the successor function $S$ such that $S(x)$ is the minimum of the set $U=\{y: y\gt x\}$

To show that this is well defined we must establish that $U$ is nonempty and has a minimum element.

$X$ has no maximum so there exists an element greater than $x$ so $U$ is nonempty. Let $v\gt x\in U$ and let $V=\{z\in U: z\le v\}$. $V$ is nonempty, bounded below by $x$ and bounded above by $v$. Therefore $V$ is finite and so has a minimum element, call it $m$. If $u\in U$ is in $V$ then $m\le u$ because $m$ is the minimum of $V$. If $u\notin V$ then $m\le v\lt u$ so $m\lt u$.

Therefore, the successor function $S$ is well defined. A similar set of arguments allow us to define a predecessor function $P$ such that $P(x)$ is the maximum of $L=\{y:y\lt x\}$.

Using the functions $S$ and $P$ we can construct an isomorphism between $(\mathbb Z,\lt_i)$ and $(X, \lt)$.

Choose $x_0\in X$. Define an isomorphism $\phi:\mathbb Z\rightarrow X$ by $\phi(0)=x_0$, $\phi(n) = S^n(x_0)$ for $n\gt 0$ and $\phi(n)=P^n(x_0)$ for $n\lt 0$.

To show that $\phi$ is an isomorphism we must establish some facts about our successor and predecessor functions.

1. If $P^m(x) = S^n(x)$ then $m=n=0$.

This is easy to see because $P^m(x)\lt x$ for $m\gt 0$ and $S^n(x)\gt x$ for $n\gt 0$.

2. $m\lt n\implies S^m(x)\lt S^n(x)$.

$S^n(x)\ge S(S^m(x))\gt S^m(x)$

3. $m\lt n\implies P^m(x)\gt P^n(x)$.

$P^n(x)\le P(P^m(x))\lt P^m(x)$

4. Given $y\in U$, $y=S^n(x_0)$ or $y=P^n(x_0)$ for some $n$.

If $y=x_0$ then $n=0$. Suppose $y\gt x_0$. Then the set $\{z: x_0\le z\le y\}$ is bounded and so is finite. If it contains $n$ elements then $y=S^{n-1}(x_0)$

A similar argument can be used if $y\lt x_0$.

Now we are ready to show that $\phi$ is an isomorphism.

If $\phi(m)=\phi(n)$ then by considering $1$, $2$ and $3$ above, $m=n$ so $\phi$ is injective.

Given $x\in X$, by $4$ above $x=S^n(x_0)$ or $x=P^n(x_0)$ for some n. If $x=x_0$ the $\phi(0)=x$; if $x\gt x_0$, then $\phi(n) = x$ and if $x\lt x_0$ then $\phi(-n) = x$. Therefore, $\phi$ is surjective.

By $1$, $2$ and $3$ above, $\phi$ preserves order so it is an isomorphism.