How Many Countable Models of the successor function

Question

Consider the successor function (s(x)=x+1), $T_{S}$ to be the set of axioms given by;

S1: ∀xy[s(x)=s(y)→x=y] (injective)

S2: [s(x)≠0] (never 0)

S3: ∀x[x≠0→∃y[s(y)=x]] (everything bar 0 is in image)

S4n : ∀x[sn(x)≠x] (no cycles)

clearly $\langle N;s,0 \rangle$ is a model of TS and the upward Löwenheim–Skolem theorem theorem tells us there are models of TS of every infinite cardinality

I claim that there are $\aleph _{0}$ many countable models, how would i prove this claim?

Answer 1

HINT: Show (if you’ve not already done so) that a countable model of $T_S$ has the form $\Bbb N\cup(I\times\Bbb Z)$ for some countable $I$, where $s(\langle i,n\rangle)=\langle i,n+1\rangle$ for each $\langle i,n\rangle\in I\times Z$. Then show that if $|I|=|J|$, the resulting models are isomorphic. You will then have exactly one model for each $|I|\le\omega$. The key idea is that although the successor function determines a linear order on $\Bbb N$ and on each of the $\Bbb Z$-chains $\{i\}\times\Bbb Z$, it does not determine any ordering of the set of $\Bbb Z$-chains: they can be permuted arbitrarily.

Answer 2

If $\langle X,s,0\rangle$ is a model, we can define an equvalence relaton on $X$ via $x\sim y\iff \exists z\in X, n,m\in \mathbb N_0\colon x=s^n(z), y=s^m(z)$. The equivalnece classes are all isomorphic to $\mathbb Z$ (with standard successor function) or $\mathbb N_0$ (for the unique class that contains $0$). Conclude that $X\cong \mathbb N_0\sqcup \mathbb Z^I$ for some set $I$ and that $X$ is countable iff $I$ is countable.