An Escape From Vardanyan’s Theorem

Journal of Symbolic Logic 88 (4):1613-1638 (2023)
  Copy   BIBTEX

Abstract

Vardanyan’s Theorems [36, 37] state that $\mathsf {QPL}(\mathsf {PA})$ —the quantified provability logic of Peano Arithmetic—is $\Pi ^0_2$ complete, and in particular that this already holds when the language is restricted to a single unary predicate. Moreover, Visser and de Jonge [38] generalized this result to conclude that it is impossible to computably axiomatize the quantified provability logic of a wide class of theories. However, the proof of this fact cannot be performed in a strictly positive signature. The system $\mathsf {QRC_1}$ was previously introduced by the authors [1] as a candidate first-order provability logic. Here we generalize the previously available Kripke soundness and completeness proofs, obtaining constant domain completeness. Then we show that $\mathsf {QRC_1}$ is indeed complete with respect to arithmetical semantics. This is achieved via a Solovay-type construction applied to constant domain Kripke models. As corollaries, we see that $\mathsf {QRC_1}$ is the strictly positive fragment of $\mathsf {QGL}$ and a fragment of $\mathsf {QPL}(\mathsf {PA})$.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,386

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

No Escape from Vardanyan's theorem.Albert Visser & Maartje de Jonge - 2006 - Archive for Mathematical Logic 45 (5):539-554.
A Note on Introducing a 'Zero-Line' of Welfare as an Escape-Route from Arrow's Theorem.Christian List - 2001 - Pacific Economic Review (Special Section in Honour of Amartya Sen) 6 (2):223-238.
Minds, Machines, and Gödel: A Retrospect.J. R. Lucas - 1996 - In Raffaela Giovagnoli (ed.), Etica E Politica. Clarendon Press. pp. 1.
The translation theorem.Peter Cholak - 1994 - Archive for Mathematical Logic 33 (2):87-108.
Compactness Theorem.A. C. Paseau & Robert Leek - 2022 - Internet Encyclopedia of Philosophy.
Query the Triple Loophole of the Proof of Gödel Incompleteness Theorem.FangWen Yuan - 2008 - Proceedings of the Xxii World Congress of Philosophy 41:77-94.
Taking the Coase Theorem Seriously.Richard D. Mckelvey - 1999 - Economics and Philosophy 15 (2):235-247.

Analytics

Added to PP
2022-05-15

Downloads
16 (#886,588)

6 months
10 (#255,509)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Joost Joosten
Universitat de Barcelona

Citations of this work

Provability logic.Rineke Verbrugge - 2008 - Stanford Encyclopedia of Philosophy.

Add more citations