Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-16T22:27:49.842Z Has data issue: false hasContentIssue false

On the No-Counterexample Interpretation

Published online by Cambridge University Press:  12 March 2014

Ulrich Kohlenbach*
Affiliation:
BRICS, (Basic Research in Computer Science, Centre of the Danish National Research Foundation), Department of Computer Science, University of Aarhus, NY Munkegade, BLDG. 540, DK.-8000 Aarhus C, Denmark, E-mail: kohlenb@brics.dk

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 of order type < ε0 which realize the Herbrand normal form AH 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 nocounterexample 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].

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1999

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