On interpretations of bounded arithmetic and bounded set theory

DOI10.1215/00294527-2009-003MaRDI QIDQ1038653zbMATH OpenOpenAlexFDO

Authors Richard Pettigrew

Publication date 18 November 2009

Published in Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0807.4850

zbMATH Keywords

bounded inductionfinite set theoryinterpretations

Mathematics Subject Classification ID

Models of arithmetic and set theory (03C62)

Abstract: In a recent paper, Kaye and Wong proved the following result, which they considered to belong to the folklore of mathematical logic. THEOREM: The first-order theories of Peano arithmetic and ZF with the axiom of infinity negated are bi-interpretable: that is, they are mutually interpretable with interpretations that are inverse to each other. In this note, I describe a theory of sets that stands in the same relation to the bounded arithmetic IDelta0 + exp. Because of the weakness of this theory of sets, I cannot straightforwardly adapt Kaye and Wong's interpretation of arithmetic in set theory. Instead, I am forced to produce a different interpretation.

Review text

In [``On interpretations of arithmetic and set theory, Notre Dame J. Formal Logic 48, No. 4, 497--510 (2007; Zbl 1137.03019)], \textit{R. Kaye} and \textit{T. L. Wong} proved that Peano Arithmetic is bi-interpretable with the suitably formulated ZF set theory with the axiom of infinity negated. Pettigrew proves an analogous result for the theory \(\text{I}\Delta_0+\exp\). The corresponding set theory is a variant of the axiom system EA introduced by \textit{J. P. Mayberry} [The foundations of mathematics in the theory of sets. Encyclopedia of Mathematics and Its Applications. 82. Cambridge: Cambridge University Press (2000; Zbl 0972.03001)]. EA is a first-order theory in the language including the constant \(\emptyset\), function symbols for power set, sum set, pair set, and rank operations, as well as unary function symbols \(\{x\in y: \Phi(x)\}\) for each formula \(\Phi(x)\) in which each quantifier is bounded by a term. The system, called EA\(^*\), includes the axioms of Extensionality, Pair Set, Sum Set, Power Set, Foundation, Axiom Schema of Subset Separation for Bounded Formulas, Dedekind Finiteness, and a special axiom, called Weak Hierarchy Principle, which guarantees that for every set there exists the first level of the cumulative hierarchy at which that set occurs. The interpretation of EA\(^*\) in \(\text{I}\Delta_0+\exp\) is the standard Ackermann interpretation. The inverse interpretation uses arithmetic operations defined using a function that takes each level of the cumulative hierarchy \(V_n\) to a linear ordering of \(V_n\).

Recommendations

• On interpretations of arithmetic and set theory
• Models of arithmetic and categories with finiteness conditions
• Constructive Ackermann's interpretation
• An Effective Conservation Result for Nonstandard Arithmetic
• scientific article; zbMATH DE number 3875271
• Bounded Induction and Satisfaction Classes
• scientific article; zbMATH DE number 1289488
• A one axiom set theory based on higher order predicate calculus
• Typed lambda-calculus in classical Zermelo-Fraenkel set theory
• Truth In V for ∃*∀∀-Sentences is Decidable

Cited in

(9)

• Constructive Ackermann's interpretation
• On interpretations of arithmetic and set theory
• Strict \({\varPi^1_1}\)-reflection in bounded arithmetic
• scientific article; zbMATH DE number 5778051 (Why is no real title available?)
• scientific article; zbMATH DE number 1163985 (Why is no real title available?)
• Characterizations of interpretability in bounded arithmetic
• Bounded finite set theory
• Varieties of truth definitions
• A theory of implicit commitment

This page was built for publication: On interpretations of bounded arithmetic and bounded set theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1038653)