Models of the successor function

715 Views Asked by At

I would like to ask a few questions about models of the succesor function (s(x)=x+1), intact that is a bit vague, consider $T_{S}$ to be the set of axioms given by;

S1: $\forall xy[s(x)=s(y) \rightarrow x=y]$ (injective)

S2: $[s(x) \neq 0]$ (never $0$)

S3: $\forall x[x \neq 0 \rightarrow \exists y[s(y)=x]]$ (everything bar $0$ is in image)

S$4_{n}$ : $\forall x[s^{n}(x)\neq x]$ (no cycles)

clearly $\langle \mathbb{N};s,0 \rangle$ is a model of $T_{S}$ and the upward Löwenheim–Skolem theorem theorem tells us there are models of $T_{S}$ of every infinite cardinality furthermore i have shown every model has a substructure isomorphic to $\mathbb{N}$ and then for a model M not equal to $\mathbb{N}$ each element that is not a natural number creates a copy of $\mathbb{Z}$

I proved this by saying that if a isn't an element of $\mathbb{N}$ (we are using this loosely here to talk about the substructure isomorphic to the naturals.) then it can't be one of the elements of $s^{k}(a_{0})$ so there has to be an element b such that $s(b)=a$ which also can't be any of the powers of the successor function, we do the same for b, etc and so we get a set of distinct elements isomorphic to the integers.

This is as far as i have gotten with my study of the successor function, what remains for me to show is the following,

1)Make the above more rigorous by showing that any model $M$ of $T_{s}$ is isomorphic to a model $M_{I}$ with domain $\mathbb{N} \cup (I \times \mathbb{Z})$ such that each $(i,n) \in (I \times \mathbb{Z})$ satisfies $S^{M_{I}}((i,n))=(i,n+1)$

2)Show that $M_{I_{1}} \cong M_{I_{2}}$ if and only if $I_{1}$ has the same cardinality as $I_{2}$

3)Show that the cardinality of $M_{I}$ is $ |I| + \aleph_{0}$

From all the above we know that $T_{S}$ is categorical in all uncountable cardinalities and it has no finite models so it is a complete theory (los caught) so our list of axioms is complete. Awesome!

I need help proving 1-3 any hints or model proofs would be greatly appreciated,

once that is done i need to answer one final thing

4)How many countable models are there up to isomorphism for $T_{S}$

1

There are 1 best solutions below

2
On

These axioms won't adequately describe the natural numbers. First, you should start with $s:\mathbb{N}\to \mathbb{N}$ or some equivalent.

Your axioms will not rule out a structure consisting of two main sequences -- one that looks like the regular set of natural numbers going off to infinity in one direction starting from $0$, the other like the integers going off to infinity in both directions.

$$ 0\to 1 \to 2\to 3 \to 4 \to\cdots$$

$$+$$

$$\cdots\to (-2)\to (-1) \to (+0) \to (+1) \to (+2)\to\cdots$$

Notice that there would be no cycles or loops here.

Your final axiom should be more like:

$$\forall P\subset \mathbb{N}: [0\in P \land \forall x\in P:[s(x)\in P] \implies P=\mathbb{N}]$$

This will rule out the above structure leaving you with only:

$$ 0\to 1 \to 2\to 3 \to 4 \to\cdots$$