On the no-counterexample interpretation

Journal of Symbolic Logic 64 (4):1491-1511 (1999)

Abstract
In [15], [16] G. Kreisel introduced the no-counterexample interpretation (n.c.i.) of Peano arithmetic. In particular he proved, using a complicated ε-substitution method (due to W. Ackermann), that for every theorem A (A prenex) of first-order Peano arithmetic PA one can find ordinal recursive functionals Φ A of order type 0 which realize the Herbrand normal form A H of A. Subsequently more perspicuous proofs of this fact via functional interpretation (combined with normalization) and cut-elimination were found. These proofs however do not carry out the no-counterexample interpretation as a local proof interpretation and don't respect the modus ponens on the level of the no-counterexample interpretation of formulas A and A → B. Closely related to this phenomenon is the fact that both proofs do not establish the condition (δ) and--at least not constructively-- (γ) which are part of the definition of an 'interpretation of a formal system' as formulated in [15]. In this paper we determine the complexity of the no-counterexample interpretation of the modus ponens rule for (i) PA-provable sentences, (ii) for arbitrary sentences A, B ∈ L(PA) uniformly in functionals satisfying the no-counterexample interpretation of (prenex normal forms of) A and A → B, and (iii) for arbitrary A, B ∈ L(PA) pointwise in given α( 0 ) -recursive functionals satisfying the no-counterexample interpretation of A and A → B. This yields in particular perspicuous proofs of new uniform versions of the conditions (γ), (δ). Finally we discuss a variant of the concept of an interpretation presented in [17] and show that it is incomparable with the concept studied in [15], [16]. In particular we show that the no-counterexample interpretation of PA n by α( n (ω))-recursive functionals (n ≥ 1) is an interpretation in the sense of [17] but not in the sense of [15] since it violates the condition (δ)
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2307/2586791
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 42,938
Through your library

References found in this work BETA

Reflection Principles and Their Use for Establishing the Complexity of Axiomatic Systems.G. Kreisel & A. Lévy - 1968 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 14 (7-12):97-142.
Reflection Principles and Their Use for Establishing the Complexity of Axiomatic Systems.Georg Kreisel & Azriel Lévy - 1968 - Zeitschrift für Mathematische Logic Und Grundlagen der Mathematik 14 (1):97--142.
A Survey of Proof Theory.G. Kreisel - 1968 - Journal of Symbolic Logic 33 (3):321-388.
Kreisel's 'Unwinding Program'.Solomon Feferman - 1996 - In Piergiorgio Odifreddi (ed.), Kreiseliana. About and Around Georg Kreisel. A K Peters. pp. 247--273.

View all 11 references / Add more references

Citations of this work BETA

On Spector's Bar Recursion.Paulo Oliva & Thomas Powell - 2012 - Mathematical Logic Quarterly 58 (4-5):356-265.

View all 9 citations / Add more citations

Similar books and articles

Analytics

Added to PP index
2009-01-28

Total views
23 ( #369,547 of 2,259,414 )

Recent downloads (6 months)
3 ( #506,095 of 2,259,414 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature