Hostname: page-component-7b7567c8c-p67k6 Total loading time: 0 Render date: 2026-11-19T19:09:05.010Z Has data issue: false hasContentIssue false

Fragments of Heyting arithmetic

Published online by Cambridge University Press:  12 March 2014

Wolfgang Burr*
Affiliation:
Institut für Mathematische Logik und Grundlagenforschung, der Westfälischen Wilhelms-Universität Münster, Einsteinstr. 62, D-48149 Münster, Germany E-mail: Wolfgang.Burr@math.uni-muenster.de

Abstract

We define classes Φn of formulae of first-order arithmetic with the following properties:

(i) Every φ ϵ Φn is classically equivalent to a Πn-formula (n ≠ 1, Φ1 := Σ1).

(ii)

(iii) IΠn and iΦn (i.e., Heyting arithmetic with induction schema restricted to Φn-formulae) prove the same Π2-formulae.

We further generalize a result by Visser and Wehmeier. namely that prenex induction within intuitionistic arithmetic is rather weak: After closing Φn both under existential and universal quantification (we call these classes Θn) the corresponding theories iΘn still prove the same Π2-formulae. In a second part we consider iΔ0 plus collection-principles. We show that both the provably recursive functions and the provably total functions of are polynomially bounded. Furthermore we show that the contrapositive of the collection-schema gives rise to instances of the law of excluded middle and hence .

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2000

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable