Contenuto in:
Capitolo

First and second Gödel’s theorems and related results

  • Duccio Pianigiani

We start with the central result from which we derive the first Gödel Theorem. That the 1931 proof of the first theorem is syntactic and constructive. This means that it doesn’t appeal to truth and that we concretely give examples of sentences that are independent (neither provable nor refutable). We show Rosser’s version of the first incompleteness theorem. Then we discuss the limit of incompleteness phenomenon and we illustrate a complete and decidable theory. We introduce nonostandard model and we take another look at incompleteness: Tennenbaum’s theorem.

  • Keywords:
  • first and second incompleteness theorems,
  • Presburger arithmetic,
  • Rosser sentences,
+ Mostra di più

Duccio Pianigiani

University of Siena, Italy - ORCID: 0000-0001-9441-7226

  1. Berarducci, Alessandro. 1990. “The interpretability logic of Peano Arithmetic” . The Journal of Symbolic Logic 55: 1059-1089. DOI: 10.2307/2274474
  2. Berarducci, Alessandro and D’Aquino, Paola. 1995.“∆ 0 -complexity of the relation y = Π i≤nF (i) ” . Annals of Pure and Applied Logic 75 (1-2): 49-56. DOI: 10.1016/0168-0072(94)00055-8
  3. Berarducci, Alessandro and Mamino, Marcello. 2023. “Provability logic: models within models in Peano Arithmetic” . Bollettino dell’Unione Mat. Ital. 16: 25-41. DOI: 10.1007/s40574-022-00325-9
  4. Berarducci, Alessandro and Otero, Margarita. 1996. “A Recursive Nonstandard Model of Normal Open Induction” . The Journal of Symbolic Logic 61 (4): 1228-41. DOI: 10.2307/2275813
  5. Bovykin, Andrey and Kaye, Richard. 2002. “Order-types of models of Peano arithmetic” . In Y. Zhang (edior) Logic and Algebra. Contemporary Mathematics 302 275-285. Providence: American Mathematical Society. DOI: 10.1017/bsl.2021.48
  6. Brouwer, Luitzen Egbertus Jan. 1912. “Intuitionism and formalism.”Bull. Amer. Math. Soc. 20: 81-96, (reprinted in Philosophy of Mathematics: Selected Readings 1984, edited by Paul Benacerraf and Hilary Putnam, 77-89. Cambridge: Cambridge University Press.
  7. Buss, Samuel R. 1986. Bounded Arithmetic. Napoli: Bibliopolis. DOI: 10.1111/j.1755-2567.1997.tb00745.x
  8. Chang, Chen Chung and Keisler, H. Jerome. 1978. Model Theory (third edition). Amsterdam: North Holland.
  9. Cooper, D. C. 1972. “Theorem-proving in arithmetic without multiplication”. Machine Intell. 7: 91–99.
  10. D’Aquino, Paola. 1992. “Local behaviour of the Chebyshev theorem in models of I∆ 0 ” . The Journal of Symbolic Logic 57 (1): 12-27. DOI: 10.2307/2275173
  11. D’Aquino, Paola. 1997. “Toward the Limits of the Tennenbaum Phenomenon” . Notre Dame Journal of Formal Logic 38 (1):81-92. DOI: 10.1305/ndjfl/1039700698
  12. D’Aquino, Paola and Macintyre, Angus. 2000. “Non-standard finite fields over I∆ 0 + Ω 1 ” . Israel Journal of Mathematics 117 (1): 311-333. DOI: 10.1007/BF02773575
  13. De Jongh, Dick, and Veltman, Frank. 1990. “Provability logics for relative interpretability” . In P. P. Petkov (editor) Mathematical Logic: 175-208. New York: Plenum Press. DOI: 10.1007/978-1-4613-0609-2_3
  14. Enderton, Herbert B. A mathematical introduction to logic (Second edition). Har- court/Academic Press: San Diego.
  15. Gaifman, Haim and Dimitracopoulos, Costas. 1982. “Fragments of Peano’s Arithmetic and the MRDP theorem” . Monographie de L’Enseignement Mathematique 30: 187-206.
  16. Girard, Jean Yves. 1987. Proof-theory and logical complexity I. Napoli: Bibliopolis.
  17. 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 and Davis, Sigal and Weyuker (1994): 4-39).
  18. Hájek, Peter and Pudlák, Pavel. 1993. Metamathematics of first order arithmetic. Berlin: Springer. DOI: 10.1017/9781316717271
  19. Harrison, John. 2009. Handbook of practical logic and authomated reasoning. Cambridge: Cambridge University Press. DOI: 10.1007/s10817-012-9251-8
  20. Hilbert, David and Bernays, Paul. 1934. Grundlagen der Mathematik I. Berlin: Springer.
  21. Kaye, Richard. 1991. Models of Peano arithmetic. Oxford: Oxford University Press. DOI: 10.2307/2275347
  22. Kennedy, Juliette. 2022. Gödel’s Incompleteness Theorems. Cambridge: Cambridge Univer- sity Press. DOI: 10.1017/9781108981972
  23. Kossak, Roman and Schmerl, James. 2006. The Structure of Models of Peano Arithmetic. Oxford: Oxford University Press. DOI: 10.1007/sll225-012-9407-x
  24. Montagna, F. 1987. “Provability in finite subtheories of PA” . The Journal of Symbolic Logic 52(2): 494–511. DOI: 10.2307/2274396
  25. Montagna, Franco and Mancini, Antonella. 1994. “A minimal predicative set theory” . Notre Dame Journal of Formal Logic 35 (2): 186-203. DOI: 10.1305/ndjfl/1094061860
  26. Mostowski, Andrzej W.. 1957. “On recursive models of formalised arithmetic”. Bulletin de l’Académie Polonaise des Sciences, Classe III, (5): 705-710
  27. Murawski, Roman. 1999. Recursive Functions and Metamathematics. Dordrecht: Kluwer. DOI: 10.1023/b133914
  28. Odifreddi, Piergiorgio. 1989. Classical Recursion Theory I. Amsterdam: North Holland. DOI: 10.2307/2274492
  29. Potthoff, Klaus. 1969. “Über Nichtstandardmodelle der Arithmetik und der rationalen Zahlen”. Zeitschrift für mathematische Logik und Grundlagen der Mathematik 15 (1969): 223-236.
  30. Rosser, Barkley. 1936. “Extensions of some theorems of Godel and Church. “ The Journal of Symb. Log. 1: 87-91
  31. Shavrukov, Volodya Yu. 1988. “The logic of relative interpretability over Peano arithmetic”. Preprint, Steklov Mathematical Institute, Moscow, 1988. In Russian.
  32. Shepherdson, John C. 1964. “A nonstandard model for a free variable fragment of number theory”. Bulletin of the Polish Academy of Sciences 12: 7. DOI: 10.2307/2295180
  33. Skolem,Thoralf. 1955. “Peano’s axioms and models of arithmetic”. In T. Skolem, G. Hasenjaeger, G. Kreisel, A. Robinson, H. Wang. L. Hen and J. Loś (editors) Mathematical Interpre- tations of Formal Systems 1-14. Amsterdam: North-Holland.
  34. Švejdar, Vítěszlav. 1983. “Modal analysis of generalized Rosser sentences.”The Journal of Symbolic Logic 48: 986-999. DOI: 10.2307/2274397
  35. Švejdar, Vítěszlav. 2007. “An interpretation of Robinson arithmetic in its Grzegorczyk’s weaker variant”. Fundamenta Informaticae 81 (1-3): 347-354.
  36. Tennenbaum, Stanley. 1959. “Non-Archimedean models for arithmetic.”Notices of the Ameri- can Mathematical Society 6: 270.
  37. Van Dalen, Dirk. 2013. Logic and Structure (5th ed.). Berlin: Springer. DOI: 10.2307/2274040
  38. Visser, Albert. 2009. “Why the theory R is special”. Logic Group preprint series, 279. Utrecht Univ. Now in In Friedman, H. and Tennants, N. (eds.) 2014. Foundational Adventures. Essay in honour of Harvey Friedman 7-23. London: College Publications. DOI: 10.1007/978-1-4419-0231-9_2
PDF
  • Anno di pubblicazione: 2025
  • Pagine: 99-120

XML
  • Anno di pubblicazione: 2025

Informazioni sul capitolo

Titolo del capitolo

First and second Gödel’s theorems and related results

Autori

Duccio Pianigiani

Lingua

Inglese

DOI

10.36253/979-12-215-0778-2.08

Opera sottoposta a peer review

Anno di pubblicazione

2025

Copyright

© 2025 Author(s)

Licenza d'uso

CC BY-SA 4.0

Licenza dei metadati

CC0 1.0

Informazioni bibliografiche

Titolo del libro

Lectures in Proof Theory and Complexity

Autori

Duccio Pianigiani

Opera sottoposta a peer review

Anno di pubblicazione

2025

Copyright

© 2025 Author(s)

Licenza d'uso

CC BY-SA 4.0

Licenza dei metadati

CC0 1.0

Editore

Firenze University Press, USiena Press

DOI

10.36253/979-12-215-0778-2

eISBN (pdf)

979-12-215-0778-2

eISBN (xml)

979-12-215-0779-9

Collana

UNIverSI. Ricerca e Didattica all’Università di Siena

ISSN della collana

3035-5915

e-ISSN della collana

3035-5931

119

Download dei libri

114

Visualizzazioni

Salva la citazione

1.481

Libri in accesso aperto

in catalogo

3.227

Capitoli di Libri

5.569.557

Download dei libri

5.515

Autori

da 1181 Istituzioni e centri di ricerca

di 66 Nazioni

77

scientific boards

da 413 Istituzioni e centri di ricerca

di 46 Nazioni

1.316

I referee

da 405 Istituzioni e centri di ricerca

di 39 Nazioni