Preservation theorems and restricted consistency statements in bounded arithmetic

@article{citeulike:131999, abstract = {We define and study a new restricted consistency notion RCon*(T2j) for bounded arithmetic theories T2j. It is the strongest [forall][Pi]1b-statement over S21 provable in T2j, similar to Con(Gi) in Krajicek and Pudlak, (Z. Math. Logik Grundl. Math. 36 (1990) 29) or RCon(Ti1) in Krajicek and Takeuti (Ann. Math. Artificial Intelligence 6 (1992) 107). The advantage of our notion over the others is that RCon*(T2j) can directly be used to construct models of T2j. We apply this by proving preservation theorems for theories of bounded arithmetic of the following well-known kind: The [forall][Pi]1b-separation of bounded arithmetic theories S2i from T2j (1[les]i[les]j) is equivalent to the existence of a model of S2i which does not have a [Delta]0b-elementary extension to a model of T2j.More specific, let M [vDash] [Omega]1nst denote that there is a nonstandard element c in M such that the function n |-> 2log(n)c is total in M. Let BL[Sigma]1b be the bounded collection schema for [Sigma]1b-formulas. We obtain the following preservation results: the [forall][Pi]1b-separation of S2i from T2j (1[les]i[les]j) is equivalent to the existence of 1. a model of S2i+[Omega]1nst which is 1b-closed w.r.t. T2j,2. a countable model of S2i+BL[Sigma]1b without weak end extensions to models of T2j.}, author = {Beckmann, Arnold }, citeulike-article-id = {131999}, doi = {10.1016/j.apal.2003.11.003}, journal = {Annals of Pure and Applied Logic}, keywords = {bounded\_arithmetic}, month = {April}, number = {1-3}, pages = {255--280}, posted-at = {2005-03-18 11:21:11}, priority = {2}, title = {Preservation theorems and restricted consistency statements in bounded arithmetic}, url = {http://dx.doi.org/10.1016/j.apal.2003.11.003}, volume = {126}, year = {2004} }

TY - JOUR ID - citeulike:131999 L3 - citeulike-article-id:131999 TI - Preservation theorems and restricted consistency statements in bounded arithmetic JF - Annals of Pure and Applied Logic VL - 126 IS - 1-3 SP - 255 EP - 280 N2 - We define and study a new restricted consistency notion RCon*(T2j) for bounded arithmetic theories T2j. It is the strongest [forall][Pi]1b-statement over S21 provable in T2j, similar to Con(Gi) in Krajicek and Pudlak, (Z. Math. Logik Grundl. Math. 36 (1990) 29) or RCon(Ti1) in Krajicek and Takeuti (Ann. Math. Artificial Intelligence 6 (1992) 107). The advantage of our notion over the others is that RCon*(T2j) can directly be used to construct models of T2j. We apply this by proving preservation theorems for theories of bounded arithmetic of the following well-known kind: The [forall][Pi]1b-separation of bounded arithmetic theories S2i from T2j (1[les]i[les]j) is equivalent to the existence of a model of S2i which does not have a [Delta]0b-elementary extension to a model of T2j.More specific, let M [vDash] [Omega]1nst denote that there is a nonstandard element c in M such that the function n |-> 2log(n)c is total in M. Let BL[Sigma]1b be the bounded collection schema for [Sigma]1b-formulas. We obtain the following preservation results: the [forall][Pi]1b-separation of S2i from T2j (1[les]i[les]j) is equivalent to the existence of 1. a model of S2i+[Omega]1nst which is 1b-closed w.r.t. T2j,2. a countable model of S2i+BL[Sigma]1b without weak end extensions to models of T2j. KW - bounded_arithmetic AU - Beckmann, Arnold PY - 2004/04// UR - http://dx.doi.org/10.1016/j.apal.2003.11.003 ER -