Journal article 1041 views
Preservation theorems and restricted consistency statements in bounded arithmetic
Arnold Beckmann 
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.014291 |