Journal article 1041 views
Preservation theorems and restricted consistency statements in bounded arithmetic
Annals of Pure and Applied Logic, Volume: 126, Issue: 1-3, Pages: 255 - 280
Swansea University Author:
Arnold Beckmann
Full text not available from this repository: check for access using links below.
DOI (Published version): 10.1016/j.apal.2003.11.003
Abstract
In this article we prove preservation theorems for theories of bounded arithmetic. The following one is well-known: The ∀Π b 1 - separation of bounded arithmetic theories S i 2 from T j 2 (1 ≤ i ≤ j) is equivalent to the existence of a model of S i 2 which does not have a Δ b 0 - elementary extensio...
| Published in: | Annals of Pure and Applied Logic |
|---|---|
| ISSN: | 0168-0072 |
| Published: |
2004
|
| Online Access: |
Check full text
|
| URI: | https://cronfa.swan.ac.uk/Record/cronfa13722 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Abstract: |
In this article we prove preservation theorems for theories of bounded arithmetic. The following one is well-known: The ∀Π b 1 - separation of bounded arithmetic theories S i 2 from T j 2 (1 ≤ i ≤ j) is equivalent to the existence of a model of S i 2 which does not have a Δ b 0 - elementary extension to a model of T j 2 .Let Ω1nst denote that there is a nonstandard element c such that the function n→2log(n)c is a total function.Let BLΣ b 1 be the bounded collection schema ∀x≤|t| ∃y φ(x,y) → ∃z ∀x≤|t| ∃y≤z φ(x,y) for φ ∈ Σ b 1 .Main Theorem. The ∀Π b 1 - separation of S i 2 from T j 2 (1 ≤ i ≤ j) is equivalent to the existence of a model of S i 2 + Ω1nst which is 1b - closed w.r.t. T j 2 , a countable model of S i 2 + BLΣ b 1 without weak end extensions to models of T j 2 .These results still hold when the theories are extended by finitely many ∃ ∀ (Σ b i ∪ Π b i ) - sentences. |
|---|---|
| College: |
Faculty of Science and Engineering |
| Issue: |
1-3 |
| Start Page: |
255 |
| End Page: |
280 |