Hostname: page-component-78c5997874-j824f Total loading time: 0 Render date: 2024-11-05T10:47:09.577Z Has data issue: false hasContentIssue false
  • English
  • Français

FINDING THE LIMIT OF INCOMPLETENESS I

Part of: Computability and recursion theory Proof theory and constructive mathematics

Published online by Cambridge University Press:  16 April 2021

YONG CHENG
YONG CHENG*
Affiliation:
SCHOOL OF PHILOSOPHY WUHAN UNIVERSITYWUHAN430072, HUBEIPEOPLE’S REPUBLIC OF CHINA E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper, we examine the limit of applicability of Gödel’s first incompleteness theorem ($\textsf {G1}$ for short). We first define the notion “$\textsf {G1}$ holds for the theory $T$”. This paper is motivated by the following question: can we find a theory with a minimal degree of interpretation for which $\textsf {G1}$ holds. To approach this question, we first examine the following question: is there a theory T such that Robinson’s $\mathbf {R}$ interprets T but T does not interpret $\mathbf {R}$ (i.e., T is weaker than $\mathbf {R}$ w.r.t. interpretation) and $\textsf {G1}$ holds for T? In this paper, we show that there are many such theories based on Jeřábek’s work using some model theory. We prove that for each recursively inseparable pair $\langle A,B\rangle $, we can construct a r.e. theory $U_{\langle A,B\rangle }$ such that $U_{\langle A,B\rangle }$ is weaker than $\mathbf {R}$ w.r.t. interpretation and $\textsf {G1}$ holds for $U_{\langle A,B\rangle }$. As a corollary, we answer a question from Albert Visser. Moreover, we prove that for any Turing degree $\mathbf {0}< \mathbf {d}<\mathbf {0}^{\prime }$, there is a theory T with Turing degree $\mathbf {d}$ such that $\textsf {G1}$ holds for T and T is weaker than $\mathbf {R}$ w.r.t. Turing reducibility. As a corollary, based on Shoenfield’s work using some recursion theory, we show that there is no theory with a minimal degree of Turing reducibility for which $\textsf {G1}$ holds.

Keywords

Gödel’s first incompleteness theoreminterpretationessential undecidabilityRobinson’s R

MSC classification

Primary: 03F40: Gödel numberings and issues of incompleteness
Secondary: 03F30: First-order arithmetic and fragments 03D35: Undecidability and degrees of sets of sentences
Type
Communication
Information
Bulletin of Symbolic Logic , Volume 26 , Issue 3-4 , December 2020 , pp. 268 - 286
Check for updates
Copyright
© The Association for Symbolic Logic 2021

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.)

References

REFERENCES

Beklemishev, L. D., Gödel incompleteness theorems and the limits of their applicability I. Russian Mathematical Surveys, vol. 65 (2010), pp. 61–106.Google Scholar
Boolos, G., The Logic of Provability, Cambridge University Press, Cambridge, 1993.Google Scholar
Buss, S. R., Bounded Arithmetic, Bibliopolis, Napoli, 1986.Google Scholar
Cheng, Y., Incompleteness for Higher-Order Arithmetic: An Example Based on Harrington’s Principle, Springer Series: Springerbrief in Mathematics, Springer, New York, 2019.CrossRefGoogle Scholar
Cheng, Y., Current research on Gödel’s incompleteness theorems, this Journal, to appear. arXiv:2009.04887v2Google Scholar
Cheng, Y., On the depth of Gödel’s incompleteness theorem, this Journal, submitted. arXiv:2008.13142v1Google Scholar
Ebbinghaus, H.-D. and Flum, J., Finite Model Theory, Springer Monographs in Mathematics, Springer, New York, 1999.Google Scholar
Enderton, H. B., A Mathematical Introduction to Logic, second ed., Academic Press, Boston, MA, 2001.Google Scholar
Feferman, S., Degrees of unsolvability associated with classes of formalized theories. Journal of Symbolic Logic, vol. 22 (1957), no. 2, pp. 161–175.CrossRefGoogle Scholar
Ferreira, F. and Ferreira, G., Interpretability in Robinson’s $\textsf{Q}$, this Journal, vol. 19 (2013), no. 3, pp. 289–317.Google Scholar
Ganea, M., Arithmetic on semigroups. Journal of Symbolic Logic, vol. 74 (2009), no. 1, pp. 265–278.CrossRefGoogle Scholar
Gödel, K., Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Monatshefte für Mathematik, vol. 38 (1931), no. 1, pp. 173–198.CrossRefGoogle Scholar
Grzegorczyk, A., Undecidability without arithmetization. Studia Logica, vol. 79 (2005), no. 2, pp. 163–230.CrossRefGoogle Scholar
Grzegorczyk, A. and Zdanowski, K., Undecidability and concatenation, Andrzej Mostowski and Foundational Studies (Ehrenfeucht, A., Marek, V. W., and Srebrny, M., editors), IOS Press, Amsterdam, 2008, pp. 72–91.Google Scholar
Guaspari, D. and Solovay, R. M., Rosser sentences. Annals of Mathematical Logic, vol. 16 (1979), no. 1, pp. 81–99.CrossRefGoogle Scholar
Hájek, P., Mathematical fuzzy logic and natural numbers. Fundamenta Informaticae, vol. 81 (2007), no. 1–3, pp. 155–163.Google Scholar
Hájek, P., Interpretability and fragments of arithmetic, Arithmetic, Proof Theory and Computational Complexity (Clote, P. and Jan Krajícek, J., editors). Oxford Logic Guides 23, Clarendon Press, Oxford, 1993, pp. 185–196.Google Scholar
Hájek, P. and Pudlák, P., Metamathematics of First-Order Arithmetic, Springer-Verlag, Berlin-Heidelberg, 1993.CrossRefGoogle Scholar
Higuchi, K. and Horihata, Y., Weak theories of concatenation and minimal essentially undecidable theories-an encounter of WTC and S2S. Archive for Mathematical Logic, vol. 53 (2014), no. 7–8, pp. 835–853.CrossRefGoogle Scholar
Janiczak, A., Undecidability of some simple formalized theories. Fundamenta Mathematicae, vol. 40 (1953), pp. 131–139.CrossRefGoogle Scholar
Jeřábek, E., Recursive functions and existentially closed structures. Journal of Mathematical Logic, vol. 20 (2020), no. 1, 2050002.CrossRefGoogle Scholar
Jones, J. P. and Shepherdson, J. C., Variants of Robinson’s essentially undecidable theory R. Archive for Mathematical Logic, vol. 23 (1983), pp. 65–77.Google Scholar
Kotlarski, H., The incompleteness theorems after 70 years. Annals of Pure and Applied Logic, vol. 126 (2004), pp. 125–138.CrossRefGoogle Scholar
Lindström, P., Aspects of Incompleteness, Lecture Notes in Logic, Springer-Verlag, Berlin, 1997.CrossRefGoogle Scholar
Murawski, R., Recursive Functions and Metamathematics: Problems of Completeness and Decidability, Gödel’s Theorems, Springer Netherlands, 1999.10.1007/978-94-017-2866-9CrossRefGoogle Scholar
Nelson, E., Predicative Arithmetic, Mathematical Notes, vol. 32, Princeton University Press, Princeton, NJ, 1986.CrossRefGoogle Scholar
Pour-El, M. B. and Kripke, S., Deduction-preserving “recursive isomorphisms” between theories. Fundamenta Mathematicae, vol. 61 (1967), pp. 141–163.CrossRefGoogle Scholar
Sacks, G. E., Degrees of Unsolvability, Annals of Mathematics Studies, vol. 55, Princeton University Press, Princeton, NJ, 1963.Google Scholar
Sacks, G. E., The recursively enumerable degrees are dense. Annals of Mathematics, vol. 80 (1964), no. 2, pp. 300–312.CrossRefGoogle Scholar
Shoenfield, J. R., Degrees of formal systems. The Journal of Symbolic Logic, vol. 23 (1958), no. 4, pp. 389–392.CrossRefGoogle Scholar
Smith, P., An Introduction to Gödel’s Theorems, Cambridge University Press, Cambridge, 2007.Google Scholar
Smoryński, C., The incompleteness theorems, Handbook of Mathematical Logic (Barwise, J., editor), North-Holland, Amsterdam, 1977, pp. 821–865.CrossRefGoogle Scholar
Švejdar, V., An interpretation of Robinson arithmetic in its Grzegorczyk’s weaker variant. Fundamenta Informaticae, vol. 81 (2007), no. 1–3, pp. 347–354.Google Scholar
Švejdar, V., On interpretability in the theory of concatenation. Notre Dame Journal of Formal Logic, vol. 50 (2009), no. 1, pp. 87–95.10.1215/00294527-2008-029CrossRefGoogle Scholar
Tarski, A., Mostowski, A., and Robinson, R. M., Undecidabe Theories, Studies in Logic and the Foundations of Mathematics, North-Holland, Amsterdam, 1953.Google Scholar
Vaught, R. L., On a theorem of Cobham concerning undecidable theories, Proceedings of the 1960 International Congress on Logic, Methodology and Philosophy of Science (Nagel, E., Suppes, P., and Tarski, A., editors), Stanford University Press, Stanford, 1962, pp 14–25.Google Scholar
Visser, A., Growing commas: A study of sequentiality and concatenation. Notre Dame Journal of Formal Logic, vol. 50 (2009), no. 1, pp. 61–85.CrossRefGoogle Scholar
Visser, A., Can we make the second incompleteness theorem coordinate free? Journal of Logic and Computation, vol. 21 (2011), no. 4, pp. 543–560.CrossRefGoogle Scholar
Visser, A., Why the theory R is special?, Foundational Adventures. Essay in Honour of Harvey Friedman, College Publications, London, 2014, pp. 7–23.Google Scholar
Visser, A., On Q. Soft Computing, vol. 21 (2017), pp. 39–56.CrossRefGoogle Scholar
Visser, A., The second incompleteness theorem: Reflections and ruminations, Gödel’s Disjunction: The Scope and Limits of Mathematical Knowledge (Horsten, L. and Welch, P., editors), Oxford University Press, Oxford, 2016.Google Scholar