6

Among the basic results of logic which, simple as they are, never fail to intrigue me, is Ackermann's interpretation of ZF-Infinity in PA (see for refs this MO question and here for an excellent overview)

Of course, the minus here is critical: PA does not know anything about infinite objects.

Yet, my curiosity is by no means $\aleph_0$-bound:one could add to some fragment of PA strong enough to verify all the axioms of ZF-infinity another axiom stating the existence of a number encoding an infinite countable set. That number would be non-standard in all models, but so what?

Perhaps the Ackermann Yoga can be pushed even further, attempting to add higher infinity axioms to the arithmetical theory, to "catch up" with Set Theory. The Ackermann's Yoga could give some insights on non standard models of arithmetics, by thinking of some nonstandard elements as large sets.

Has anything been investigated along these lines?

YCor
  • 60,149
Mirco A. Mannucci
  • 7,603
  • 2
    I'm imagining a non-mathematician reading titles involving the word "yoga" and asking himself in which perverted ways mathematicians use to convey ideas to each other... – Qfwfq Jun 07 '11 at 12:35
  • 1
    LOL!!! well, tell your non-mathematician to check out this MO question: http://mathoverflow.net/questions/64071/what-does-the-term-yoga-mean-in-mathematics

    PS As u certainly know, there are many types of Yoga (Hatha Yoga,the most popular, being only the first level): Raja Yoga, Jnana Yoga, etc. so why not Ackermann 's Yoga? It stretches your mind....

     – Mirco A. Mannucci Jun 07 '11 at 12:46
  • As a non-mathematician reading the title, I ask myself why mathematicians work so hard to avoid conveying ideas. – bof Jul 16 '20 at 00:16
  • @bof: But as a mathematician, do you think that mathematicians just want to have fun? – Asaf Karagila Jul 16 '20 at 07:26

3 Answers3

16

This question reminds me of a magical little-known theorem of Jean Pierre Ressayre that shows that every nonstandard model of $PA$ has a model of $ZF$ as a submodel of its Ackermann intepretation, more specifically:

Theorem. [Ressayre] 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 $\mathcal{M}$ satisfies "the $a$-th digit in 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$.

Proof Outline: By Löwenheim-Skolem, it suffices to consider the case when $M$ is countable. Choose a nonstandard integer $k$ in $M$, and consider the submodel $M_k$ of $(M,\in_{Ack})$ consisting of sets of ordinal rank less than $k$ [as computed within $(M,\in_{Ack})$]. "Usual arguments" show that $(M,\in_{Ack})$ has a Tarskian truth-definition for $M_k$, which in turn implies that $(M_k,\in_{Ack})$ is recursively saturated. Since $M_k$ is also countable, $(M_k,\in_{Ack})$ must be resplendent [which means that it has an expansion to every recursive $\Sigma^1_1$ theory that its elementary diagram is consistent with].

Now add a new unary predicate symbol $A$ to the language ${\in}$ of set theory and consider the (recursive) theory $T^A$ consisting of sentences of the form $\phi^A$, where $\phi \in T$, and $\phi^A$ is obtained by relativizing every quantifier of $\phi$ to $A$. It is not hard to show that $T^A$ is consistent with the the elementary diagram of $(M_k,\in_{Ack})$, so by replendence the desired $A$ can be produced.

[I will be glad to add clarifications]

Ressayre's theorem appears in the following paper:

J. P. Ressayre, Introduction aux modèles récursivement saturés, Séminaire Général de Logique 1983–1984 (Paris, 1983–1984), 53–72, Publ. Math. Univ. Paris VII, 27, Univ. Paris VII, Paris, 1986.

Ali Enayat
  • 17,058
  • I don’t see why $T^A$ is consistent with $(M_k,\in_{Ack})$. Doesn’t this require $M_k$ to satisfy all $\Sigma_1$ consequences of $T$, or something like that? – Emil Jeřábek Jun 07 '11 at 17:26
  • 3
    Aha, I’ll answer myself. $M_k$ is not an end-extension of $A$, hence it only needs to satisfy existential consequences of $T$ to make it work. Now, in set theory, there is no MRDP theorem, and existential sentences have very little expressive power: they assert the existence of a finite configuration of points with prescribed elementhood relation on them. It is easy to see that every such sentence is decidable in ZF without infinity (or its negation), hence if $T$ is consistent, its existential consequences are indeed valid in $M_k$. Alright, this is magic. – Emil Jeřábek Jun 07 '11 at 17:54
  • @Emil: Yes, you have the perfect explanation. – Ali Enayat Jun 07 '11 at 18:17
  • Indeed this results is a real pearl: totally fascinating! Do you know of any type of classification of nonstandard models of PA on the basis of how strong their internal set theory is? For instance, in certain models an Ackermann "ordinal" could be an inaccessible cardinal.. – Mirco A. Mannucci Jun 08 '11 at 19:10
  • 1
    @Mirco: Ressayre's result applies to all nonstandard model of $PA$, and all consistent extension $T$ of $ZF$, including those that assert the existence of large cardinals; so for better-or-worse, it does not lend itself as a tool of classification. Also, since the model produced in Ressayre's theorem is not "internal" to the ambient model of arithmetic, the theorem does not say much about the "internal set theory" of the model, rather, it shows it is so rich that, externally, we can carve out models of strong set theories from it. – Ali Enayat Jun 08 '11 at 21:07
  • Yes, I see your point Ali: Ressayre's model is not directly related to the "internal set theory" of the ambient model M. It is from outside that we know what M does not, namely that certain "sets" are infinite. As far as M is concerned, its internal set theory is all finite. Ok, but my initial question is not about PA. Instead, it can be reformulated this way: the ackermann yoga tells us that the only real distinction between set theory and arithmetics is that ZF knows about actual infinity, whereas PA does not. Very well. Then, can I start from an arithmetical theory strong enough to verify – Mirco A. Mannucci Jun 08 '11 at 22:17
  • Ackermann (but perhaps weaker than PA), and enrich it with axioms stating the existence of Ackermann's infinite "sets"? In other words, can I bridge the real gap between arithmetics and ZF all the while remaining in an arithmetical theory? And if yes, can I push this "catching up" to put on equal footings not only arithmetics and ZF, but actually ZF "beefed up" with high infinity axioms? – Mirco A. Mannucci Jun 08 '11 at 22:24
  • @Mirco: in some sense, the answer is yes, since you can add all kinds of consistency statements (of recursive theories, such as $ZF$ plus such and such large cardinals, to $PA$. Since $PA$ "knows" about the completeness theorem (thanks to a theorem of Hilbert-Barnays), 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. – Ali Enayat Jun 09 '11 at 02:54
  • [continued from above} But such internal models, from the point of view of the ambient model of arithmetic, have nonstandard integers. – Ali Enayat Jun 09 '11 at 02:55
  • Yes Ali, I see the point: you can take, say T= PA + CON(ZFC). Via the arithmetized completeness theorem, any model of T will be able to "construct" an inner model of ZFC. Same applies to stronger consistency statements, such as CON(ZFC + exists a Mahlo cardinal", etc. – Mirco A. Mannucci Jun 12 '11 at 20:41
  • But this is not exactly what i add in mind: my question is, can I add, via the Ackermann interpretation, a statement such as : There exist a number which is the code of an infinite set", or maybe even more, and get some Ackermann interpretation of ZF inside the arithmetical theory. In other words, are there limits for the Ackermann's yoga? – Mirco A. Mannucci Jun 12 '11 at 20:41
  • Mirco: $PA$ proves the negation of the axiom of infinity for the Ackermann interpretation, so as 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. – Ali Enayat Jun 13 '11 at 03:29
4

You might want to look into the notion of the standard system of a nonstandard model $M$ of PA. Any nonstandard member $x$ of $M$, determines, via your favorite coding, a subset $X$ of $M$ that is finite in the internal sense of $M$ but may be infinite when seen from outside $M$. Intersecting this $X$ with the standard part $\mathbb N$ of $M$, we get some subset of $\mathbb N$, and the family of all the intersections obtainable in this way, as $x$ varies over $M$, is called the standard system of $M$. With this definition, it's a collection of subsets of $\mathbb N$, but it corresponds, via Ackermann coding, to a collection of subsets of the set $HF$ of hereditarily finite sets (the standard model of ZF minus infinity).

Andreas Blass
  • 72,290
-1

I wrote a paper proposing a solution to this. https://www.mdpi.com/2075-1680/8/1/31

I am working on a newer version,

https://www.preprints.org/manuscript/202006.0098/v3

Juan Ramirez
  • 1