Journal article 1089 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!
|
first_indexed |
2013-07-23T12:10:46Z |
---|---|
last_indexed |
2018-02-09T04:44:36Z |
id |
cronfa13722 |
recordtype |
SURis |
fullrecord |
<?xml version="1.0"?><rfc1807><datestamp>2013-10-17T11:50:43.4976257</datestamp><bib-version>v2</bib-version><id>13722</id><entry>2012-12-17</entry><title>Preservation theorems and restricted consistency statements in bounded arithmetic</title><swanseaauthors><author><sid>1439ebd690110a50a797b7ec78cca600</sid><ORCID>0000-0001-7958-5790</ORCID><firstname>Arnold</firstname><surname>Beckmann</surname><name>Arnold Beckmann</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2012-12-17</date><deptcode>SCS</deptcode><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.</abstract><type>Journal Article</type><journal>Annals of Pure and Applied Logic</journal><volume>126</volume><journalNumber>1-3</journalNumber><paginationStart>255</paginationStart><paginationEnd>280</paginationEnd><publisher/><placeOfPublication/><issnPrint>0168-0072</issnPrint><issnElectronic/><keywords/><publishedDay>31</publishedDay><publishedMonth>12</publishedMonth><publishedYear>2004</publishedYear><publishedDate>2004-12-31</publishedDate><doi>10.1016/j.apal.2003.11.003</doi><url/><notes/><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><apcterm/><lastEdited>2013-10-17T11:50:43.4976257</lastEdited><Created>2012-12-17T10:28:52.3612725</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>Arnold</firstname><surname>Beckmann</surname><orcid>0000-0001-7958-5790</orcid><order>1</order></author></authors><documents/><OutputDurs/></rfc1807> |
spelling |
2013-10-17T11:50:43.4976257 v2 13722 2012-12-17 Preservation theorems and restricted consistency statements in bounded arithmetic 1439ebd690110a50a797b7ec78cca600 0000-0001-7958-5790 Arnold Beckmann Arnold Beckmann true false 2012-12-17 SCS 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. Journal Article Annals of Pure and Applied Logic 126 1-3 255 280 0168-0072 31 12 2004 2004-12-31 10.1016/j.apal.2003.11.003 COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University 2013-10-17T11:50:43.4976257 2012-12-17T10:28:52.3612725 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Arnold Beckmann 0000-0001-7958-5790 1 |
title |
Preservation theorems and restricted consistency statements in bounded arithmetic |
spellingShingle |
Preservation theorems and restricted consistency statements in bounded arithmetic Arnold Beckmann |
title_short |
Preservation theorems and restricted consistency statements in bounded arithmetic |
title_full |
Preservation theorems and restricted consistency statements in bounded arithmetic |
title_fullStr |
Preservation theorems and restricted consistency statements in bounded arithmetic |
title_full_unstemmed |
Preservation theorems and restricted consistency statements in bounded arithmetic |
title_sort |
Preservation theorems and restricted consistency statements in bounded arithmetic |
author_id_str_mv |
1439ebd690110a50a797b7ec78cca600 |
author_id_fullname_str_mv |
1439ebd690110a50a797b7ec78cca600_***_Arnold Beckmann |
author |
Arnold Beckmann |
author2 |
Arnold Beckmann |
format |
Journal article |
container_title |
Annals of Pure and Applied Logic |
container_volume |
126 |
container_issue |
1-3 |
container_start_page |
255 |
publishDate |
2004 |
institution |
Swansea University |
issn |
0168-0072 |
doi_str_mv |
10.1016/j.apal.2003.11.003 |
college_str |
Faculty of Science and Engineering |
hierarchytype |
|
hierarchy_top_id |
facultyofscienceandengineering |
hierarchy_top_title |
Faculty of Science and Engineering |
hierarchy_parent_id |
facultyofscienceandengineering |
hierarchy_parent_title |
Faculty of Science and Engineering |
department_str |
School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science |
document_store_str |
0 |
active_str |
0 |
description |
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. |
published_date |
2004-12-31T03:15:41Z |
_version_ |
1763750278665863168 |
score |
11.021648 |