# Extensions of the Ackermann interpretation to nonstandard theories of arithmetic

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, sem 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)?

• Will you simplify this? There are 11 paragraphs of introduction here before any direction to a question. Then there are 6 questions, of which 4 use the word "know" in quotes. It would help to either ask directly for a formalization of "know", in which case the four questions here are secondary; or suggest a definition so you can ask the questions without the quote marks. – Matt F. Dec 29 '16 at 8:30
• The Ackermann interpretation is definable. That is, there is a formula $\varphi(x, y)$ - interpreted as "the set represented by $x$ is an element of the set represented by $y$ - such that PA proves that the structure $(\mathbb{N}, \varphi)$ is a model of ZF-Inf+$\neg$Inf. Note that "$\mathbb{N}$" here refers to the set of natural numbers as understood by the model of PA - this is what I meant by "appear finite": a nonstandard element of $M\models PA$ appears finite to $M$, even though it is externally infinite. Such an element will code an externally infinite set (cont'd) – Noah Schweber Dec 29 '16 at 16:49
• even though of course the Ackermann structure of $M$, $Ack(M)$, thinks that every set is finite. This is just the usual phenomenon of a theory PA or ZF-Inf+$\neg$Inf thinking that every object is finite, but having models with externally infinite objects. This addresses the "appears finite" issue. The other point is that the Ackermann interpretation is already extended to all of the model of PA, including the nonstandard elements! Parikh's model doesn't gain us anything here. You then write that the Ackermann interpretation of a nonstandard number should help define $\omega$; (cont'd) – Noah Schweber Dec 29 '16 at 16:51
• This is false. Think about how - even in a nonstandard model of PA - there are no definable cuts. If $M$ is a nonstandard model of $PA$, then $Ack(M)$ is a nonstandard model of $ZF-Inf+\neg Inf$, but it still satisfies $\neg Inf$ internally. So in particular it doesn't help you define $\omega$. I think the key point you are missing is that the Ackermann interpretation, being definable, makes sense for all elements of any model of PA, and the relevant facts about it, being PA-expressible (by the definability of the Ackermann interpretation) and PA-provable, are true in all models. – Noah Schweber Dec 29 '16 at 16:53
• The point is: definable phenomena aren't going to grant you surprising power, even in nonstandard models. And Parikh's exponentiations, being undefinable, play no role in the analysis of the Ackermann interpretation. – Noah Schweber Dec 29 '16 at 16:55

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.

• Could the existence of Parikh's undefinable maps which satisfy the axioms for exponentiation be added as extra axioms to $PA$? Could this new system define $\omega$ and negate the negation of the axiom of infinity (if this strategem is silly I will delete the comment)? – Thomas Benjamin Dec 30 '16 at 1:06
• @ThomasBenjamin First of all, let's make the question more precise. How do you express the existence of an undefinable map? What you could do is add a new function symbol $f$ to the language, and axioms asserting that it behaves like exponentiation yet is different from the actual (defined-as-usual) exponentiation function. The problem, now, is that the induction scheme of PA can't apply to formulas which use the symbol "$f$": otherwise consider the point of least difference between $f$ and "true" exponentiation. (continued) – Noah Schweber Dec 30 '16 at 1:09
• Besides, I don't really see how having a different exponential function around helps you - what exactly do you plan on doing with it? – Noah Schweber Dec 30 '16 at 1:15
• What I was hoping to do was develop a formal theory of arithmetic, slightly stronger than $PA$, whose models satisfy the axiom of infinity. I find it interesting that, in point of fact, $PA$ and $ZF$ with the axiom of infinity negated are bi-interpretable, and that $PRA$ + $TI({\epsilon_0})$ can prove the consistency of $ZF$ with the axiom of infinity negated (the bi-interpretability of $PA$ and $ZF$ with the negation of the axiom of infinity seems, superficially, to fly in the face of the late Edward Nelson's contention that $PA$'s induction axiom is somehow dependent – Thomas Benjamin Dec 30 '16 at 11:42
• (cont.) on the existence of a completed infinity. Having noticed (from the Kaye and Wong paper I quoted) that the axioms of $ZF$ with the axiom of infinity negated (under the Ackermann interpretation) are all theorems of $PA$, I was hoping to somehow develop an extension of the Ackermann interpretation in this extension of $PA$ I wished to develop that would derive the axiom of infinity as a theorem via its Ackermann interpretation. My questions were preliminary questions to get a feel for what could be done. (Note: The extension of $PA$ I wished to develop, was, of course, to be a – Thomas Benjamin Dec 30 '16 at 12:18