Journal article 1340 views
An unexpected separation result in Linearly Bounded Arithmetic
Arnold Beckmann 
,
Jan Johannsen
,
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.
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...
| 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: |
Faculty of Science and Engineering |
| Issue: |
2 |
| Start Page: |
191 |
| End Page: |
200 |