Generalizations of PA and its standard and non-standard models

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

1. $(\forall x) \neg Sx = 0$
2. $\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$:

1. $(\forall x) \neg S_ix = 0\ \ \$ for $i = 1,...,n$
2. $\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 a non-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?

-
I think you mean "... and ${\mathbb N}+{\mathbb Z}\cdot{\mathbb Q}$ as the order type of its countable non-standard models." –  Adam Aug 18 '11 at 19:58
I have the sense (possibly wrong) that you are or are about to conflate "first-order theory" with "Modifier first-order theory" where Modifier could be "finitely axiomatized" or "recursively axiomatized". I request you edit the question to add clarity for this and other issues. Also, with respect to the $T_\omega$ structure, what besides its first order properties do you want to capture with its first order theory? Gerhard "Ask System Design" Paseman, 2011.08.18 –  Gerhard Paseman Aug 18 '11 at 20:02
My understanding was, that N+Z⋅Q is "necessary" only in the presence of addition and multiplication. Am I wrong? –  Hans Stricker Aug 18 '11 at 20:06
You are right, Hans. However you probably shouldn't say "Peano's Axioms" to refer to just these two axioms -- it's a bit confusing. –  François G. Dorais Aug 18 '11 at 20:26
@Hans: Keep reading the page until you hit the first-order axioms. You will see that first-order Peano Arithmetic also need axioms for $+$ and $\times$. Peano originally formulated the axioms in second-order logic. This circumvents that difficulty because $+$ and $\times$ already exist as second-order objects and they only need to be characterized. In any case, the Peano Axioms (in both first-order and second-order forms) include induction axioms. –  François G. Dorais Aug 18 '11 at 21:14

Let me begin by describing a particular non-standard model $M$ of the theory of $n$ successor functions, i.e., of the complete first-order theory of the $n$-fold branching tree $T$. $M$ consists of $T$ plus the set $A$ of all infinite sequences of elements of $\{1,2,\dots,n\}$. $S_i$ acts on $A$ by sending any sequence $(a_0,a_1,\dots)$ to $(i,a_0,a_1,\dots)$.

One might call $M$ "the standard non-standard model", but the analogy with $\mathbb N+\mathbb Z$ fails in at least one respect: $M$ has many nonstandard components. In more detail, consider the graph whose vertices are the elements of the model and whose edges connect any element to any of its $n$ successors. The graph corresponding to the standard model is connected. When $n=1$, the graph corresponding to $\mathbb N+\mathbb Z$ has just two components. But when $n>1$, the graph corresponding to my $M$ has $\mathfrak c$ (the cardinal of the continuum) connected components. Two elements of $A$ are in the same component iff they become equal after you delete some finite initial segments (possibly of different lengths) from each of them. If an analog of $\mathbb N+\mathbb Z$ should have just two components, then it would have to consist of $T$ plus a single component of $A$, and I see no good reason to prefer one component over another.

A general model of the complete first-order theory of $T$ would consist of $T$ plus, for each component of $A$, some cardinal number of disjoint copies of that component.

Thus, for $n>1$, this first-order theory is not $\omega$-stable (and in particular not $\aleph_1$-categorical, in contrast to the $n=1$ case), but, unless I'm overlooking something, it is superstable. (In particular, whether or not $n>1$, it does not have a definable linear ordering, contrary to what some comments seem to have presupposed.)

-
In the case $n=1$, the theory of $(N,S)$ admits a considerably simpler axiomatization than that given by the induction schema. One needs axioms saying that 0 is not a successor, that $S$ is one-to-one, that there are no finite $S$-cycles (one axiom for each length of cycle), and that every element except 0 is in the image of $S$. I think a similar axiomatization works in the case of $n$ successor functions. –  Andreas Blass Aug 18 '11 at 23:42

Regarding Question 2, rather than having finitely many function symbols $S_n(x)$, the easiest solution is to have a single relation symbol $S(n,x,m)$ asserting that the "$n$-labeled" successor of $x$ is $m$. Then your induction axiom can quantify over this:

$$\phi(0)\ \&\ {\Large[}(\forall x,n,m)\ \phi(x)\ \&\ S(n,x,m)\ \Rightarrow\ \phi(m){\Large]}\ \Rightarrow\ (\forall x)\phi(x)$$

The only problem remaining is that the scheme above allows the labels themselves to be "tree-shaped natural numbers". If you want the labels on the edges to be "linear natural numbers" (i.e. only one successor for each element), you'll need to include a separate copy of Peano's axioms in your theory, and simulate a two-sorted theory by including a unary relation (predicate) symbol which distinguishes "linear" naturals from "tree-shaped" naturals and asserts that an element of one kind is never the successor of an element of the other kind.

-
@Adam: Interesting! –  Hans Stricker Aug 18 '11 at 20:36

There are apparently missing axioms in the question. “Peano arithmetic” in the signature $\{0,S\}$ is not axiomatized by the two axioms given, since the axioms have a two-element model $\{0,\infty\}$ where $S(0)=S(\infty)=\infty$. One needs further axiom

$$\forall x\,\forall y\,(S(x)=S(y)\to x=y)$$

(expressing that $S$ is injective).

Now, the “standard model” with injective functions $\{S_i:i\in I\}$ (where $I$ can be finite or infinite of arbitrary cardinality) is nothing else than the term algebra (with no variables) in the signature $\{0\}\cup\{S_i:i\in I\}$. The complete theory of term algebras is well known, it can be easily axiomatized, and it enjoys quantifier elimination in an appropriate language (see e.g. Hodges’ “A shorter model theory” for details). In our case, the theory is axiomatized by

1. $\forall x\:S_i(x)\ne0$ for each $i\in I$
2. $\forall x\,\forall y\:S_i(x)\ne S_j(y)$ for each $i,j\in I$, $i\ne j$
3. $\forall x\,\forall y\,(S_i(x)=S_i(y)\to x=y)$ for each $i\in I$
4. $\forall x\:S_{i_0}(S_{i_1}(\cdots(S_{i_n}(x))\cdots))\ne x$ for each $n\in\omega$ and $i_0,\dots,i_n\in I$
5. $\displaystyle\forall x\,\Bigl(x=0\lor\exists y\,\bigvee_{i\in I}S_i(y)=x\Bigr)$ if $I$ is finite

In particular, in the finite case the induction schema follows from these axioms. On the other hand, the axioms 2, 3, and 4 do not follow from Hans’ axioms; in the case of 3 (the injectivity axiom), this is likely an omission (since the functions are described as injective), but I’m not sure about the others (though I find it unlikely that intended nonstandard models include the natural numbers endowed with $S_1(x)=\dots=S_n(x)=x+1$, or the model $\{0,a_n,b_n:n\in\omega\}$ where $S_1(0)=a_0$, $S_2(0)=b_0$, $S_1(a_{2n})=b_{2n}$, $S_2(a_{2n})=a_{2n+1}$, $S_1(b_{2n})=b_{2n+1}$, $S_2(b_{2n})=a_{2n}$, $S_1(a_{2n+1})=a_{2n+2}$, $S_2(a_{2n+1})=b_{2n+1}$, $S_1(b_{2n+1})=a_{2n+1}$, $S_2(b_{2n+1})=b_{2n+2}$). Notice also that in the Peano case $|I|=1$, axiom 4 follows from axioms 1, 3 and induction, but this is no longer true when $|I|\ge2$.

This axiomatization answers the original Question 2. Moreover, it may be helpful for understanding the structure of nonstandard models of the theory (since the induction-free axioms are more concrete) and to correct the axiomatization (if I’m right in believing that the incompleteness of Hans’ axioms is unintended).

-
@Emil: Sorry for the confusion. I hoped it was enough to say that S is injective (what I did). But I should have listed injectivity explicitly as an axiom. –  Hans Stricker Aug 19 '11 at 12:14
If you said something like “$S$ is injective and additionally satisfies the following axioms”, it would be enough (though still a bit confusing on the first sight). However, the way you wrote it, it looks like an assertion that injectivity follows from $S(x)\ne0$ and induction. Anyway: what about the other two axioms I mention? –  Emil Jeřábek Aug 19 '11 at 12:25
I understand axiom 2 (which I implicitly assumed when saying "pairwise injective"), but I didn't think of 4 and 5. I have to think about them. Thanks for your help! –  Hans Stricker Aug 19 '11 at 13:01
In case I didn’t make it clear, axiom 5 (unlike the others) follows from induction (but there is not really much point to include induction in the axiom system, since the only axiom it can save is 5). –  Emil Jeřábek Aug 19 '11 at 13:19
Thanks for the clarification. –  Hans Stricker Aug 19 '11 at 15:31