No Cover Image

Journal article 1183 views

Preservation theorems and restricted consistency statements in bounded arithmetic

Arnold Beckmann Orcid Logo

Annals of Pure and Applied Logic, Volume: 126, Issue: 1-3, Pages: 255 - 280

Swansea University Author: Arnold Beckmann Orcid Logo

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

Check full text

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...

Full description

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
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>MACS</deptcode><abstract>In this article we prove preservation theorems for theories of bounded arithmetic. The following one is well-known: The &#x2200;&#x3A0; b 1 - separation of bounded arithmetic theories S i 2 from T j 2 (1 &#x2264; i &#x2264; j) is equivalent to the existence of a model of S i 2 which does not have a &#x394; b 0 - elementary extension to a model of T j 2 .Let &#x3A9;1nst denote that there is a nonstandard element c such that the function n&#x2192;2log(n)c is a total function.Let BL&#x3A3; b 1 be the bounded collection schema &#x2200;x&#x2264;|t| &#x2203;y &#x3C6;(x,y) &#x2192; &#x2203;z &#x2200;x&#x2264;|t| &#x2203;y&#x2264;z &#x3C6;(x,y) for &#x3C6; &#x2208; &#x3A3; b 1 .Main Theorem. The &#x2200;&#x3A0; b 1 - separation of S i 2 from T j 2 (1 &#x2264; i &#x2264; j) is equivalent to the existence of a model of S i 2 + &#x3A9;1nst which is 1b - closed w.r.t. T j 2 , a countable model of S i 2 + BL&#x3A3; b 1 without weak end extensions to models of T j 2 .These results still hold when the theories are extended by finitely many &#x2203; &#x2200; (&#x3A3; b i &#x222A; &#x3A0; 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>Mathematics and Computer Science School</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>MACS</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 MACS 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 Mathematics and Computer Science School COLLEGE CODE MACS 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-31T12:28:29Z
_version_ 1821408503921639424
score 11.139166

Similar Items