Online research in philosophy

A realizability notion that employs only Kalmar elementary functions is defined, and, relative to it, the soundness of EA-(10-IR), a fragment of Heyting Arithmetic (HA) with names and axioms for all elementary functions and induction rule restricted to 10 formulae, is proved. As a corollary, it is proved that the provably recursive functions of EA-(10-IR) are precisely the elementary functions. Elementary realizability is proposed as a model of strict arithmetic constructivism, which allows only those constructive procedures for which the amount (...) of computational resources required can be bounded in advance. (shrink)

A new method of "minimal" realizability is proposed and applied to show that the definable functions of Heyting arithmetic (HA)--functions f such that HA $\vdash \forall x\exists!yA(x, y)\Rightarrow$ for all m, A(m, f(m)) is true, where A(x, y) may be an arbitrary formula of L(HA) with only x, y free--are precisely the provably recursive functions of the classical Peano arithmetic (PA), i.e., the $ -recursive functions. It is proved that, for prenex sentences provable in HA, Skolem functions may always be (...) chosen to be $ -recursive. The method is extended to intuitionistic finite-type arithmetic, HA ω 0 , and elementary analysis. Generalized forms of Kreisel's characterization of the provably recursive functions of PA and of the no-counterexample-interpretation for PA are consequently derived. (shrink)

A realizability notion that employs only primitive recursive functions is defined, and, relative to it, the soundness of the fragment of Heyting Arithmetic (HA) in which induction is restricted to Σ 0 1 formulae is proved. A dual concept of falsifiability is proposed and an analogous soundness result is established for a further restricted fragment of HA.

It is well known that the following features hold of AR + T under the strong Kleene scheme, regardless of the way the language is Gödel numbered: 1. There exist sentences that are neither paradoxical nor grounded. 2. There are 2ℵ0 fixed points. 3. In the minimal fixed point the weakly definable sets (i.e., sets definable as {n∣ A(n) is true in the minimal fixed point where A(x) is a formula of AR + T) are precisely the Π1 1 sets. (...) 4. In the minimal fixed point the totally defined sets (sets weakly defined by formulae all of whose instances are true or false) are precisely the ▵1 1 sets. 5. The closure ordinal for Kripke's construction of the minimal fixed point is ωCK 1. In contrast, we show that under the weak Kleene scheme, depending on the way the Gödel numbering is chosen: 1. There may or may not exist nonparadoxical, ungrounded sentences. 2. The number of fixed points may be any positive finite number, ℵ0, or 2ℵ0 . 3. In the minimal fixed point, the sets that are weakly definable may range from a subclass of the sets 1-1 reducible to the truth set of AR to the Π1 1 sets, including intermediate cases. 4. Similarly, the totally definable sets in the minimal fixed point range from precisely the arithmetical sets up to precisely the ▵1 1 sets. 5. The closure ordinal for the construction of the minimal fixed point may be ω, ωCK 1, or any successor limit ordinal in between. In addition we suggest how one may supplement AR + T with a function symbol interpreted by a certain primitive recursive function so that, irrespective of the choice of the Godel numbering, the resulting language based on the weak Kleene scheme has the five features noted above for the strong Kleene language. (shrink)