Yoriyuki Yamagata - Bounded Arithmetic in Free Logic

lmcs:863 - Logical Methods in Computer Science, August 10, 2012, Volume 8, Issue 3 - https://doi.org/10.2168/LMCS-8(3:7)2012
Bounded Arithmetic in Free LogicArticle

Authors: Yoriyuki Yamagata

    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ödel 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.


    Volume: Volume 8, Issue 3
    Published on: August 10, 2012
    Imported on: March 5, 2012
    Keywords: Mathematics - Logic,Computer Science - Logic in Computer Science,cs.LO

    Consultation statistics

    This page has been seen 969 times.
    This article's PDF has been downloaded 238 times.