Some Results on LΔ_{n+1}^{−}

Alejandro Fernández Margarit & F. Félix Lara Martín

Research partially supported by the Ministerio de Educación y Cultura (Spain) grant PB96–1345)

This work is conected with the Parameter Free Paris–Friedman’s Conjecture (see [1] Problem 34, and [2] page 398):

LΔ_{n+1}^{−} ⟺ IΔ_{n+1}^{−}

The relationships among the schemas of induction, minimalization and collection for formulas in the classes of the Arithmetic Hierarchy (Σ_{n}, Π_{n}) has been studied by J. Paris and L. A. Kirby (see [2] and [4]). The parameter free versions of these schemas have been studied by R. Kaye, J. Paris and C. Dimitracopoulos (see [3] and [5]).

Here we study the quantifier complexity of LΔ_{n+1}^{−} and some relations between this theory and the class of the Π_{n+1} true sentences, Th_{Π_{n+1}}(N). In particular, we prove that

(a) LΔ_{n+1}^{−} is Σ_{n+2}–axiomatized but is not Π_{n+2}–axiomatizable.
(b) LΔ_{n+1}^{−} is not finitely axiomatizable.
(c) IΣ_{n} is not an extension of LΔ_{n+1}^{−}. So, LΔ_{1}^{−} is a proper extension of IΔ_{0}.

(d) Let T be a theory such that T + exp is consistent. If Th_{Π_{2}}(T) is an extension of LΔ_{1}^{−} then Th_{Π_{1}}(T + exp) = Th_{Π_{1}}(N).

(e) For n ≥ 1, Th_{Π_{n+1}}(N) is (up to equivalence) the unique theory Π_{n+1}–axiomatized that is an extension of LΔ_{n+1}^{−}.

Part (e) is proved in [5] for IΠ_{n+1}^{−}. Since, IΠ_{n+1}^{−} is a proper extension of LΔ_{n+1}^{−}, the property given in (e) improves that result. Properties (a)-(c) and weak versions of (d) and (e) are also true for IΔ_{n+1}^{−}.

References

[1] Clote, P.; Krajícek, J. Open Problems. Arithmetic, Proof Theory and Computational Complexity, pages 1–19. Clarendon Press, Oxford, 1993.

[2] Hájek, P.; Pudlák, P. Metamathematics of First Order Arithmetic. Perspectives in Mathematical Logic, Springer Verlag, Berlin, 1993.

[3] Kaye, R. Diophantine and Parameter-free Induction. Ph.D. Thesis. University of Manchester, 1987.

[4] Kaye, R. Models of Peano Arithmetic. Clarendon Press, Oxford 1991.

[5] Kaye, R.; Paris, J.; Dimitracopoulos, C. On parameter free induction schemas. The Journal of Symbolic Logic. Vol. 43 (1988) 1082-1097.

(Research partially supported by the Ministerio de Educación y Cultura (Spain) grant PB96–1345)

Address: Departamento de Ciencias de la Computación e Inteligencia Artificial, Facultad de Matemáticas. Universidad de Sevilla, C/ Tarfia s/n, Sevilla, 41012, Spain

E-mail: fflara@cica.es