Extensions of the Ackermann interpretation to nonstandard theories of arithmetic

Question

In their paper, " On Interpretations of Arithmetic and Set Theory" (Notre Dame Journal of Formal Logic, Vol. 8, No. 4 (2007), pp. 497-510) in section 7, "Fragments of Arithmetic and Set Theory", Kaye and Wong make the following (interesting) remarks:

It is fairly straightforward to see that $I{\Delta_0}$ proves the Ackermann interpretation of many set theory axioms including extensionality, empty set, sum set, foundation, transitive closure, and the negation of the axiom of infinity.

Adding the further arithmetic axiom $exp$, ($\forall$$x$)($\exists$$y$)($y$=$2^x$), stating the totality of of the function $x$$\mapsto$$2^x$, we may prove the Ackermann interpretation of of the pair axiom and the power set axiom. Moreover, $exp$ is necessary as well as sufficient for these: to show $I{\Delta_0}$$\vdash$$Pair^{\mathfrak a}$$\rightarrow$$exp$ and $I{\Delta_0}$$\vdash$$Pow^{\mathfrak a}$$\rightarrow$$exp$, take a number $y$ and $2^x$, the smallest power of two greater than $y$. Then as $2^x$ codes the set {$x$}, by pair set or power set the set {$x$, {}} must also be coded, and this code can only be $2^{2^x}$+1. Thus $2^{2^x}$ exists and so therefore does $2^y$.

Furthermore, consider the following theorem of Ressayre as quoted by Ali Enayat in his answer to Mirco Mannucci's mathoverflow question, "Set Theory inside Arithmetic via the Ackermann Yoga":

Suppose $($ $M$, $+$, $\cdot$ $)$ is a nonstandard model of $PA$, and $\in_{Ack}$ is the Ackermann epsilon on $M$, i.e., $a$$\in_{Ack}$$b$ iff $M$ satisfies "the $a$-th digit of the binary expansion of $b$ is 1". Then for every consistent recursive extension $T$ of $ZF$ there is a subset $A$ of $M$ such that $($ $A$, $\in_{Ack}$ $)$ is a model of $T$.

Prof. Enayat then makes the following comment to Mirco in the the 'comments' section for the question:

$PA$ proves the negation of the axiom of infinity for the Ackermann interpretation, so far as the Ackermann interpretation is concerned, every set is "doomed" to be finite from $PA$'s point of view. So there indeed is a severe limit to the "Yoga", unless--as in Ressayre's theorem--one moves to an external venue.

It should be noted that Sayre and Wong, in their above remarks, seem to be working in that external venue.

Finally, consider the following statement Samuel Buss made regarding Rohit Parikh's 1971 paper "Existence and feasibility in arithmetic" in his own paper, "Bounded arithmetic, proof complexity and two papers of Parikh" (Annals of Pure and Applied Logic 96 (1999), 43-55):

(i) In section 3 of the "feasibility" paper, Parikh presents a model-theoretic result illustrating the gap between exponentiation and the feasible operations of addition and multiplication in models of arithmetic. Specifically, consider the axioms

$f$($x$,0)=1, $f$($x$, $y$+$z$)=$f$($x$,$y$) $\cdot$ $f$($x$,$z$)

$f$($x$,$S$($y$))=$x$ $\cdot$ $f$($x$,$y$), $f$($x$, $y$$\cdot$$z$)=$f$($f$($x$,$y$), $z$)

which uniquely characterize $f$($x$,$y$) as the exponentiation function $x^y$ in the standard integers. Parikh proved, however, that there is a non-standard model of Th($\mathbb N$) and two distinct function $f_1$ and $f_2$ on $M$ both of which satisfy the above four axioms for all values of $x$, $y$, $z$ $\in$ $M$. [Parikh seems to also be working in Ressayre's 'external venue'--my comment.]

Consider now Parikh's non-standard model $M_{Parikh}$. By Ressayre's theorem, there is a subset $A$ of $M_{Parikh}$ such that $($ $A$, $\in_{Ack}$ $)$ is a model of $ZF$, including the Axiom of Infinity.

Question: Does $M_{Parikh}$ 'know' that the Ackermann interpretation of the axiom of infinity is the axiom of infinity (in the 'external venue')?

Question: Is the set {0,1,2,3,...}=$\omega$ representable in $($ $A$, $\in_{AcK}$ $)$, and does $M_{Parikh}$ 'know' this?

Question: In a comment to Mirco regarding his question, Prof. Enayat writes: "Since $PA$ 'knows' about the completeness theorem (thanks to a theorem of Hilbert-Bernays), arithmetical models of such consistency statements can define an epsilon relation on themselves that turns them into models of set theory; moreover, the model of arithmetic has even a definable truth-predicate for such internal models of set theory. But such internal models, from the point of view of the ambient model of arithmetic, have nonstandard integers." Apparently, this is is also true of $M_{Parikh}$. In what way does $PA$ ($M_{Parikh}$) 'know' about the completeness theorem? Does $PA$ ($M_{Parikh}$) 'know' that $($ $A$, $\in_{Ack}$ $)$ is a model of $ZF$? How does Goedel's second incompleteness theorem apply here (how does $PA$ ($M_{Parikh}$) avoid inconsistency in this situation)?

Answer 1

Based on the comments, I think it's worth clarifying some points about the Ackermann interpretation.

The Ackermann interpretation is definable: it is a formula $\varphi(x, y)$, and - given a model $M\models PA$ - it gives us an interpreted structure $Ack(M)=(M, \varphi^M)$. This is true regardless of what $M$ is.

Now, some facts about $\varphi$ are provable in $PA$, and these facts in turn tell us things about the theory of the structure $Ack(M)$ associated to a model of $PA$. For example, $PA$ proves $$\forall x_1, x_2[\forall y[\varphi(y, x_1)\iff\varphi(y, x_2)]\iff x_1=x_2],$$ and this tells us that $Ack(M)$ satisfies extensionality. In fact, every axiom of $ZF-Inf+\neg Inf$ (call that theory "$T$" for simplicity), when appropriately phrased in terms of "$\varphi$" in place of "$\in$", is a provable sentence of $PA$ (this takes work); so if $M\models PA$, we will always have $Ack(M)\models T$.

In particular, this means we can never "get $\omega$" from the Ackermann interpretation of a model of $PA$. This can in fact be proved pretty easily: show that if $Ack(M)$ thinks $n$ is $\omega$, then $M$ thinks $n$ defines a proper cut in $M$, and this is impossible if $M\models PA$.

This should also help explain how Parikh's phenomenon is irrelevant here: the Ackermann interpretation leans on a specific formula, whereas Parikh shows that undefinable functions with certain properties can exist in some models.

---

Now let me say some things about definability/undefinability. There are a couple things worth pointing out:

• In terms of what a model $M$ "knows" about the substructure of $Ack(M)$ corresponding to a subset $A\subseteq M$, note that this question best makes sense if $M$ knows about $A$ to begin with. But most of the time, the $A$s we'll be interested in won't be definable in $M$: indeed, no model $W$ of ZF can be Ackermann-coded into any nonstandard model $M$ of PA in a definable way (since such an encoding would give evidence in $M$ of the non-standardness of whatever element of $M$ is coding the $\omega$ of $W$). So you have to be very careful when you ask "What does $M$ know?" about such a situation - what exactly do you mean, given that the most basic information about such a configuration will generally be undefinable in $M$?

• In terms of Parikh's model, let me recap what I said above in more detail. Any model of PA has a unique definable map satisfying the recursive properties of exponentiation. (Indeed, PA proves "there is a unique exponentiation function" in the following sense: PA proves "for all $n$, there is a unique map from $\{0, 1, . . . , n\}^2$ to $\mathbb{N}$ which satisfies [recursive properties]". Note that such a map is a finite object, so can be talked about directly in PA, even though the whole exponentiation map can't.) Ackermann coding works with respect to this definable map. Parikh showed that we can have undefinable maps that also satisfy the properties of exponentiation. But these maps aren't relevant to Ackermann coding.

Both bullet points really fall under the same category: although "strong foundational" theories (like PA and ZF) imply lots of rigidity about the universe in various ways, their nonstandard models have tons of flexibility, undefinably. For example, every nonstandard model $W$ of ZF contains a set model $m$ of ZF, even if it proves that ZF is inconsistent! . . . the trick being, of course, that the model is incorrect about what ZF is, and $m$ fails to satisfy some of the axioms of ZF$^W$, so the sense in which $m$ is a model of ZF is really undefinable. Similarly, Cohen's result that we can have a model of ZF with an automorphism of order $2$ is inherently about the undefinable structure of models, since no model of ZF has any definable automorphisms at all.

Ressayre's substructures and Parikh's exponentiations are examples of this "undefinable flexibility". But because they're appropriately undefinable, they're quite slippery, and don't interact with definable phenomena (like Ackermann coding) in any nice way.