No Cover Image

Journal article 548 views

An unexpected separation result in Linearly Bounded Arithmetic / Arnold Beckmann; Jan Johannsen

MLQ, Volume: 51, Issue: 2, Pages: 191 - 200

Swansea University Author: Arnold, Beckmann

Full text not available from this repository: check for access using links below.

Check full text

DOI (Published version): 10.1002/malq.200410019

Abstract

The theories S i 1 (α) and T i 1 (α) are the analogues of Buss' relativized bounded arithmetic theories in the language where every term is bounded by a polynomial, and thus all definable functions grow linearly in length. For every i , a Σ b i+1 (α) - formula TOPi(α) , which expresses a form o...

Full description

Published in: MLQ
ISSN: 0942-5616 1521-3870
Published: 2005
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa13721
Tags: Add Tag
No Tags, Be the first to tag this record!
Abstract: The theories S i 1 (α) and T i 1 (α) are the analogues of Buss' relativized bounded arithmetic theories in the language where every term is bounded by a polynomial, and thus all definable functions grow linearly in length. For every i , a Σ b i+1 (α) - formula TOPi(α) , which expresses a form of the total ordering principle, is exhibited that is provable in S i+1 1 (α) , but unprovable in T i 1 (α) . This is in contrast with the classical situation, where S i+1 2 is conservative over T i 2 w.r.t. Σ b i+1 -sentences. The independence results are proved by translations into propositional logic, and using lower bounds for corresponding propositional proof systems.
College: College of Science
Issue: 2
Start Page: 191
End Page: 200