10
$\begingroup$

Given $\frak M$ a countable nonstandard model of $\sf PA$ and let $a\in M$ be a nonstandard element. A "cluster around $a$" is the set of successors and predecessors of $a$, a cluster is a subset of $M$ that is a cluster around some $a\in M$.

It is standard exercise to show that the set of clusters of $\frak M$ is order-isomorphic to $\mathbb Q$, and it is simple to see that it is not isomorphic to $\Bbb Q^+$ when adding the additive structure (this can be seen by looking at the bounded sequence $(nX\mid n\in\Bbb N)$ for some cluster $X$).

Indeed the additive structure of the clusters of $\frak M$ seems to be quite complicated, the similarity to $\Bbb Q^+$ doesn't even hold "locally" (in the sense that given any cluster $X$ there exists a cluster $Y$ such that $Y$ is bigger than $X$ and smaller than any $X+X/n$ for standard $n$ $^1$).

So the ordered additive structure of the clusters of $\frak M$ is quite complicated, which brings me to the following questions:

  1. Given $(C,<,+)$ the structure of clusters of $\frak M$, can we recover the additive structure on $M$?

  2. If the answer of the above is "yes", what about uncountable models?


$^1$ Note that division by a standard number is defined as $X/n$ is the unique cluster $Y$ such that there is $y∈Y$ and $x∈X$ with $yn=x$

$\endgroup$
10
  • 1
    $\begingroup$ Possibly relevant items: (1) The additive reduct of a nonstandard model of PA is computably saturated, and I think this will carry over to the additive cluster structure. (2) The standard system of a model of PA is visible in its additive structure, but I'm not yet sure if this is true for the additive cluster structure. Can we recover the standard system of a model of PA from its additive cluster structure? $\endgroup$ Commented Sep 8, 2023 at 12:53
  • 1
    $\begingroup$ A negative answer to my question in (2) about the standard systems could be seen as a strong negative answer to the question of the OP. If we cannot define the standard system from the additive cluster structure, then we cannot recover the additive structure of the original model, since the standard system is definable there. $\endgroup$ Commented Sep 8, 2023 at 13:17
  • 2
    $\begingroup$ @JoelDavidHamkins The additive cluster structure is a divisible ordered group. This theory has $2^\omega$ types, hence it has no countable saturated model at all. $\endgroup$ Commented Sep 8, 2023 at 13:53
  • 2
    $\begingroup$ Yes, I think so. Basically, represent a set of natural numbers by (the standard part of) the binary expansion of $x/y$, where $y>x>0$ are infinitely large. This is definable in the additive structure, and it is independent of the choice of representants of clusters because adding a finite number to $x$ or $y$ only changes the fraction by an infinitesimal amount. $\endgroup$ Commented Sep 8, 2023 at 14:03
  • 1
    $\begingroup$ Ah, very good. Now we can hope to recover the additive structure for countable models, if there is an additive version of Friedman's theorem. That is, perhaps additive computable saturation plus the standard system determines the additive structure. $\endgroup$ Commented Sep 8, 2023 at 14:13

2 Answers 2

7
$\begingroup$

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.

Multiplication. Incidently, there is a multiplicative version of the lemma, showing that if two countable models have the same standard system, then their multiplicative reducts are isomorphic. The proof is essentially the same overall structure as I gave above. The standard system is coded into the multiplicative structure, which is computably saturated, and from this the back-and-forth argument shows that the multiplicative structure is determined.

Conclusion: the additive cluster structure of a countable model of arithmetic also knows the multiplicative reduct of the original model up to isomorphism!

$\endgroup$
2
  • 1
    $\begingroup$ Amazing result! I'm surprised about how hard it is to see. Intuitively I would imagine that there is a clever encoding that will immediately give a way to recover the additive reduction of the original model. And I'm very surprised about the multiplicative result $\endgroup$
    – Holo
    Commented Sep 15, 2023 at 21:53
  • 1
    $\begingroup$ Vika Gitman and I are thinking about the uncountable case, and I will report back if we figure anything out. I'm inclined to expect counterexamples in the uncountable case, but the fact that the additive cluster structures knows the standard system and the order isomorphism type of the original model is confabulating. $\endgroup$ Commented Sep 15, 2023 at 22:00
7
$\begingroup$

If you intend literally to recover the addition operation of the given model $M$, then the answer is negative. For every nonstandard model of arithmetic $M$ there is another model $M'$ having exactly the same domain, the same clusters, with the same cluster order and cluster addition, but a different addition operation $+^M\neq +^{M'}$.

Given any $M$, construct a model $M'$ by shifting the individuals within some nonstandard cluster, but fixing all other individuals (or apply any permutation at all within a cluster, such as swapping two individuals only). That is, we define $M'$ so that $M$ is isomorphic to $M'$ by the map we considered. So the models $M$ and $M'$ will have the same domain and the same clusters, and their clusters will be in the same order, and since cluster addition is well defined with respect to finite shifts, the models have the same cluster addition operation. But they have different addition operations.

Conclusion: the addition operation of the model is not determined by the order relation and addition operation on the clusters.

But perhaps you aim at a more subtle manner of recovering the structure, where you recover the addition of $M$ up to isomorphism, instead of the actual operation $x+y=z$ on individuals.

$\endgroup$
4
  • 2
    $\begingroup$ Thanks for the answer, my intent in this question was the more general manner, indeed if we can show that given an additive cluster structure we can identify M up to isomorphism I would regard this as a positive answer $\endgroup$
    – Holo
    Commented Sep 8, 2023 at 19:07
  • $\begingroup$ Yes, of course. I think there is a strategy outline now described in the comments on the main thread. I'm checking with some models-of-PA friends of mine about generalizing the PA result on isomorphic comp saturated models with same theory and same standard system to the additive case, and if that works, then we'll get the positive result. $\endgroup$ Commented Sep 8, 2023 at 19:43
  • $\begingroup$ Great! I will be waiting for any updates $\endgroup$
    – Holo
    Commented Sep 8, 2023 at 20:15
  • $\begingroup$ @Holo I posted another answer explaining this proof. $\endgroup$ Commented Sep 13, 2023 at 18:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .