Consider Peano's axioms — in its first-order version and without addition and multiplication — with its single injective function $S$:

- $(\forall x) \neg Sx = 0$
- $\Big(\phi(0)\ \ \&\ \big( (\forall x)\ \phi(x) \Rightarrow \phi(Sx)\big)\Big) \Rightarrow (\forall x)\ \phi(x)\ \ \ $ for all first-order formulas $\phi(x)$

These axioms fix $\mathbb{N}$ as its standard model and $\mathbb{N} + \mathbb{Z}$ as its standard *non*-standard model.

Now consider a generalization with finitely many pairwise injective functions $S_i$, $i = 1,...,n > 1$:

- $(\forall x) \neg S_ix = 0\ \ \ $ for $i = 1,...,n$
- $\Big(\phi(0)\ \ \&\ \big( (\forall x)\ \phi(x) \Rightarrow (\phi(S_1x)\ \&\ ...\ \& \ \phi(S_nx))\big)\Big) \Rightarrow (\forall x)\ \phi(x)\ \ \ $ for all formulas $\phi(x)$

The standard model of these axioms is a rooted, directed, and appropriately edge-colored tree.

Question 1:But how does anon-standard model look like, containing a directed tree, infinite to-and-fro (as a generalization of $\mathbb{Z}$)? What is an example of such a tree?

Finally consider a generalization with countably many pairwise injective functions $S_i, i \in \mathbb{N}$. It's (relatively) easy to imagine an appropriate rooted tree $T_\omega$ — with $\omega$-many childs of each node — as a standard model.

Question 2:But of what first-order theory, actually?

Axiom (scheme) 1 is not a problem, but can the induction axiom (scheme) 2 be generalized for infinitely many functions?

While $\mathbb{N}$ can be at least partially captured — as a standard model — by a first-order theory, the corresponding $T_\omega$ cannot be captured at all by a first-order theory?

6more comments