[FOM] Plea for literature on recursion theory in V_\omega

Ali Enayat ali.enayat at gmail.com
Wed Apr 30 18:08:32 EDT 2008

This is a reply to Csaba Henk's query, who has asked for reference on:

 > [snip] Or any book which discusses the well-known
 > semantic equivalence (yes, this is a vague term, but you should know
 > what I mean...) of <\omega, + , *> and <V_\omega, \epsilon> ?

1. The most recent paper on the above subject, with many references to
the literature, is the following:

Kaye, Richard and Wong, Tin Lok
On interpretations of arithmetic and set theory.
Notre Dame J. Formal Logic 48 (2007), no. 4, 497--510.

Note: you can find a more complete version of the paper below:

The above paper corrected the misconception that PA is
bi-interpretable with "finitistic ZF set theory" ZF_fin, defined via

ZF_fin: = ZF \ {Infinity} + {the negation of Infinity}.

More explicitly, Kaye and Wong show [by analysing the Ackermann
interpretation, and building an inverse for it] that PA is
bi-interpretable with ZF_fin + TC, where:

TC:= "every set has a transitive closure"

[indeed they show the stronger statement that the above two theories
are definitionally equivalent]. Note that it has long been known that
ZF_fin does not prove TC.

In a recent paper (almost ready for public dissemination) with Jim
Schmerl and Albert Visser, we have shown, among other things, that
even a modest form of bi-interpretability does not hold between PA and

2. You may also wish to consult the following text:

Mayberry, J. P.
The foundations of mathematics in the theory of sets.
Encyclopedia of Mathematics and its Applications, 82. Cambridge
University Press, Cambridge, 2000.

Best regards,

Ali Enayat

More information about the FOM mailing list