On interpretations of arithmetic and set theory (Q2425351): Difference between revisions

It is ``folklore knowledge'' that PA (Peano Arithmetic) and ZF-inf (Zermelo-Fraenkel set theory with the axiom of infinity negated) are mutually interpretable. Codes of bounded definable sets in a model of PA serve as a universe of a model of ZF-inf. Ordinals in a model of ZF-inf form a model of PA. However, as the authors say in the conclusions of the paper, ``[...] for the finer result with interpretations inverse to each other, careful axiomatization of the set theory is required.'' The main result is an interpretation of PA in finite set theory in which the domain of the interpretation is the whole set-theoretic universe. To achieve this, ZF-inf is replaced by ZF-inf plus the axiom declaring that every set is contained in a transitively closed set. The paper concludes with hierarchical variants of interpretations for fragments of PA and ZF and a discussion of difficulties and potential applications of similar results to weak fragments of arithmetic in which totality of the exponential function if not provable.