Skip to main content
3 of 4
added 696 characters in body
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

The answer is yes. The additive cluster structure knows the additive structure of the original model up to isomorphism.

Theorem. The additive structure of any countable nonstandard model $M$ of $\newcommand\PA{\text{PA}}\PA$ can be recovered, up to isomorphism, from the induced additive structure on its clusters.

The cluster of an element in $M$ consists of all the elements at standard finite difference from it. Addition is well defined with respect to this congruence relation.

Proof. The first step is to realize that the standard system of $M$ is revealed in its additive structure. The standard system of $M$ consists of the sets $A\subseteq\newcommand\N{\mathbb{N}}\N$ that arise as the standard parts of a definable class in $M$. Since $M$ is a $\PA$ model, there are a variety of coding methods. If we use the prime-product coding, for example, then the standard system is easily seen using only the additive structure of $M$. Namely, we say that $A\subseteq\N$ is coded by element $a\in M$ if $k\in A\iff p_k$ divides $a$ in $M$, where $p_k$ is the $k$th prime. So $a$ is a multiple of the primes indexed by an element of $A$. Note that $p\mid a$ is determined by the additive structure alone, since it is equivalent to $\exists x(x+\cdots+x=a)$, where there are $p$ many summands.

Next, we argue (following Emil's comment) that the standard system is also revealed in the additive cluster structure. Namely, we can use two nonstandard elements $x<y$ to code the bits that consist of the standard part of the binary representation of the fraction $x/y$ as $M$ sees it. Note that this is visible from the additive cluster structure, since $\frac p{2^k}\leq \frac xy$ if and only if $p\cdot y\leq 2^k\cdot x$, which is equivalent to $y+\cdots+y\leq x+\cdots+ x$, where we take $p$ and $2^k$ many summands, respectively. For standard $p$ and $k$, this amounts to a property of the additive structure. Note, crucially, that since $x$ and $y$ are nonstandard, the standard binary bits of $x/y$ do not change when at most a finite standard change is made to $x$ or $y$. Thus, this method of coding is well defined with respect to the additive cluster structure, and so we can use the cluster addition operation. In short, the additive cluster structure knows the standard system of $M$.

Next, we seek to appeal to an additive version of the folklore result (variously attributed to Jensen and Ehrenfeucht 76, also Smoryński 81, and Wilmers) that a countable computably saturated model of $\PA$ is determined by its theory and its standard system.

We know that the additive reduct $\langle M,+^M\rangle$ is computably saturated. This can be seen as a consequence of the elimination of quantifiers for Presburger arithmetic, so any finitely satisfiable type turns into a finitely satisfiable type of bounded complexity, for which we have a definable truth predicate, and so by overspill the type is realized.

Finally, putting this together, we notice that indeed the additive version of the folklore result works just with $\PA$.

Lemma. If $M$ and $N$ are countable nonstandard models of $\PA$ with the same standard system, then the additive reducts are isomorphic. $$\langle M,+^M\rangle\cong\langle N,+^N\rangle$$

Proof. This is a back-and-forth argument. Enumerate the two models, and suppose we've defined finitely much of the isomorphism $\vec a\mapsto \vec b$, in such a way that the type of $\vec a$ in $M$ is the same as that of $\vec b$ in $N$. Note that the additive theory of $M$ is the same as the additive theory of $N$, since both are just Presburger arithmetic, which is complete. Consider the next element $a$. It's additive type over $\vec a$ is in the standard system of $M$ (this uses computable saturation, since we can write down a computable type of what it would be like for an element to code the type of $a$ over $\vec a$). So this type is also in the standard system of $N$. Furthermore, it is finitely realized in $N$, since if not, then there would be some finite part of that type that was not realizable over $\vec b$, but this is part of the type of $\vec b$, contrary to the fact that that part was realized in $M$ over $\vec a$. By computable saturation, this type must be realized in $N$, and so we can extend the isomorphism. $\Box$

Let us now complete the proof of the theorem by putting it all together. The additive cluster structure knows the standard system. The additive reduct of $M$ is computably saturated. And the isomorphism type of this is determined by these two facts. So the additive cluster structure determines the additive model $M$ up to isomorphism. $\Box$

Uncountable models. Regarding uncountable models, I know only a few things, but not the full picture.

First, the lemma above is not true for uncountable models, since one can have two models of PA of size $\omega_1$ with the same standard system, but one is $\omega_1$-like and one is not, so the additive reducts are not isomorphic. So one will need other ideas.

Meanwhile, evidently it is a theorem of Harnak that all $\omega_1$-like models of $\PA$ have isomorphic additive reducts. And being $\omega_1$ like is visible in the additive cluster structure, so this provides a sufficient condition for the additive cluster structure knows the additive reduct of the original model.

Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k