Bounded arithmetic in free logic

DOI10.2168/LMCS-8(3:7)2012MaRDI QIDQ2904624zbMATH OpenFDO

Authors Yoriyuki Yamagata

Publication date 15 August 2012

Published in Logical Methods in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

bounded arithmeticfinitistic Gödel sentencesfree logic

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30)

Abstract: One of the central open questions in bounded arithmetic is whether Buss' hierarchy of theories of bounded arithmetic collapses or not. In this paper, we reformulate Buss' theories using free logic and conjecture that such theories are easier to handle. To show this, we first prove that Buss' theories prove consistencies of induction-free fragments of our theories whose formulae have bounded complexity. Next, we prove that although our theories are based on an apparently weaker logic, we can interpret theories in Buss' hierarchy by our theories using a simple translation. Finally, we investigate finitistic G"odel sentences in our systems in the hope of proving that a theory in a lower level of Buss' hierarchy cannot prove consistency of induction-free fragments of our theories whose formulae have higher complexity.

Review text

The paper is devoted to the open problem whether Buss's hierarchy of theories of bounded arithmetic collapses or not. Buss's theories are reformulated using free logic. It is conjectured that such theories are easier to handle. To show this, it is proved that Buss's theories prove consistencies of induction-free fragments of introduced theories whose formulae have bounded complexity. It is also shown that theories in Buss's hierarchy can be interpreted in the introduced theories using a simple translation. Finally, finitistic Gödel sentences in the developed systems are investigated. The aim here is the hope of proving that a theory in a lower level of Buss's hierarchy cannot prove consistency of induction-free fragments of introduced theories whose formulae have higher complexity.

Recommendations

• Bounded arithmetic and truth definition
• scientific article; zbMATH DE number 218509
• Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\)
• On the Hierarchy of Intuitionistic Bounded Arithmetic
• Gödel sentences of bounded arithmetic

Cited in

(4)

• Bounded arithmetic for NC, ALogTIME, L and NL
• A bounded arithmetic AID for Frege systems
• Gödel sentences of bounded arithmetic
• scientific article; zbMATH DE number 2196511 (Why is no real title available?)

This page was built for publication: Bounded arithmetic in free logic

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