Abstract views of incompleteness Duccio Pianigiani University of Siena, Italy This is a section of Lectures in Proof Theory and Complexity(DOI: 10.36253/979-12-215-0778-2) by Duccio Pianigiani Firenze University Press, USiena Press Florence 2025 https://doi.org/10.36253/979-12-215-0778-2.05

Available for academic research purposes

Open Access

Copyright Author(s)

Content licence CC BY-SA 4.0

Metadata licence CC0 1.0

This is original content, published for academic research purposes

 Digital edition XML powered by Booksflow

The aim of this section is to account for Gödel’s original intuition with the means of modern computability theory, showing the different complexity of the theorems of a theory of formal arithmetic with certain properties, and of the set of true propositions of the language of this theory. For this purpose, we refine the notion of computably enumerable set through the concept of creative set, introduced by Emil Post.

 Recutsive functions recursive enumerability crative sets productive sets incompleteness

It is available online at https://doi.org/10.36253/979-12-215-0778-2.05

References Amidei, Jacopo and Pianigiani, Duccio and San Mauro Luca and Simi, Giulia and Sorbi, Andrea. 2016. “Trial and error Mathematics I.” The Review of Symbolic Logic 9(2): 299-324. 10.1017/S1755020315000404 Amidei Jacopo and Pianigiani, Duccio and San Mauro Luca and Sorbi, Andrea. 2016. “Trial and error mathematics II: dialectical sets and quasi-dialectical sets, their degrees, and their distribution within the class of limit sets.” The Review of Symbolic Logic 9(4): 810-835. 0.1017/S1755020316000253 Amidei Jacopo and Andrews, Uri and Pianigiani, Duccio and San Mauro Luca and Sorbi, Andrea. 2019. “Trial and error mathematics III: Dialectical systems and completions of theories.”Journal of Logic and Computation, 29 (1): 157-184 10.1093/logcom/exy033 Bernardi, Claudio. 1981. “On the relation provable equivalence and on partitions in effectively inseparable sets” . Studia Logica 40: 29-37. 10.1007/BF01837553 Boykan Pour-El, Marian. 1968. “Effectively extensible theories” . The Journal of Symbolic Logic 33 (1): 56-68. 10.2307/2270052 Buss, Samuel R. 1998. “First-order proof theory of arithmetic.” In Handbook of Proof Theory, edited by S. Buss, 79-147. Amsterdam: Elsevier. Cheng, Yong. 2023. “There Are No Minimal Effectively Inseparable Theories ” Notre Dame Journal of Formal Logic 64 (4): 425-439. 10.1215/00294527-2023-0017 Cooper, Barry S. 2003. Computability Theory. Boca Raton: Chapman and Hall/ CRC Press 10.1201/9781315275789 Cooper, Barry S. 2004. “The Incomputable Alan Turing” . In Proceedings of the 2004 inter- national conference on Alan Mathison Turing: a celebration of his life and achievements (Turing’04), edited by J. Delve and J. Paris, 1-17. Swindon: BCS Learning and Development Ltd. Copeland, Jack. The Church-Turing Thesis. alanturing.net Copeland, B. Jack and Shagrir, Oron. 2013. “Turing versus Gödel on Computability and the Mind” . In J. B. Copeland, C. Posy, O. Shagrir (editors) Computability: Gödel, Turing, Church, and beyond 1-35. Boston: MIT Press. 10.7551/mitpress/8009.003.0002 Dawson, John. 1997. Logical Dilemmas. The Life and Work of Kurt Gödel. Wellesley: A K Peters. 10.1201/9780429294884 Gödel, Kurt. 1951. “Some basic theorems on the foundations of mathematics and their implications” (Gibbs Lecture). In Gödel’s Collected Works (1986-2005) III, 304-323. Gödel, Kurt. 1931. “Über Formal Unentscheidbare Sätze der Principia Mathematica und Verwandter Systeme I.” Monatshefte für Mathematik und Physik 38: 173-198 (reprinted in Gödel’s Collected Works (1986-2005), Vol. I: 144-195 10.1007/BF01700692 Gold, E. Mark. 1967. “Language identification in the limit” Information and Control 10 (5): 447-474. Grattan-Guinness, Ivor. 1979. “In Memoriam Kurt Gödel: his 1931 correspondence with Zermelo on his incompletability theorem” . Historia Math. 6: 294-304. Grattan-Guinness, Ivor. 1979. “In Memoriam Kurt Gödel: his 1931 correspondence with Zermelo on his incompletability theorem” . Historia Math. 6: 294-304. 10.1016/J.HM.2015.09.002 Grattan-Guinness, Ivor. 2011. “The Reception of Gödel’s 1931 Incompletability Theorems by Mathematicians, and Some Logicians, to the Early 1960s. ” In Kurt Gödel and the Foundations of Mathematics, edited by M. Baaz, 57-74. Cambridge: Cambridge University Press. 10.1017/CBO9780511974236 Hilbert, David and Bernays, Paul. 1934. Grundlagen der Mathematik I. Berlin: Springer. Hilbert, David and Bernays, Paul. 1939. Grundlagen der Mathematik II. Berlin: Springer. Krajewski, Stanislaw. 2004. “Gödel on Tarski.” Annals of Pure and Applied Logic 127: 303- 323. 10.1016/j.apal.2003.11.019. Kelly, Kevin T. 2023. The Logic of Reliable Inquiry. Oxford: Oxford University Press. 10.1093/oso/9780195091953.003.0002 Kugel, Peter. 1986. “Thinking may be more than computing.” Cognition 18: 128-149. Jeřábek, Emil. 2016. “Division by zero” Archive for Mathematical Logic 55: 997-1013. 10.1007/s00153-016-0508-5 Jeroslow, Robert G. 1975. “Experimental logics and ∆ 2 theories.” Journal of Philosophical Logic 4 (3): 253-267 10.1007/BF00261270 Magari, Roberto. 1974. “Su certe teorie non enumerabili.” Annali di Matematica Pura ed Applicata 4, XCVIII: 119-152. 10.1007/BF02792706 Lakatos, Imre. 1976. Proofs and Refutations. Cambridge: Cambridge University Press. 10.1017/CBO 9781139171472 Matiyasevich, Yuri. 1970. "Enumerable sets are Diophantine." Doklady Akademii Nauk SSSR, 191: 79-282. Odifreddi, Piergiorgio. 1989. Classical Recursion Theory I. Amsterdam: North Holland. Osherson, Daniel. N. and Stob, Michael and Weinstein, Scott. 1986. Systems that learn: An introduction to learning theory for cognitive and computer scientists. Boston: MIT Press. Parsons, Charles. 1970. “On a Number Theoretic Choice Schema and its Relation to Induction.” in A. Kino, J. Myhill, R.E. Vesley (editors), Studies in Logic and the Foundations of Mathematics vol. 60. Amsterdam: Elsevier. 10.2307/2272677 Peter, Rozsa. 1957. Rekursive Funktionen. Berlin, Boston: de Gruyter. Post, Emil. 1941. “Absolutely Unsolvable Problems and Relatively Undecidable Propositions: Account of an Anticipation.” In The Undecidable 1965, edited by M. Davis 340-433. New York: Raven Press. Post, Emil. 1944. “Recursively enumerable sets of positive integers and their decision problems”. Bulletin of the American Mathematical Society 50: 284-316. Post, Emil L. 1948. “Degrees of recursive unsolvability: preliminary report.” Bulletin of the American Math. Soc. 54: 641-642. Putnam, Hilary. 1965. “Trial and error predicates and the solution to a problem of Mostowski.” The Journal of Symbolic Logic 30 (1): 49-57. 10.2307/2270581 Robinson, Raphael. 1950, “An Essentially Undecidable Axiom System”, in Proceedings of the International Congress of Mathematics, 1950: 729-730 Rogers, Hartley. 1987. The Theory of Recursive Functions and Effective Computability. Boston: MIT Press. Smullyan, Raymond Merrill. 1961. Theory of Formal Systems. Princeton: Princeton University Press. Soare, Robert I. 1996. “Computability and Recursion.” The Bulletin of Symbolic Logic 2 (3): 284-321. 10.2307/420992 Soare, Robert I. 2009. “Turing oracle machines, online computing, and three displacements in computability theory”. Annals of Pure and Applied Logic 160 (3): 368-399. Turing, Alan M. 1936. “On computable numbers, with application to the Entscheidungsprob- lem”, in Proceedings of London Math. Soc. 42: 230-265, 544-546. Turing, Alan M. 1947. “Lecture to the London Mathematical Society on 20 February 1947.” In The Essential Turing, edited by B. J. Copeland, 378-394. Oxford: Oxford U.P. Von Neumann, John. 1951. “The general and logical theory of automata”. In Cerebral mechanisms in behavior; the Hixon Symposium, edited by L. A. Jeffress, 1-41. Hoboken: Wiley. Wang, Hao. 1974. From Mathematics to Philosophy. New York: Routledge and Kegan. Zach, Richard. 1998. “Numbers and functions in Hilbert’s finitism”. Taiwanese Journal for Philosophy and History of Science 10: 33-60. 10.1017/S1755020320000015