Some Functional Schemes in Arithmetic

M.C. Graciani, M.J. Pérez Jiménez & A. Romero Jiménez

Peano Arithmetic, PA, can be described through the classical axioms schemes of induction (I), minimization (L), collection (B) and strong collection (S) for the hierarchy of Σ_{n} and Π_{n}-formulas. The relationships between the schemes above for that hierarchy were established by J. Paris and L. Kirby (1977) [1], for induction, minimization and collection. And by P. Clote (1983) for strong collection.

In this work, we introduce some new functional schemes about the existence of a maximum element as follows: Given a formula Θ(x, y) of the language of Arithmetic, the axiom F^{∗}_{Θ} states that if Θ defines a function with nonempty and bounded domain, then its range has a maximum element. On the other hand, the axiom FT^{∗}_{Θ} states the same, but with Θ defining a total function. If Γ ⊆ Form(L), then we can consider the theories F^{∗}Γ and FT^{∗}Γ.

The main result of this work is the following:

Theorem 1 For every n ∈ ω:

SΣ_{n+1} ⟺ F^{∗}Σ_{n+1} ⟺ F^{∗}Π_{n} ⟺ SΠ_{n}
BΣ_{n+1} ⟺ FT^{∗}Σ_{n+1} ⟺ FT^{∗}Π_{n} ⟺ BΠ_{n}

Finally, we state the equivalence between the scheme FT^{∗} and the scheme of minimization for Δ_{n+1}- formulas, what allows us for a new “functional” formulation of the Friedmann-Paris conjecture, in relation to the equivalence between the axioms schemes of induction and minimization for Δ_{n+1}-formulas.

[1] Paris, J., Kirby, L., Σ_{n}-collection schemas in Arithmetic, Logic Colloquium ’77, (1978), 199-209

[2] Pérez Jiménez, M.J., Esquemas del máximo en la Aritmética, Ph.D, Thesis, (1992), Universidad de Sevilla

Partially supported by research project DGES 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: cgdiaz, marper, alvaro @cica.es