On some formalized conservation results in arithmetic
On some formalized conservation results in arithmetic
复制标题
关于算术中的一些形式化守恒结果
DOI：
10.1007/bf01792983
复制
发表时间：
1990
影响因子：
0.3
通讯作者：
J. Paris
中科院分区：
文献类型：
--
作者：
P. Clote;P. Hájek;J. Paris
IΣn andBΣn是著名的一阶算法片段，分别有归纳公式和集合公式forΣn；IΣn0 andBΣn0是它们的二级对应。RCA0是众所周知的具有递归理解的二阶算法片段；WKL0 isRCA0加上弱König引理。我们首先通过表明wkl0 +BΣn0是Π11-conservative高于rca0 +BΣn0来加强Harrington的守恒结果。然后，我们在wkl0中发展了一些模型理论，并通过给出一个相对简单的事实证明thatIΣ1 provesBΣn+1是Πn+2保守的overIΣn来说明形式化模型理论的使用。最后，我们给出了一个证明理论证明，证明了theΠn+2守恒结果已经可以证明inIΔ0 +超经验。ThusIΣn+1证明1-Con (BΣn+1) andIΔ0 +superexp证明Con（IΣn）↔Con（BΣn+1）。
IΣn andBΣn are well known fragments of first-order arithmetic with induction and collection forΣn formulas respectively;IΣn0 andBΣn0 are their second-order counterparts. RCA0 is the well known fragment of second-order arithmetic with recursive comprehension;WKL0 isRCA0 plus weak König's lemma. We first strengthen Harrington's conservation result by showing thatWKL0 +BΣn0 is Π11-conservative overRCA0 +BΣn0. Then we develop some model theory inWKL0 and illustrate the use of formalized model theory by giving a relatively simple proof of the fact thatIΣ1 provesBΣn+1 to be Πn+2-conservative overIΣn. Finally, we present a proof-theoretic proof of the stronger fact that theΠn+2 conservation result is provable already inIΔ0 + superexp. ThusIΣn+1 proves 1-Con (BΣn+1) andIΔ0 +superexp proves Con (IΣn)↔Con(BΣn+1).