On n-quantifier induction
On n-quantifier induction
复制标题
关于 n 量词归纳
DOI：
10.2307/2272731
复制
发表时间：
1972
影响因子：
0.6
通讯作者：
C. Parsons
中科院分区：
文献类型：
--
作者：
C. Parsons
本文用量词的形式讨论了基于归纳法限制的数论子系统，证明了“n-量词归纳法”的所有自然公式都可归结为两种(对于n≠0)不等价范式之一：归纳法公理限制于(或等价地)公式和归纳法规则限制于公式。设Z0是经典的初等数论，每个Kalmar初等函数有一个符号和定义方程，归纳规则仅限于无限定符的公式。假设Ian是IA对具有≤n个嵌套量词的Z0公式的限制，Ian‘是对具有≤n个嵌套量词的公式的限制，而不考虑有界量词、对公式的限制、对公式的限制。Irn，irn‘，，都是相似的。然后，我们证明了，对于每个n，，，Ian，和Ian‘，都是模Z0等价的。相应的陈述不适用于IR。我们证明了，如果n≠0可约为；显然IRn可约为。另一方面，Irn‘显然等价于Ian’[10，引理2]。
In this paper we discuss subsystems of number theory based on restrictions on induction in terms of quantifiers, and we show that all the natural formulations of ‘n-quantifier induction’ are reducible to one of two (for n ≠ 0) nonequivalent normal forms: the axiom of induction restricted to (or, equivalently, ) formulae and the rule of induction restricted to formulae. Let Z0 be classical elementary number theory with a symbol and defining equations for each Kalmar elementary function, and the rule of induction restricted to quantifier-free formulae. Given the schema let IAn be the restriction of IA to formulae of Z0 with ≤n nested quantifiers, IAn′ to formulae with ≤n nested quantifiers, disregarding bounded quantifiers, the restriction to formulae, the restriction to , formulae. IRn, IRn′, , are analogous. Then, we show that, for every n, , , IAn, and IAn′, are all equivalent modulo Z0. The corresponding statement does not hold for IR. We show that, if n ≠ 0, is reducible to ; evidently IRn is reducible to . On the other hand, IRn′ is obviously equivalent to IAn′ [10, Lemma 2].