 Journal article 758 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:

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

Full description

Published in: Annals of Pure and Applied Logic 0168-0072 2004 https://cronfa.swan.ac.uk/Record/cronfa13722 No Tags, Be the first to tag this record!
first_indexed 2013-07-23T12:10:46Z 2018-02-09T04:44:36Z cronfa13722 SURis 2013-10-17T11:50:43.4976257v2137222012-12-17Preservation theorems and restricted consistency statements in bounded arithmetic1439ebd690110a50a797b7ec78cca6000000-0001-7958-5790ArnoldBeckmannArnold Beckmanntruefalse2012-12-17SCSIn 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 ArticleAnnals of Pure and Applied Logic1261-32552800168-0072311220042004-12-3110.1016/j.apal.2003.11.003COLLEGE NANMEComputer ScienceCOLLEGE CODESCSSwansea University2013-10-17T11:50:43.49762572012-12-17T10:28:52.3612725Faculty of Science and EngineeringSchool of Mathematics and Computer Science - Computer ScienceArnoldBeckmann0000-0001-7958-57901 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 Preservation theorems and restricted consistency statements in bounded arithmetic Preservation theorems and restricted consistency statements in bounded arithmetic Arnold Beckmann Preservation theorems and restricted consistency statements in bounded arithmetic Preservation theorems and restricted consistency statements in bounded arithmetic Preservation theorems and restricted consistency statements in bounded arithmetic Preservation theorems and restricted consistency statements in bounded arithmetic Preservation theorems and restricted consistency statements in bounded arithmetic 1439ebd690110a50a797b7ec78cca600 1439ebd690110a50a797b7ec78cca600_***_Arnold Beckmann Arnold Beckmann Arnold Beckmann Journal article Annals of Pure and Applied Logic 126 1-3 255 2004 Swansea University 0168-0072 10.1016/j.apal.2003.11.003 Faculty of Science and Engineering facultyofscienceandengineering Faculty of Science and Engineering facultyofscienceandengineering Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science 0 0 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. 2004-12-31T03:17:15Z 1756053410324414464 10.927301