Sergei Artemov
CUNY Graduate Center
ABSTRACT In 1933 Gödel introduced an axiomatic system, currently known as S4, for a logic of an absolute provability, i.e. not depending on the formalism chosen ([God 33]). The problem of finding a fair provability model for S4 was left open. The famous formal provability predicate which first appeared in the Gödel Incompleteness Theorem does not do this job: the logic of formal provability is not compatible with S4. As was discovered in [Art 95], this defect of the formal provability predicate can be bypassed by replacing hidden quantifiers over proofs by proof polynomials in a certain finite basis. The resulting Logic of Proofs enjoys a natural arithmetical semantics and provides an intended provability model for S4, thus answering a question left open by Gödel in 1933. Proof polynomials give an intended semantics for some other constructions based on the concept of provability, including intuitionistic logic with its Brouwer- Heyting- Kolmogorov interpretation, ?-calculus and modal ?-calculus. In the current paper we demonstrate how the intuitionistic propositional logic Int can be directly realized by proof polynomials. It is shown, that Int is complete with respect to this proof realizability
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1080/11663081.1999.10510968
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 69,089
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Basic Proof Theory.A. S. Troelstra - 2000 - Cambridge University Press.
Logic of Proofs.Sergei Artëmov - 1994 - Annals of Pure and Applied Logic 67 (1-3):29-59.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles


Added to PP index

Total views
15 ( #694,827 of 2,499,017 )

Recent downloads (6 months)
1 ( #419,059 of 2,499,017 )

How can I increase my downloads?


My notes