A Quantified Logic of Evidence

AbstractA propositional logic of explicit proofs, LP, was introduced in [S. Artemov, Explicit provability and constructive semantics, The Bulletin for Symbolic Logic 7 (1) (2001) 1–36. http://www.cs.gc.cuny.edu/~sartemov/publications/BSL.ps], completing a project begun long ago by Gödel, [K. Gödel. Vortrag bei Zilsel. Translated as Lecture at Zilsel's in [S. Feferman, editor. Kurt Gödel Collected Works. Oxford, 1986–2003. Five volumes] III, 62–113, 1938]. LP can be looked at more generally as a logic of explicit evidence, something currently being investigated. The Realization Theorem for LP says that any theorem of S4 can be converted into a theorem of LP by some replacement of necessitation symbols with explicit proof terms. Thus □ of S4 is a kind of implicit existential quantifier: there exists a proof term (explicit evidence) such that.… Here, quantification over evidence is added to LP, and it is shown that the connection between S4 necessitation and the existential quantifier is direct. The extension of LP with quantifiers is called QLP. A semantics and an axiom system for QLP are given, soundness and completeness are established, and several results are proved relating QLP to LP and to S4