<?xml version="1.0" encoding="utf-8" standalone="yes"?>
<TEI xmlns="http://www.tei-c.org/ns/1.0">
  <teiHeader>
    <fileDesc>
      <titleStmt>
        <title type="main" level="a">First and second Gödel’s theorems and related results</title>
        <author>
          <persName n="1" ref="https://orcid.org/0000-0001-9441-7226" type="ORCID">
            <forename>Duccio</forename>
            <surname>Pianigiani</surname>
            <placeName type="affiliation">University of Siena, Italy</placeName>
          </persName>
        </author>
        <respStmt>
          <resp>This is a section of <title>Lectures in Proof Theory and Complexity</title>(DOI: <idno type="DOI">10.36253/979-12-215-0778-2</idno>) by </resp>
          <name>Duccio Pianigiani</name>
        </respStmt>
      </titleStmt>
      <publicationStmt>
        <publisher>Firenze University Press, USiena Press</publisher>
        <pubPlace>Florence</pubPlace>
        <date when="2025">2025</date>
        <idno type="DOI">https://doi.org/10.36253/979-12-215-0778-2.08</idno>
        <availability>
          <p>Available for academic research purposes</p>
          <p>Open Access</p>
          <p>Copyright Author(s)</p>
          <licence source="text" target="https://creativecommons.org/licenses/by-sa/4.0/legalcode">
            <p>Content licence CC BY-SA 4.0</p>
          </licence>
          <licence source="metadata" target="https://creativecommons.org/publicdomain/zero/1.0/legalcode">
            <p>Metadata licence CC0 1.0</p>
          </licence>
        </availability>
      </publicationStmt>
      <sourceDesc>
        <p>This is original content, published for academic research purposes</p>
      </sourceDesc>
    </fileDesc>
    <encodingDesc>
      <appInfo>
        <application version="2.2" ident="Booksflow">
          <desc>Digital edition XML powered by Booksflow</desc>
        </application>
      </appInfo>
    </encodingDesc>
    <profileDesc>
      <abstract xml:lang="en">
        <p>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.</p>
      </abstract>
      <textClass>
        <keywords>
          <list>
            <item>first and second incompleteness theorems</item>
            <item>Presburger arithmetic</item>
            <item>Rosser sentences</item>
          </list>
        </keywords>
      </textClass>
    </profileDesc>
  </teiHeader>
  <text>
    <body>
      <p>It is available online at https://doi.org/10.36253/979-12-215-0778-2.08<ref target="https://doi.org/10.36253/979-12-215-0778-2.08" /></p>
      <div>
        <listBibl>
          <head>References</head>
          <bibl n="207617">
            <bibl>Berarducci, Alessandro. 1990. “The interpretability logic of Peano Arithmetic” . The Journal
of Symbolic Logic 55: 1059-1089.</bibl>
            <idno type="DOI">10.2307/2274474</idno>
          </bibl>
          <bibl n="207551">
            <bibl>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.</bibl>
            <idno type="DOI">10.1016/0168-0072(94)00055-8</idno>
          </bibl>
          <bibl n="207527">
            <bibl>Berarducci, Alessandro and Mamino, Marcello. 2023. “Provability logic: models within models
in Peano Arithmetic” . Bollettino dell’Unione Mat. Ital. 16: 25-41.</bibl>
            <idno type="DOI">10.1007/s40574-022-00325-9</idno>
          </bibl>
          <bibl n="207532">
            <bibl>Berarducci, Alessandro and Otero, Margarita. 1996. “A Recursive Nonstandard Model of
Normal Open Induction” . The Journal of Symbolic Logic 61 (4): 1228-41.</bibl>
            <idno type="DOI">10.2307/2275813</idno>
          </bibl>
          <bibl n="207472">
            <bibl>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.</bibl>
            <idno type="DOI">10.1017/bsl.2021.48</idno>
          </bibl>
          <bibl n="207445">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.</bibl>
          <bibl n="207780">
            <bibl>Buss, Samuel R. 1986. Bounded Arithmetic. Napoli: Bibliopolis.</bibl>
            <idno type="DOI">10.1111/j.1755-2567.1997.tb00745.x</idno>
          </bibl>
          <bibl n="207701">Chang, Chen Chung and Keisler, H. Jerome. 1978. Model Theory (third edition). Amsterdam:
North Holland.</bibl>
          <bibl n="207707">Cooper, D. C. 1972. “Theorem-proving in arithmetic without multiplication”. Machine Intell. 7: 91–99.</bibl>
          <bibl n="207594">
            <bibl>D’Aquino, Paola. 1992. “Local behaviour of the Chebyshev theorem in models of I∆ 0 ” . The
Journal of Symbolic Logic 57 (1): 12-27.</bibl>
            <idno type="DOI">10.2307/2275173</idno>
          </bibl>
          <bibl n="207632">
            <bibl>D’Aquino, Paola. 1997. “Toward the Limits of the Tennenbaum Phenomenon” . Notre Dame
Journal of Formal Logic 38 (1):81-92.</bibl>
            <idno type="DOI">10.1305/ndjfl/1039700698</idno>
          </bibl>
          <bibl n="207574">
            <bibl>D’Aquino, Paola and Macintyre, Angus. 2000. “Non-standard finite fields over I∆ 0 + Ω 1 ” .
Israel Journal of Mathematics 117 (1): 311-333.</bibl>
            <idno type="DOI">10.1007/BF02773575</idno>
          </bibl>
          <bibl n="207506">
            <bibl>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.</bibl>
            <idno type="DOI">10.1007/978-1-4613-0609-2_3</idno>
          </bibl>
          <bibl n="207666">Enderton, Herbert B. A mathematical introduction to logic (Second edition). Har-
court/Academic Press: San Diego.</bibl>
          <bibl n="207524">Gaifman, Haim and Dimitracopoulos, Costas. 1982. “Fragments of Peano’s Arithmetic and
the MRDP theorem” . Monographie de L’Enseignement Mathematique 30: 187-206.</bibl>
          <bibl n="207755">Girard, Jean Yves. 1987. Proof-theory and logical complexity I. Napoli: Bibliopolis.</bibl>
          <bibl n="207441">G&amp;#246;del, Kurt. 1931. “&amp;#220;ber Formal Unentscheidbare S&amp;#228;tze der Principia Mathematica und
Verwandter Systeme I” . Monatshefte f&amp;#252;r Mathematik und Physik 38: 173-198 (reprinted
in G&amp;#246;del’s Collected Works (1986-2005), Vol. I: 144-195 and Davis, Sigal and Weyuker
(1994): 4-39).</bibl>
          <bibl n="207716">
            <bibl>H&amp;#225;jek, Peter and Pudl&amp;#225;k, Pavel. 1993. Metamathematics of first order arithmetic. Berlin:
Springer.</bibl>
            <idno type="DOI">10.1007/978-3-662-22156-3</idno>
          </bibl>
          <bibl n="207660">
            <bibl>Harrison, John. 2009. Handbook of practical logic and authomated reasoning. Cambridge:
Cambridge University Press.</bibl>
            <idno type="DOI">10.1007/s10817-012-9251-8</idno>
          </bibl>
          <bibl n="207746">Hilbert, David and Bernays, Paul. 1934. Grundlagen der Mathematik I. Berlin: Springer.</bibl>
          <bibl n="207766">
            <bibl>Kaye, Richard. 1991. Models of Peano arithmetic. Oxford: Oxford University Press.</bibl>
            <idno type="DOI">10.2307/2275347</idno>
          </bibl>
          <bibl n="207717">
            <bibl>Kennedy, Juliette. 2022. G&amp;#246;del’s Incompleteness Theorems. Cambridge: Cambridge Univer-
sity Press.</bibl>
            <idno type="DOI">10.1017/9781108981972</idno>
          </bibl>
          <bibl n="207644">
            <bibl>Kossak, Roman and Schmerl, James. 2006. The Structure of Models of Peano Arithmetic.
Oxford: Oxford University Press.</bibl>
            <idno type="DOI">10.1007/sll225-012-9407-x</idno>
          </bibl>
          <bibl n="207686">
            <bibl>Montagna, F. 1987. “Provability in finite subtheories of PA” . The Journal of Symbolic Logic
52(2): 494–511.</bibl>
            <idno type="DOI">10.2307/2274396</idno>
          </bibl>
          <bibl n="207583">
            <bibl>Montagna, Franco and Mancini, Antonella. 1994. “A minimal predicative set theory” . Notre
Dame Journal of Formal Logic 35 (2): 186-203.</bibl>
            <idno type="DOI">10.1305/ndjfl/1094061860</idno>
          </bibl>
          <bibl n="207556">Mostowski, Andrzej W.. 1957. “On recursive models of formalised arithmetic”. Bulletin de
l’Acad&amp;#233;mie Polonaise des Sciences, Classe III, (5): 705-710</bibl>
          <bibl n="207762">
            <bibl>Murawski, Roman. 1999. Recursive Functions and Metamathematics. Dordrecht: Kluwer.</bibl>
            <idno type="DOI">10.1023/b133914</idno>
          </bibl>
          <bibl n="207752">
            <bibl>Odifreddi, Piergiorgio. 1989. Classical Recursion Theory I. Amsterdam: North Holland.</bibl>
            <idno type="DOI">10.2307/2274492</idno>
          </bibl>
          <bibl n="207497">Potthoff, Klaus. 1969. “&amp;#220;ber Nichtstandardmodelle der Arithmetik und der rationalen Zahlen”.
Zeitschrift f&amp;#252;r mathematische Logik und Grundlagen der Mathematik 15 (1969): 223-236.</bibl>
          <bibl n="207681">Rosser, Barkley. 1936. “Extensions of some theorems of Godel and Church. “ The Journal of Symb. Log. 1: 87-91</bibl>
          <bibl n="207525">Shavrukov, Volodya Yu. 1988. “The logic of relative interpretability over Peano arithmetic”.
Preprint, Steklov Mathematical Institute, Moscow, 1988. In Russian.</bibl>
          <bibl n="207562">
            <bibl>Shepherdson, John C. 1964. “A nonstandard model for a free variable fragment of number
theory”. Bulletin of the Polish Academy of Sciences 12: 7.</bibl>
            <idno type="DOI">10.2307/2295180</idno>
          </bibl>
          <bibl n="207450">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.</bibl>
          <bibl n="207645">
            <bibl>Švejdar, V&amp;#237;těszlav. 1983. “Modal analysis of generalized Rosser sentences.”The Journal of
Symbolic Logic 48: 986-999.</bibl>
            <idno type="DOI">10.2307/2274397</idno>
          </bibl>
          <bibl n="207557">Švejdar, V&amp;#237;těszlav. 2007. “An interpretation of Robinson arithmetic in its Grzegorczyk’s weaker
variant”. Fundamenta Informaticae 81 (1-3): 347-354.</bibl>
          <bibl n="207636">Tennenbaum, Stanley. 1959. “Non-Archimedean models for arithmetic.”Notices of the Ameri-
can Mathematical Society 6: 270.</bibl>
          <bibl n="207775">
            <bibl>Van Dalen, Dirk. 2013. Logic and Structure (5th ed.). Berlin: Springer.</bibl>
            <idno type="DOI">10.2307/2274040</idno>
          </bibl>
          <bibl n="207448">
            <bibl>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.</bibl>
            <idno type="DOI">10.1007/978-1-4419-0231-9_2</idno>
          </bibl>
        </listBibl>
      </div>
    </body>
  </text>
</TEI>