On interpretations of bounded arithmetic and bounded set theory

Notre Dame Journal of Formal Logic 50 (2):141-152 (2009)
  Copy   BIBTEX

Abstract

In 'On interpretations of arithmetic and set theory', Kaye and Wong proved the following result, which they considered to belong to the folklore of mathematical logic.

THEOREM 1 The first-order theories of Peano arithmetic and Zermelo-Fraenkel set theory with the axiom of infinity negated are bi-interpretable.

In this note, I describe a theory of sets that is bi-interpretable with the theory of bounded arithmetic IDelta0 + exp. Because of the weakness of this theory of sets, I cannot straightforwardly adapt Kaye and Wong's interpretation of the arithmetic in the set theory. Instead, I am forced to produce a different interpretation.

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 98,219

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

On Interpretations of Arithmetic and Set Theory.Richard Kaye & Tin Lok Wong - 2007 - Notre Dame Journal of Formal Logic 48 (4):497-510.
Bounded finite set theory.Laurence Kirby - 2021 - Mathematical Logic Quarterly 67 (2):149-163.
Bounded Scott Set Saturation.Alex M. McAllister - 2002 - Mathematical Logic Quarterly 48 (2):245-259.
Interpreting classical theories in constructive ones.Jeremy Avigad - 2000 - Journal of Symbolic Logic 65 (4):1785-1812.
Bi-interpretation in weak set theories.Alfredo Roque Freire & Joel David Hamkins - 2021 - Journal of Symbolic Logic 86 (2):609-634.
Structures interpretable in models of bounded arithmetic.Neil Thapen - 2005 - Annals of Pure and Applied Logic 136 (3):247-266.
The theory of hereditarily bounded sets.Emil Jeřábek - 2022 - Mathematical Logic Quarterly 68 (2):243-256.
An Independence Result on Weak Second Order Bounded Arithmetic.Satoru Kuroda - 2001 - Mathematical Logic Quarterly 47 (2):183-186.

Analytics

Added to PP
2009-08-07

Downloads
214 (#106,483)

6 months
27 (#117,931)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Richard Pettigrew
University of Bristol

Citations of this work

Bounded finite set theory.Laurence Kirby - 2021 - Mathematical Logic Quarterly 67 (2):149-163.
Constructive Ackermann's interpretation.Hanul Jeon - 2022 - Annals of Pure and Applied Logic 173 (5):103086.

Add more citations

References found in this work

Existence and feasibility in arithmetic.Rohit Parikh - 1971 - Journal of Symbolic Logic 36 (3):494-508.
On Interpretations of Arithmetic and Set Theory.Richard Kaye & Tin Lok Wong - 2007 - Notre Dame Journal of Formal Logic 48 (4):497-510.
Die Widerspruchsfreiheit der Allgemeinen Mengenlehre.Wilhelm Ackerman - 1937 - Journal of Symbolic Logic 2 (4):167-167.

Add more references