Skip to main content
SpringerLink
Log in

Rosser-Type Undecidable Sentences Based on Yablo’s Paradox

  • Published:
Journal of Philosophical Logic Aims and scope Submit manuscript

Abstract

It is widely considered that Gödel’s and Rosser’s proofs of the incompleteness theorems are related to the Liar Paradox. Yablo’s paradox, a Liar-like paradox without self-reference, can also be used to prove Gödel’s first and second incompleteness theorems. We show that the situation with the formalization of Yablo’s paradox using Rosser’s provability predicate is different from that of Rosser’s proof. Namely, by using the technique of Guaspari and Solovay, we prove that the undecidability of each instance of Rosser-type formalizations of Yablo’s paradox for each consistent but not Σ1-sound theory is dependent on the choice of a standard proof predicate.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. Recently, Leach-Krouse [13] independently proved the existence of a standard proof predicate such that ∀ x∀y(Y R(x) ↔ Y R(y)) is provable.

  2. This can be done since for any given formula, we can effectively find a Rosser-type Yablo formula of the formula.

  3. Note that the remark by von Bülow [17] on the proof of Lemma 6.3 in [8] does not affect our proof of Lemma 13 because the provability predicate Pr τ (x) is sufficiently strong for carrying out our proof.

  4. Here the notation \(\bar {a}\) is ambiguous since a is formally a variable. In practice, \(\exists y > a \textsf {Th}_{T}^{R}\left (\ulcorner Y^{R}(\dot {y}) \urcorner \right )\) holds, and \(\textsf {Pr}_{\tau }\left (\ulcorner \exists y > \dot {a} \textsf { Th}_{T}^{R}\left (\ulcorner Y^{R}(\dot {y}) \urcorner \right ) \urcorner \right )\) is derived by the formalized Σ1-completeness.

References

  1. Boolos, G. (1989). A new proof of the Gödel incompleteness theorem. Notices of the American Mathematical Society, 36, 388–390.

    Google Scholar 

  2. Boolos, G. (1993). The logic of provability. Cambridge: Cambridge University Press.

  3. Cantini, A. (2009). Paradoxes, self-reference and truth in the 20th century. In D.M. Gabbay, J. Woods (Eds.), Handbook of the history of logic (vol. 5, pp. 875–1013). Amsterdam: Elsevier/North-Holland.

  4. Chaitin, G.J. (1974). Information-theoretic limitations of formal systems. Journal of the Association for Computing Machinery, 21, 403–424.

    Article  Google Scholar 

  5. Cieśliński, C., & Urbaniak, R. (2013). Gödelizing the Yablo sequence. Journal of Philosophical Logic, 42(5), 679–695.

    Article  Google Scholar 

  6. Feferman, S. (1960). Arithmetization of metamathematics in a general setting. Fundamenta Mathematicae, 49, 35–92.

    Google Scholar 

  7. Gödel, K. (1931). Über formal unentscheidbare sätze der Principia Mathematica und verwandter systeme I (in German). Monatshefte für Mathematik und Physik, 38(1), 173–198, English translation in Kurt Gödel, Collected Works (vol. 1, pp. 145–195).

  8. Guaspari, D., & Solovay, R.M. (1979). Rosser sentences. Annals of Mathematical Logic, 16(1), 81–99.

    Article  Google Scholar 

  9. Kikuchi, M., & Kurahashi, T. (2011). Three short stories around Gödel’s incompleteness theorems (in Japanese). Journal of the Japan Association for Philosophy of Science, 38(2), 27–32.

    Google Scholar 

  10. Kikuchi, M., Kurahashi, T., Sakai, H. (2012). On proofs of the incompleteness theorems based on Berry’s paradox by Vopěnka, Chaitin, and Boolos. Mathematical Logic Quarterly, 58(4–5), 307–316.

    Article  Google Scholar 

  11. Kritchman, S., & Raz, R. (2010). The surprise examination paradox and the second incompleteness theorem. Notices of the American Mathematical Society, 57(11), 1454–1458.

    Google Scholar 

  12. Kurahashi, T. (2013). Predicate provability logic and incompleteness theorems in formalized arithmetic. PhD thesis, Kobe University.

  13. Leach-Krouse, G. (2013). Yablifying the Rosser sentence. Journal of Philosophical Logic. doi:10.1007/s10992-013-9291-5.

  14. Lindström, P. (1997). Aspects of incompleteness. In Lecture Notes in Logic (vol. 10). Berlin: Springer-Verlag.

  15. Priest, G. (1997). Yablo’s paradox. Analysis, 57(4), 236–242.

    Article  Google Scholar 

  16. Rosser, B. (1936). Extensions of some theorems of Gödel and Church. The Journal of Symbolic Logic, 1(3), 87–91.

    Article  Google Scholar 

  17. von Bülow, C. (2008). A remark on equivalent Rosser sentences. Annals of Pure and Applied Logic, 151, 62–67.

    Article  Google Scholar 

  18. Vopěnka, P. (1966). A new proof of the Gödel’s result on non-provability of consistency. Bulletin de l’Académie Polonaise des Sciences. Série des Sciences Mathématiques, Astronomiques et Physiques, 14, 111–116.

    Google Scholar 

  19. Yablo, S. (1993). Paradox without self-reference. Analysis, 53(4), 251–252.

    Article  Google Scholar 

Download references

Acknowledgments

This work was supported by JSPS KAKENHI Grant Number 12J00654. This work is a part of the author’s dissertation [12], and the author is grateful to Makoto Kikuchi who is a supervisor of the dissertation. The author would also like to thank Hidenori Kurokawa for his helpful comments on the earlier version of this paper.

Author information

Authors and Affiliations

  1. Graduate School of System Informatics, Kobe University, 1-1 Rokkodai, Nada, Kobe, Japan

    Taishi Kurahashi

Authors
  1. Taishi Kurahashi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Taishi Kurahashi.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kurahashi, T. Rosser-Type Undecidable Sentences Based on Yablo’s Paradox. J Philos Logic 43, 999–1017 (2014). https://doi.org/10.1007/s10992-013-9309-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10992-013-9309-z

Keywords

Search

Navigation